Also versuche ich, einige der Operationen zu verbessern, die die Klasse BigInteger von .net 4 bietet, da die Operationen quadratisch erscheinen. Ich habe eine grobe Karatsuba-Implementierung gemacht, aber es ist immer noch langsamer als erwartet.
Das Hauptproblem scheint zu sein, dass BigInteger keine einfache Möglichkeit bietet, die Anzahl der Bits zu zählen, und deshalb muss ich BigInteger.Log (..., 2) verwenden. Laut Visual Studio werden etwa 80-90% der Zeit für die Berechnung von Logarithmen verwendet.
%Vor%Also, was kann ich tun, um es zu beschleunigen?
Warum alle Bits zählen?
In vb mache ich das:
%Vor%In C # wäre es:
%Vor%Endlich ...
%Vor%Wenn Sie die Erweiterungsmethode aufrufen, kann dies die Geschwindigkeit verlangsamen, was vielleicht schneller wäre:
%Vor%Zu Ihrer Information: Mit der Bitlängenmethode können Sie auch eine gute Approximation des Logs schneller berechnen als die BigInteger-Methode.
%Vor%Was den Zugriff auf das interne UInt32-Array der BigInteger-Struktur betrifft, ist hier ein Hack dafür.
Importieren Sie den Reflexionsnamensraum
%Vor%Dann können Sie den zugrunde liegenden UInteger () der großen Ganzzahl als
erhalten %Vor%oder alternativ
%Vor%Beachten Sie, dass _bits fieldinfo verwendet werden kann, um direkt auf das zugrunde liegende UInteger () _bits-Feld der BigInteger-Struktur zuzugreifen. Dies ist schneller als das Aufrufen der ToUInt32Array () -Methode. Wenn BigInteger B & lt; = UInteger.MaxValue _bits jedoch nichts ist. Ich vermute, dass eine Optimierung, wenn ein BigInteger der Größe eines 32-Bit-Wortes (Maschinengröße) entspricht, MS-Returns normale Maschinenwortarithmetik unter Verwendung des nativen Datentyps ausführt.
Ich war auch nicht in der Lage, die _bits.SetValue (B, Data ()) zu verwenden, wie Sie normalerweise Reflektion verwenden könnten. Um dies zu umgehen, benutze ich den BigInteger (bytes () b) -Konstruktor, der Overhead hat. In c # können Sie mit unsicheren Zeigeroperationen ein UInteger () in Byte () umwandeln. Da es in VB keine Zeigeroperationen gibt, verwende ich Buffer.BlockCopy. Wenn auf diese Weise auf die Daten zugegriffen wird, ist es wichtig zu beachten, dass wenn das MSB des Arrays bytes () gesetzt ist, MS es als eine negative Zahl interpretiert. Ich würde es vorziehen, dass sie einen Konstruktor mit einem separaten Zeichenfeld gemacht haben. Das Word-Array fügt ein zusätzliches Byte 0 hinzu, um das MSB zu deaktivieren
Auch beim Quadrieren können Sie noch besser werden
%Vor%Dies eliminiert 2 Verschiebungen, 2 Additionen und 3 Subtraktionen von jeder Rekursion Ihres Multiplikationsalgorithmus.
Tags und Links biginteger c#