SML: Modul für große Integer-Darstellung

Question

Dies ist eine Hausaufgabenfrage. In SML gibt es eine Grenze für Integer-Größe, die Int.maxInt ist, also muss ich ein Paket entwerfen, das große Ganzzahlen darstellen kann und Operationen wie Addieren, Multiplizieren usw. ausführen kann. Jetzt ist die offensichtliche Wahl, sich in a aufzuteilen Liste oder Array, wo jedes Element eine ganze Zahl von akzeptabler Größe hat. Aber definieren, wenn eine Funktion annehmen,

IntToLargeInt(x, base) = (x mod base) :: IntToLargeInt(x div base , base) 

Nun, für ganze Zahlen kleiner als die maximalen Größe, ist es zu einer Reihe von anderer Basis in einer Liste zu konvertieren. Aber mit großen Ganzzahlen, bevor es sogar aufteilen kann, löst es eine Überlauf-Ausnahme aus. Also, irgendein Hinweis, wie man vom Funktionsargument direkt wie ein stdin-Stream oder etwas Ähnliches analysieren kann. Im Grunde alles, was mir hilft, die Funktion für große Ganzzahlen arbeiten zu lassen.

Sollte ich Typen wie IntInf zuerst speichern und dann zu einer anderen Basis konvertieren?

Oder vielleicht, wenn ich in die falsche Richtung gehe, wären einige Hinweise darüber, wo ich anfangen soll, gut.

Answer 1

Wenn Sie über die Effizienz besorgt sind, kann es sinnvoll sein, IntInf.fromString zu verwenden. Aber - wenn Sie sich wirklich Gedanken über die Effizienz machen würden, dann würden Sie einfach IntInf für alles verwenden und nicht versuchen, eine große Zahlenbibliothek selbst zu implementieren.

Eine naivere Methode besteht darin, eine Ziffernfolge in eine umgekehrte Ziffernliste zu zerlegen und diese Ziffernliste in eine Ihrer int-Listen umzuwandeln. Sie können dies tun, so schnell wie möglich:

1) Konvertieren einzelne Ziffern in LargeInts

2) Multiplizieren Sie Ihre LargeInts von 10

3) hinzufügen LargeInts

eine Vorstellung zu bekommen, wie dies eine Implementierung einer Funktion, die einen String in eine gewöhnliche ganze Zahl konvertiert funktionieren könnte, ist hier:

fun digitToInt d = Char.ord d - Char.ord #"0"; 

fun digitsToInt [] = 0 
| digitsToInt (d::ds) = digitToInt d + 10 * digitsToInt ds; 

Hinweis , dass die + und * in den oben genannten müssten durch Ihre benutzerdefinierten Funktionen ersetzt werden. Das oben Gesagte gilt für Ziffern, in denen die niedrigstwertige Ziffer an erster Stelle in der Liste steht. Dies ist leider das Gegenteil der Standardmethode, mit der Zahlen dargestellt werden. Wir können die eingebaute Funktion rev verwenden diese zu beheben:

val stringToInt = digitsToInt o rev o explode; 

(. Diese vollständig entspricht

fun stringToInt s = digitsToInt(rev(explode s)); 

aber etwas besser lesbar)

Zum Beispiel

- stringToInt "12345"; 
val it = 12345 : int 

Nicht sehr aufregend, aber Sie sollten in der Lage sein, diesen Ansatz zu ändern, um yo zu entsprechen Deine Situation.