BigInt für Standard ML/NJ

Question

Gibt es ein Java BigInt-Äquivalent für Standard ML? Der normale int-Typ löst bei Überlauf eine Ausnahme aus.

Answer 1

Ja, siehe die Struktur.

Answer 2

Das BigInt-Äquivalent heißt LargeInt. Siehe these lecture notes, um einige Funktionen zur Konvertierung zwischen int (aka Int) und LargeInt zu sehen.

Answer 3

Nun, Int setzt eine scheußliche Grenze für Dinge wie die Berechnung von Permutationen. SML benötigt einen großen numerischen Datentyp, der natürlicher zu verwenden ist.

Answer 4

Der offizielle SML'97 Standard basis library stellt einen Zoo von Strukturen wie Int, IntInf, Int32, Int64, LargeInt usw.

Um sich tatsächlich in der Praxis nutzen, um die Dinge funktionieren wie erwartet, und sie effizient funktionieren , müssen Sie sich die zur Verfügung stehende SML-Implementierung genau anschauen.

• Eine Familie von Implementierungen imitiert das Speicherlayout von C und Java, so Int32 wirklich ein 32-Bit-Maschine Wort sein wird (aber mit Überlaufprüfung) und Int64 ein 64-Bit-Maschine Wort. SML/NJ ist ein bemerkenswertes Beispiel dafür, und seine kleine Int-Arithmetik ist schnell, aber ihre große int-Arithmetik ist langsam.

• Eine andere Familie von Implementierungen stammt aus dem Hintergrund der symbolischen Berechnung (LISP oder Computer Algebra), wo Poly/ML ein bemerkenswertes Beispiel ist. Hier haben Sie standardmäßig Int = IntInf = LargeInt, und die Implementierung verwendet zuerst (teilweise) das native Maschinenwort als Approximation, bis es überläuft und dann zu wirklich großen Ganzzahlen wechselt, die auf dem Heap zugewiesen sind (als umrahmte Werte). Poly/ML verwendet die GNU MP-Bibliothek für diesen großen Teil.

So Int/IntInf ist sehr effizient, solange Ihre Anwendung zu ganzen Zahlen ist, nicht in der Maschine Worte einer bestimmten Größe: Int32 im symbolischen Modell wird nicht in ein einziges Wort auf 32-Bit-Hardware passen aufgrund der zusätzliche Tag-Bits, die benötigt werden. Einige Algorithmen, die sich tatsächlich mit der Wortarithmetik beschäftigen, werden sich verschlechtern, zum Beispiel SHA1 auf 32-Bit-Hardware. Das implizite Upgrade von "kürzen-als-Worte" int in Heap-allokierte große int gibt Ihnen etwas Besseres als BigInt in Java, weil Sie nicht den gesamten Objekt-Overhead für kleine Werte benötigen: 42 wird sei nur ein Bit-Muster in einem Register (mit zusätzlichem Tag-Bit), aber keine schwere Box auf dem Heap.

Answer 5

Obwohl dies nicht genau das ist, was Sie gefragt haben, möchten Sie eigentlich kein Äquivalent zur Java BigInt-Klasse. Javas BigInt-Klasse implementiert O (n^2) Zeit für die Multiplikation (im Wesentlichen Multiplikation der Art, wie es in der Grundschule gelehrt wird), anstelle von O (n log n), was möglich ist. Dies ist sehr wichtig, da eine Menge trivialer BigInt-Programmierung einfach nicht mit der n^2-Version funktioniert.