Wie mit beliebig großen Ganzzahlen zu behandeln ist

Question

Ich arbeite an einer Programmiersprache, und heute bekam ich den Punkt, wo ich die faktorielle Funktion (rekursiv) kompilieren konnte, aber aufgrund der maximalen Größe einer ganzen Zahl kann ich die größte bekommen Fakultät (12). Was sind einige Techniken für die Behandlung von ganzen Zahlen beliebiger Größe? Die Sprache arbeitet derzeit, indem sie Code in C++ übersetzt.

Answer 1

Wenn Sie mehr als 32 Bits benötigen, können Sie die Verwendung von 64-Bit-Ganzzahlen (long long) in Betracht ziehen oder eine mathematische Bibliothek mit beliebiger Genauigkeit verwenden, z. GNU MP.

Answer 2

Es gibt keine einfache Möglichkeit, es in C++ zu tun. Sie müssen eine externe Bibliothek wie GNU Multiprecision verwenden oder eine andere Sprache verwenden, die nativ große Ganzzahlen wie Python unterstützt.

Answer 3

Andere Poster haben Links zu Bibliotheken, die dies für Sie tun, aber es scheint, als ob Sie versuchen, dies in Ihre Sprache zu bauen. Mein erster Gedanke ist: Bist du sicher, dass du das tun musst? Die meisten Sprachen würden eine Add-on-Bibliothek verwenden, wie andere vorgeschlagen haben.

Angenommen, Sie schreiben einen Compiler, und Sie benötigen diese Funktion, können Sie arithmetische Ganzzahlfunktionen für beliebig große Werte in Assembly implementieren.

Zum Beispiel würde eine einfache (aber nicht optimale) Implementierung die Zahlen als binär codierte Dezimalzahlen darstellen. Die arithmetischen Funktionen könnten die gleichen Algorithmen verwenden, die Sie verwenden würden, wenn Sie mit Bleistift und Papier rechnen würden.

Verwenden Sie auch einen speziellen Datentyp für diese großen Ganzzahlen. Auf diese Weise können "normale" Ganzzahlen die 32-Bit-Standardarithmetik verwenden.

Answer 4

Meine bevorzugte Vorgehensweise wäre, meinen aktuellen Int-Typ für 32-Bit-Ints zu verwenden (oder ihn intern so zu ändern, dass er lang oder ähnlich ist, solange er dieselben Algorithmen verwenden kann) Wenn es überläuft, ändere es, indem du es als bignum speicherst, sei es von mir selbst oder mit einer externen Bibliothek. Ich habe jedoch das Gefühl, dass ich bei jeder einzelnen arithmetischen Operation auf einen Überlauf prüfen müsste, etwa zweimal bei arithmetischen Operationen. Wie könnte ich das lösen?

Answer 5

Wenn Sie dies in eine Sprache (für Lernzwecke würde ich raten), würde ich wahrscheinlich eine kleine BCD-Bibliothek schreiben. Speichern Sie Ihre BCD-Nummern einfach in Byte-Arrays.

In der Tat, mit den heutigen riesigen Speicherfähigkeiten, könnten Sie nur ein Byte-Array verwenden, wo jedes Byte nur eine Ziffer (0-9) enthält. Sie schreiben dann Ihre eigene Routine, um Ihre Byte-Arrays hinzuzufügen, zu subtrahieren und zu teilen.

(Teilen ist die harte, aber ich wette, dass Sie für einige Code finden dort irgendwo.)

Ich kann Ihnen einige Java-like psuedocode geben, kann aber nicht wirklich tun C++ von Grund auf neu an dieser Stelle:

class BigAssNumber { 
    private byte[] value; 

    // This constructor can handle numbers where overflows have occurred. 
    public BigAssNumber(byte[] value) { 
     this.value=normalize(value); 
    } 

    // Adds two numbers and returns the sum. Originals not changed. 
    public BigAssNumber add(BigAssNumber other) { 
     // This needs to be a byte by byte copy in newly allocated space, not pointer copy! 
     byte[] dest = value.length > other.length ? value : other.value;   

     // Just add each pair of numbers, like in a pencil and paper addition problem. 
     for(int i=0; i<min(value.length, other.value.length); i++) 
      dest[i]=value[i]+other.value[i]; 

     // constructor will fix overflows. 
     return new BigAssNumber(dest); 
    } 

    // Fix things that might have overflowed 0,17,22 will turn into 1,9,2   
    private byte[] normalize(byte [] value) { 
     if (most significant digit of value is not zero) 
      extend the byte array by a few zero bytes in the front (MSB) position. 

     // Simple cheap adjust. Could lose inner loop easily if It mattered. 
     for(int i=0;i<value.length;i++) 
      while(value[i] > 9) { 
       value[i] -=10; 
       value[i+1] +=1; 
      } 
     } 
    } 
} 

ich die Tatsache, dass wir viel mehr Platz in einem Byte zu helfen, mit zusätzlich überläuft in allgemeiner Weise zu tun haben. Kann auch für die Subtraktion arbeiten und bei einigen Multiplikationen helfen.

Answer 6

Wenn Sie Ihre eigene arbiträre Präzisions-Bibliothek rollen wollen, siehe Knuths Seminumerical Algorithms, Band 2 seines Hauptwerkes.

Answer 7

Wenn ich meine eigene Sprache implementiere und beliebige Längenzahlen unterstützen möchte, verwende ich eine Zielsprache mit dem Carry/Borrow-Konzept.Aber da es keine HLL gibt, die dies ohne schwerwiegende Auswirkungen auf die Leistung (wie Ausnahmen) implementiert, werde ich es sicherlich in Assembly implementieren. Es wird wahrscheinlich einen einzigen Befehl (wie in JC in x86) benötigen, um auf einen Überlauf zu prüfen und ihn zu handhaben (wie in ADC in x86), was ein akzeptabler Kompromiss für eine Sprache ist, die eine beliebige Genauigkeit implementiert. Dann werde ich ein paar Funktionen in Assembly anstelle von regulären Operatoren verwenden, wenn Sie Überladung für eine elegantere Ausgabe verwenden können, noch besser. Ich erwarte aber nicht, dass generiertes C++ als Zielsprache gepflegt werden kann (oder soll).

Oder verwenden Sie einfach eine Bibliothek, die mehr Schnickschnack hat als Sie benötigen und verwenden Sie sie für alle Ihre Nummern.

Als hybriden Ansatz, erkennen Überlauf in Assembly und rufen Sie die Bibliothek-Funktion, wenn Überlauf, anstatt Ihre eigene Mini-Bibliothek zu rollen.