Arbeiten mit Zahlen größer als den maximalen Dezimalwert

Question

Ich arbeite mit dem Produkt der ersten 26 Primzahlen. Dies erfordert mehr als 52 Bits an Genauigkeit, was meiner Meinung nach das Maximum ist, das ein Double bewältigen kann, und mehr als die 28-29 signifikanten Stellen, die eine Dezimalzahl liefern kann. Was wären also Strategien für die Multiplikation und Division von so großen Zahlen?

Welche Auswirkungen hätte die Performance auch auf die Reifen, durch die ich springen musste, um dies zu erreichen?

Das Produkt der ersten 22 Primzahlen (die ich auf meinem Rechner miteinander multiplizieren, ohne in wissenschaftlichen Modus zu fallen) ist:

10,642,978,845,819,148,849,204,664,294,430 

Das Produkt der letzten vier

72,370,439 

ist

Wenn miteinander multipliziert, die ich erhalten:

7.7023705133964511682328635583552e+38 

Die Auswirkungen auf die Leistung ein Das ist hier besonders wichtig, weil wir im Wesentlichen versuchen, die Frage zu lösen, ob eine Primzahl-String-Vergleichslösung in der Praxis schneller ist als ein direkter Vergleich von Zeichen. Der Beitrag, der zu dieser Untersuchung geführt hat, lautet here. Prozessoren sind für Gleitkommaberechnungen optimiert; Idealerweise möchte ich so viel von dieser Optimierung in jeder Lösung nutzen, die mir am Ende steht.

TIA!
James

PS: Der Code, den ich habe, ist für eine konkurrierende Lösung; Ich glaube nicht, dass die Primzahllösung möglicherweise schneller sein kann, aber ich versuche, ihr die fairste Chance zu geben.

Answer 1

Sie können BigInteger in C# 4.0 verwenden. Für ältere Versionen, denke ich, dass Sie eine Open Source-Bibliothek wie this one

Answer 2

Ich lese den Beitrag, den Sie verknüpft, über die Interviewfrage. Da Sie diese großen ganzen Zahlen nur multiplizieren und aufteilen, ist eine große Optimierung, sie in ihrer prime-factorized Form zu halten. Jede große Ganzzahl ist eine Matrix [0..25] von Inten, wobei jedes Element den Exponenten der n-ten Primzahl bei der Faktorisierung darstellt. Um zwei große Ganzzahlen in dieser Form zu multiplizieren, fügen Sie einfach die Exponenten Element-für-Element hinzu; zum Dividieren, Subtrahieren von Exponenten.

Aber Sie werden sehen, dass dies der Tabellierung von Zeichen zählt auf den beiden Strings entspricht.