Optimizar la implementación de Karatsuba

Question

Por lo tanto, estoy tratando de mejorar algunas de las operaciones que ofrece la clase BigInteger de .net 4 ya que las operaciones parecen ser cuadráticas. Hice una implementación aproximada de Karatsuba, pero aún es más lento de lo que esperaba.

El problema principal parece ser que BigInteger no proporciona una forma simple de contar el número de bits y, entonces, tengo que usar BigInteger.Log (..., 2). Según Visual Studio, aproximadamente el 80-90% del tiempo se gasta en calcular logaritmos.

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

Entonces, ¿qué puedo hacer para acelerarlo?

Answer 1

¿Por qué contar todos los bits?

en VB hago esto:

<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 

En C# sería:

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

Finalmente ...

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

Al llamar al método de extensión puede ralentizar las cosas por lo quizás esto sería más rápido:

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

FYI: con el método de longitud de bits también se puede calcular una buena aproximación del registro mucho más rápido que el Método BigInteger.

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

Por lo que el acceso a la matriz de UInt32 interna de la estructura BigInteger, aquí es un corte para eso.

importe el espacio de reflexión

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 

entonces se puede obtener la UInteger() subyacente del entero grande como

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

o alternativamente

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

Tenga en cuenta que _bits FieldInfo puede ser utilizado para acceder directamente al campo subyacente UInteger() _bits de la estructura de BigInteger re. Esto es más rápido que invocar el método ToUInt32Array(). Sin embargo, cuando BigInteger B < = UInteger.MaxValue _bits no es nada. Sospecho que, como optimización, cuando un BigInteger se ajusta al tamaño de una palabra de 32 bits (tamaño de la máquina), MS devuelve la aritmética de la palabra máquina normal utilizando el tipo de datos nativo.

Tampoco he podido utilizar _bits.SetValue (B, Data()) como normalmente lo haría con la reflexión. Para solucionar este problema, utilizo el constructor BigInteger (bytes() b) que tiene una sobrecarga. En C# puede usar operaciones de puntero inseguras para convertir un UInteger() en Byte(). Como no hay operaciones de puntero en VB, utilizo Buffer.BlockCopy. Cuando se accede a los datos de esta manera, es importante tener en cuenta que si se establece el MSB del conjunto de bytes(), MS lo interpreta como un número negativo. Preferiría que hicieran un constructor con un campo de signo separado.La palabra matriz es añadir una adición 0 bytes para hacer desmarques el MSB

Además, al elevar al cuadrado se puede mejorar aún más

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 

Esto elimina 2 turnos, 2 adiciones y 3 sustracciones a cada recursión de su algoritmo de multiplicación