करात्सुबा कार्यान्वयन को अनुकूलित करना

Question

तो, मैं कुछ संचालन को बेहतर बनाने की कोशिश कर रहा हूं .net 4 की BigInteger कक्षा प्रदान करता है क्योंकि ऑपरेशन वर्गबद्ध प्रतीत होते हैं। मैंने एक मोटा करात्सुबा कार्यान्वयन किया है लेकिन यह अभी भी धीमा है जितना मैं उम्मीद करता हूं।

मुख्य समस्या यह प्रतीत होती है कि BigInteger बिट्स की संख्या को गिनने का कोई आसान तरीका नहीं प्रदान करता है, इसलिए, मुझे BigInteger.Log (..., 2) का उपयोग करना होगा। विजुअल स्टूडियो के अनुसार, लगभग 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 में मैं यह कर:

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

एफवाईआई: बिट लम्बाई विधि के साथ आप बिगइंटर विधि से लॉग की अच्छी अनुमानित गणना भी कर सकते हैं।

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 

तो फिर तुम अंतर्निहित UInteger) बड़ा पूर्णांक के रूप में

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

या वैकल्पिक रूप से

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

ध्यान दें कि fieldinfo कर सकते हैं _bits प्राप्त कर सकते हैं (BigInteger structu के अंतर्निहित UInteger() _bits फ़ील्ड को सीधे एक्सेस करने के लिए उपयोग किया जाए कर रहे हैं। यह ToUInt32Array() विधि को आविष्कार करने से तेज़ है। हालांकि, जब BigInteger B < = UInteger.MaxValue _bits कुछ भी नहीं है। मुझे संदेह है कि जब एक बिगइंटर 32 बिट (मशीन आकार) शब्द के आकार को फिट करता है तो अनुकूलन के रूप में एमएस रिटर्न मूल डेटा प्रकार का उपयोग करके सामान्य मशीन शब्द अंकगणित करता है।

मैं _bits.SetValue (बी, डेटा()) का उपयोग करने में भी सक्षम नहीं हूं क्योंकि आप आमतौर पर प्रतिबिंब का उपयोग करने में सक्षम होंगे। इस के आसपास काम करने के लिए मैं BigInteger (बाइट्स) बी) कन्स्ट्रक्टर का उपयोग करता हूं जो ओवरहेड है। सी # में आप Uteteger() को बाइट() में डालने के लिए असुरक्षित पॉइंटर ऑपरेशंस का उपयोग कर सकते हैं। चूंकि वीबी में कोई पॉइंटर ओप नहीं है, इसलिए मैं बफर.ब्लॉककॉपी का उपयोग करता हूं। डेटा को इस तरह एक्सेस करते समय यह ध्यान रखना महत्वपूर्ण है कि यदि बाइट्स() सरणी का एमएसबी सेट किया गया है, तो एमएस इसे नकारात्मक संख्या के रूप में व्याख्या करता है। मैं पसंद करता हूं कि उन्होंने एक अलग चिह्न क्षेत्र के साथ एक कन्स्ट्रक्टर बनाया।शब्द सरणी, जब बराबरी आप आगे भी सुधार कर सकते हैं 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 subtractions समाप्त अपने गुणा एल्गोरिदम।