Umgang mit großen Zahlen in Haskell

Ich versuche, den Miller-Test in Haskell zu implementieren (nicht Miller-Rabin.) Ich habe mit großen Zahlen zu tun, und insbesondere muss ich große Zahlen potenzieren und den Modulus von a große Nummer mod eine andere große Zahl.Umgang mit großen Zahlen in Haskell

Gibt es dafür Standardfunktionen? Die normale expt-Funktion sagt mir, dass ich keinen Speicher mehr habe, bevor ein Ergebnis berechnet wird. Zum Beispiel würde ich gerne tun:

(mod (8888^38071670985) 9746347772161)

ich meine eigenen Algorithmen implementieren könnte, aber es wäre schön, wenn diese bereits vorhanden ist.

Quelle

2012-03-25 Josh Infiesto

http://stackoverflow.com/questions/1184296/why-can-haskell-handle-yy-large-numbers-easily ..., Ihr Exponent ist extrem groß ... aber .... –

NVM über meine eigene implementieren. Ich habe mir die Haskell-Implementierungen dieser Algorithmen angeschaut. Sie sind genau so, wie ich sie implementiert hätte. –

Wie ich schon sagte ... Ihr Exponent ist ..., extrem groß ... –

Im Paket arithmoi gibt es eine modulare Potenzierung (und vieles mehr).

Da ich es geschrieben habe, würde mich interessieren zu hören, wenn Sie es nützlich finden und was verbessert werden könnte.

Wenn Sie

(mod (8888^38071670985) 9746347772161)

zu berechnen versuchen, wie es steht, das Zwischenergebnis 8888^38071670985 würde etwa 5 * 10 Bits, etwa 60GB besetzen. Selbst wenn Sie so viel RAM haben, liegt das nahe (vielleicht etwas oberhalb) der Grenzen von GMP (das Größenfeld in den GMP-Ganzzahlen beträgt vier Bytes).

Also müssen Sie auch die Zwischenergebnisse während der Berechnung reduzieren. Das lässt nicht nur die Berechnung problemlos in den Speicher passen, sondern ist auch schneller, da die beteiligten Zahlen relativ klein bleiben.

Quelle

2012-03-25 21:05:54

Das hat hervorragend funktioniert. Ich hätte das von Anfang an tun sollen. Ich weiß nicht, warum ich das nicht getan habe. Ich habe den Algorithmus sowieso schon eine Weile angeguckt. Aus welchem Grund auch immer, ich habe versucht, das Expt und den Mod getrennt zu machen und es nicht zusammengefügt, um die Eigenschaften von Kongruenzen zu verwenden, um das Problem zu reduzieren. –

Eine Annäherung an Ihre Nummer vor Modulo Einnahme ist

10^log(8888^38071670985) 
= 10^(38071670985 * log(8888)) 
= 10^(1.5 * 10^11)

Mit anderen Worten: es etwa 1,5 * 10^11 Ziffern hat. Es würde um des Speichers nur benötigt, um darzustellen.

Beginnen Sie damit vielleicht nicht die beste Idee. Hat die Bibliothek , um die Berechnung mit diesen großen Zahlen zu unterstützen?

Quelle

2012-03-25 21:26:17 Irfy

Modulare Exponentiation erfordert nicht die "Nummer vor der Aufnahme Modulo" – user102008

Nizza arithmetischen Trick, dass. – Trismegistos

Umgang mit großen Zahlen in Haskell

Antwort

Verwandte Themen