Karatsuba 구현 최적화

Question

그래서, 네 번째 연산 인 .net 4의 BigInteger 클래스가 제공하는 연산을 개선하려고합니다. 거친 Karatsuba 구현을 만들었지 만 예상보다 느립니다.

주요 문제는 BigInteger가 비트 수를 계산할 수있는 간단한 방법이 없으므로 BigInteger.Log (..., 2)를 사용해야한다는 것입니다. Visual Studio에 따르면 약 80-90 %의 시간이 로그를 계산하는 데 소비됩니다.

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

그래서 속도를 높이려면 어떻게해야합니까?

Answer 1

왜 모든 비트를 계산합니까? VB에서

나는이 작업을 수행 : 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 

이 될 것입니다 :

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

마지막으로

...

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

일을 너무 느려질 수 있습니다 확장 메서드를 호출 아마도 더 빠를 것입니다 :

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

참고 : 비트 길이 방법을 사용하면 BigInteger 방법보다 훨씬 빠르게 로그를 근사 할 수 있습니다.

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

BigInteger 구조체의 내부 UInt32 배열에 액세스하는 한, 여기에 대한 해킹이 있습니다.

수입

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 

가 그런 다음의 fieldInfo 수 _bits

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

또는 다른 방법으로

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

참고로 큰 정수의) (기본 UInteger를 얻을 수있는 반사 네임 스페이스 BigInteger 구조체의 기본 UInteger() _bits 필드에 직접 액세스하는 데 사용됩니다. 레. 이 방법은 ToUInt32Array() 메서드를 호출하는 것보다 빠릅니다. 그러나 BigInteger B < = UInteger.MaxValue _bit는 아무 것도 아닙니다. 나는 BigInteger가 32 비트 (기계 크기) word의 크기에 맞을 때 MS return이 네이티브 데이터 형식을 사용하여 일반 기계어 산술 연산을 수행 할 때 최적화라고 생각합니다.

리플렉션을 사용하여 평상시처럼 _bits.SetValue (B, Data())를 사용할 수 없었습니다. 이 문제를 해결하려면 오버 헤드가있는 BigInteger (bytes() b) 생성자를 사용합니다. C#에서는 안전하지 않은 포인터 연산을 사용하여 UInteger()를 Byte()로 캐스팅 할 수 있습니다. VB에는 포인터 연산이 없으므로 Buffer.BlockCopy를 사용합니다. 이 방식으로 데이터에 액세스 할 때 bytes() 배열의 MSB가 설정되면 MS는이를 음수로 해석합니다. 나는 그들이 별도의 사인 필드를 가진 생성자를 만든 것을 선호 할 것이다.단어의 배열은, 당신이 더욱 향상시킬 수 있습니다 제곱 때 또한 MSB

의 선택을 취소하게 할 수있는 별도의 0 바이트를 추가하는 것입니다

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 

이 각 재귀에서 2 개 교대, 2 개 추가 및 3 뺄셈을 제거하여 곱셈 알고리즘.