Wie gehen Programmiersprachen mit der Arithmetik großer Zahlen um?

Question

Bei einem Computer mit einem 64-Bit-Prozessor wäre die größte Zahl, die er verarbeiten kann, 2 64 \= 18,446,744,073,709,551,616. Wie gehen Programmiersprachen, z. B. Java oder C, C++, mit der Arithmetik von Zahlen um, die höher als dieser Wert sind? Jedes Register kann diese Zahlen nicht in einem einzigen Stück speichern. Wie wurde dieses Problem angegangen?

Answer 1

Es gibt viele spezielle Techniken für Berechnungen mit Zahlen, die größer als die Registergröße sind. Einige von ihnen werden in diesem Wikipedia-Artikel über Arithmetik mit beliebiger Genauigkeit

Sprachen mit niedrigem Niveau, wie C und C++, überlassen die Berechnung großer Zahlen der Bibliothek Ihrer Wahl. Eine bemerkenswerte Bibliothek ist die GNU Multi-Precision-Bibliothek . Hochsprachen wie Python und andere integrieren dies in den Kern der Sprache, so dass normale Zahlen und sehr große Zahlen für den Programmierer identisch sind.

Answer 2

Programmiersprachen, die wirklich große Zahlen verarbeiten, verwenden benutzerdefinierte Zahlenprimitive, die über die normalen, für 32-, 64- oder 128-Bit-CPUs optimierten Operationen hinausgehen. Diese Zahlen sind besonders nützlich für die Computersicherheit und die mathematische Forschung.

Le site GNU-Bibliothek für Mehrfachpräzision ist wahrscheinlich das vollständigste Beispiel für diese Ansätze.

Größere Zahlen können Sie mit Hilfe von Arrays verarbeiten. Probieren Sie dies in Ihrem Webbrowser aus. Geben Sie den folgenden Code in der JavaScript-Konsole Ihres Webbrowsers ein:

Der Punkt, an dem JavaScript versagt

console.log(9999999999999998 + 1)
// expected 9999999999999999
// actual  10000000000000000  oops!

JavaScript verarbeitet keine einfachen Ganzzahlen über 9999999999999998 . Aber es ist einfach genug, eine eigene primitive Zahl zu schreiben, damit diese Berechnung funktioniert. Hier ist ein Beispiel mit eine benutzerdefinierte Zahlenaddiererklasse in JavaScript .

Bestehen des Tests mit einer benutzerdefinierten Zahlenklasse

// Require a custom number primative class
const {Num} = require('./bases')

// Create a massive number that JavaScript will not add to (correctly)
const num = new Num(9999999999999998, 10)

// Add to the massive number
num.add(1)

// The result is correct (where plain JavaScript Math would fail)
console.log(num.val)  // 9999999999999999

Wie es funktioniert

Sie können den Code einsehen unter class Num { ... } um zu sehen, was im Einzelnen passiert, aber hier ist ein grundlegender Überblick über die Logik, die verwendet wird:

Klassen:

• Le site Num Klasse enthält ein Array von einzelnen Digit Klassen.
• Le site Digit Klasse enthält den Wert einer einzelnen Ziffer und die Logik zur Behandlung der Carry flag

Schritte:

1. Die gewählte Zahl wird in eine Zeichenkette umgewandelt
2. Jede Ziffer wird in eine Digit Klasse und gespeichert in der Num Klasse als Array von Ziffern
3. Wenn die Num inkrementiert wird, wird sie an die erste Digit im Array (die äußerste rechte Zahl)
4. Wenn die Digit Wert plus dem Carry flag sind gleich der Base , dann die nächste Digit auf der linken Seite wird aufgerufen, um inkrementiert zu werden, und die aktuelle Zahl wird zurückgesetzt auf 0
5. ... Wiederholen Sie den Vorgang bis zur äußersten linken Stelle des Feldes

Logistisch gesehen ist es dem, was auf der Maschinenebene geschieht, sehr ähnlich, aber hier ist es unbegrenzt. Sie können Lesen Sie mehr darüber, wie Ziffern sind hier Dies kann auf Zahlen mit beliebiger Basis angewendet werden.

Answer 3

Sie nehmen das Falsche an. Die größte Zahl, die es verarbeiten kann in einem einzigen Register ist eine 64-Bit-Zahl. Mit einigen geschickten Programmiertechniken könnte man jedoch einfach ein paar Dutzend dieser 64-Bit-Zahlen in einer Reihe kombinieren, um eine riesige 6400-Bit-Zahl zu erzeugen und diese für weitere Berechnungen zu verwenden. Das ist nur nicht so schnell, wie wenn die Zahl in ein Register passt.

Selbst die alten 8- und 16-Bit-Prozessoren nutzten diesen Trick, indem sie die Zahl einfach in andere Register überlaufen ließen. Das macht die Mathematik komplizierter, aber die Möglichkeiten sind damit nicht erschöpft.

Allerdings ist eine solch hochpräzise Mathematik äußerst ungewöhnlich. Selbst wenn man die gesamte Staatsverschuldung der USA berechnen und das Ergebnis in simbabwischen Dollar speichern wollte, wäre eine 64-Bit-Ganzzahl immer noch groß genug, denke ich. Sie ist aber definitiv groß genug, um den Betrag meines Sparkontos zu speichern.

Answer 4

Mehr oder weniger auf die gleiche Weise, wie Sie tun. In der Schule haben Sie einstellige Zahlen auswendig gelernt: Addition, Multiplikation, Subtraktion und Division. Dann hast du gelernt, wie man mehrstellige Aufgaben als eine Folge von einstelligen Aufgaben löst.

Wenn man wollte, könnte man zwei zwanzigstellige Zahlen miteinander multiplizieren, wenn man nur einen einfachen Algorithmus und das einstellige Einmaleins kennt.

Answer 5

Ada unterstützt dies sogar von Haus aus, allerdings nur für seine typlosen Konstanten ("named numbers"). Für tatsächliche Variablen müssen Sie sich ein Paket mit beliebiger Länge suchen. Siehe Ganzzahl beliebiger Länge in Ada