Ottimizzazione dell'implementazione di Karatsuba

Question

Quindi, sto cercando di migliorare alcune delle operazioni che la classe di .net 4 BigInteger fornisce poiché le operazioni sembrano essere quadratiche. Ho realizzato un'implementazione rough di Karatsuba ma è ancora più lento di quanto mi aspettassi.

Il problema principale sembra essere che BigInteger non fornisce un modo semplice per contare il numero di bit e, quindi, devo usare BigInteger.Log (..., 2). Secondo Visual Studio, circa l'80-90% del tempo viene impiegato per calcolare i logaritmi.

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(); 
     } 
    } 
} 

Quindi, cosa posso fare per accelerarlo?

Answer 1

Perché contare tutti i bit?

in VB faccio questo:

<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 

In C# sarebbe:

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; 
} 

Infine ...

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)); 
    } 

Chiamando il metodo di estensione può rallentare le cose così forse questo sarebbe più veloce:

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

FYI: con il metodo della lunghezza di bit è anche possibile calcolare una buona approssimazione del log molto più velocemente rispetto al metodo BigInteger.

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

quanto riguarda l'accesso alla matrice UInt32 interna della struttura BigInteger, ecco un hack per questo.

importazione del namespace riflessione

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 

allora si può ottenere l'UInteger sottostante() del grande intero come

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

o alternativa

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

Nota che _bits FieldInfo può essere utilizzato per accedere direttamente al campo _bits UInteger() sottostante della structu BigInteger ri. Questo è più veloce del richiamo del metodo ToUInt32Array(). Tuttavia, quando BigInteger B < = Ubitte UInteger.MaxValue non è nulla. Sospetto che come ottimizzazione quando un BigInteger si adatta alle dimensioni di una parola di 32 bit (dimensione della macchina), MS restituisce l'aritmetica normale della parola macchina utilizzando il tipo di dati nativo.

Inoltre, non sono stato in grado di utilizzare _bits.SetValue (B, Data()) come normalmente si sarebbe in grado di utilizzare il reflection. Per ovviare a ciò, utilizzo il costruttore BigInteger (bytes() b) che ha un sovraccarico. In C# è possibile utilizzare operazioni di puntatore non sicure per eseguire il cast di un UInteger() su Byte(). Poiché non ci sono op di puntatore in VB, io uso Buffer.BlockCopy. Quando si accede ai dati in questo modo è importante notare che se l'MSB dell'array bytes() è impostato, MS lo interpreta come un numero negativo. Preferirei che facessero un costruttore con un campo separato.L'array parola è di aggiungere un'aggiunta 0 byte per rendere deselezionare la MSB

Inoltre, quando la quadratura è possibile migliorare ulteriormente

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 

Questo elimina 2 turni, 2 aggiunte e 3 sottrazioni di ogni ricorsione della vostra algoritmo di moltiplicazione.