Karatsuba Uygulamasının Optimize Edilmesi

Question

Bu nedenle, operasyonların ikinci dereceden göründüğü için .net 4'ün BigInteger sınıfının sağladığı bazı işlemleri geliştirmeye çalışıyorum. Zor bir Karatsuba uygulaması yaptım ama beklediğimden daha yavaş.

Ana sorun BigInteger bit sayısını saymak için basit bir yol sağlaması gibi görünüyor ve BigInteger.Log (..., 2) kullanmak zorundayım. Visual Studio'ya göre, zamanın yaklaşık% 80-90'ı logaritma hesaplamak için harcanmaktadır.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Numerics; 

namespace Test 
{ 
    class Program 
    { 
     static BigInteger Karatsuba(BigInteger x, BigInteger y) 
     { 
      int n = (int)Math.Max(BigInteger.Log(x, 2), BigInteger.Log(y, 2)); 
      if (n <= 10000) return x * y; 

      n = ((n+1)/2); 

      BigInteger b = x >> n; 
      BigInteger a = x - (b << n); 
      BigInteger d = y >> n; 
      BigInteger c = y - (d << n); 

      BigInteger ac = Karatsuba(a, c); 
      BigInteger bd = Karatsuba(b, d); 
      BigInteger abcd = Karatsuba(a+b, c+d); 

      return ac + ((abcd - ac - bd) << n) + (bd << (2 * n)); 
     } 

     static void Main(string[] args) 
     { 
      BigInteger x = BigInteger.One << 500000 - 1; 
      BigInteger y = BigInteger.One << 600000 + 1; 
      BigInteger z = 0, q; 

      Console.WriteLine("Working..."); 
      DateTime t; 

      // Test standard multiplication 
      t = DateTime.Now; 
      z = x * y; 
      Console.WriteLine(DateTime.Now - t); 

      // Test Karatsuba multiplication 
      t = DateTime.Now; 
      q = Karatsuba(x, y); 
      Console.WriteLine(DateTime.Now - t); 

      // Check they're equal 
      Console.WriteLine(z == q); 

      Console.Read(); 
     } 
    } 
} 

Peki, hızlandırmak için ne yapabilirim?

Answer 1

Neden tüm bitleri sayıyorsunuz? fi olarak

Bunu yapmak: C# '

<Runtime.CompilerServices.Extension()> _ 
Function BitLength(ByVal n As BigInteger) As Integer 
    Dim Data() As Byte = n.ToByteArray 
    Dim result As Integer = (Data.Length - 1) * 8 
    Dim Msb As Byte = Data(Data.Length - 1) 
    While Msb 
     result += 1 
     Msb >>= 1 
    End While 
    Return result 
End Function 

olurdu:

public static int BitLength(this BigInteger n) 
{ 
    byte[] Data = n.ToByteArray(); 
    int result = (Data.Length - 1) * 8; 
    byte Msb = Data[Data.Length - 1]; 
    while (Msb != 0) { 
     result += 1; 
     Msb >>= 1; 
    } 
    return result; 
} 

Nihayet

...

static BigInteger Karatsuba(BigInteger x, BigInteger y) 
    { 
     int n = (int)Math.Max(x.BitLength(), y.BitLength()); 
     if (n <= 10000) return x * y; 

     n = ((n+1)/2); 

     BigInteger b = x >> n; 
     BigInteger a = x - (b << n); 
     BigInteger d = y >> n; 
     BigInteger c = y - (d << n); 

     BigInteger ac = Karatsuba(a, c); 
     BigInteger bd = Karatsuba(b, d); 
     BigInteger abcd = Karatsuba(a+b, c+d); 

     return ac + ((abcd - ac - bd) << n) + (bd << (2 * n)); 
    } 

şeyler öylesine yavaşlatabilir uzatma yöntemini çağırma belki bu daha hızlı olurdu:

int n = (int)Math.Max(BitLength(x), BitLength(y)); 

FYI: bit uzunluk yöntemiyle, BigInteger Yönteminden çok daha hızlı bir şekilde logun iyi bir yaklaşımını hesaplayabilirsiniz.

bits = BitLength(a) - 1; 
log_a = (double)i * log(2.0); 

Bildiğim kadarıyla BigInteger yapının iç Uınt32 Dizisi erişme gibi, burada bunun için kesmek.

ithalat

Private Shared ArrM As MethodInfo 
Private Shard Bits As FieldInfo 
Shared Sub New() 
    ArrM = GetType(System.Numerics.BigInteger).GetMethod("ToUInt32Array", BindingFlags.NonPublic Or BindingFlags.Instance) 
    Bits = GetType(System.Numerics.BigInteger).GetMember("_bits", BindingFlags.NonPublic Or BindingFlags.Instance)(0) 

End Sub 
<Extension()> _ 
Public Function ToUInt32Array(ByVal Value As System.Numerics.BigInteger) As UInteger() 
    Dim Result() As UInteger = ArrM.Invoke(Value, Nothing) 
    If Result(Result.Length - 1) = 0 Then 
     ReDim Preserve Result(Result.Length - 2) 
    End If 
    Return Result 
End Function 

Sonra Fieldınfo can _bits

Dim Data() As UInteger = ToUInt32Array(Value) 
Length = Data.Length 

veya Alternatif

Dim Data() As UInteger = Value.ToUInt32Array() 

Not kadar büyük tamsayı) (altta yatan UInteger alabilirsiniz yansıma ad BigInteger structu'nun temelindeki UInteger() _bits alanına doğrudan erişmek için kullanılır yeniden. Bu, ToUInt32Array() yöntemini çağırmaktan daha hızlıdır. Ancak, BigInteger B < = UInteger.MaxValue _bits bir şey değildir. Bir BigInteger 32 bit (makine boyutunda) kelimesinin büyüklüğüne uyduğunda optimizasyon olarak, MS geri dönüşünün normal veri türünü kullanarak normal makine kelimesi aritmetiği gerçekleştirdiğinden şüpheleniyorum.

Normalde yansıma kullanabilmeniz için _bits.SetValue (B, Data()) yöntemini kullanamıyorum. Etrafında çalışmak için yükü olan BigInteger (bytes() b) yapıcısını kullanıyorum. C# 'da bir UInteger()' i Byte() 'a çevirmek için güvensiz işaretçi işlemlerini kullanabilirsiniz. VB'de işaretçi ops olmadığından, Buffer.BlockCopy'yi kullanıyorum. Verilere bu şekilde erişirken, bytes() dizisinin MSB'si ayarlanmışsa, MS'in bunu bir Negatif sayı olarak algıladığını belirtmek önemlidir. Ayrı bir işaret alanına sahip bir kurucu yapmasını tercih ederim.kelime dizisi, hatta daha da artırabilir kare alma Ayrıca MSB

işaretini kaldırın yapmak için bir ek 0 bayt eklemektir

Function KaratsubaSquare(ByVal x As BigInteger) 
    Dim n As Integer = BitLength(x) 'Math.Max(BitLength(x), BitLength(y)) 

    If (n <= KaraCutoff) Then Return x * x 
    n = ((n + 1) >> 1) 

    Dim b As BigInteger = x >> n 
    Dim a As BigInteger = x - (b << n) 
    Dim ac As BigInteger = KaratsubaSquare(a) 
    Dim bd As BigInteger = KaratsubaSquare(b) 
    Dim c As BigInteger = Karatsuba(a, b) 
    Return ac + (c << (n + 1)) + (bd << (2 * n)) 

End Function 

Bu her özyineleme 2 vardiya, 2 eklemeler ve çıkarmalar 3 ortadan kaldırır senin çarpma algoritması.