Ackermann Funktion Berechnung mittels modulo |
13.12.2018, 16:23 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Ackermann Funktion Berechnung mittels modulo
So weit, so gut. Für ackermann(4, 2, 10**9 + 7) erhalte ich relativ zügig als Ergebnis 973586823. Mein Problem liegt jetzt speziell in der Geschwindigkeit. Ich weiß, dass sich die Berechnung für A(5, n) auch auf Tetration zurückführen lässt. Für ackermann(5, 2, 10**9 + 7) braucht das Programm allerdings schon über 26 Minuten - selbst mit PyPy. Wenn n größer als 2 ist dauert es entsprechend noch länger. Für ist der Ofen dann ganz aus. Deswegen meine Frage: Lässt sich die Berechnung für -auch für größere Moduli- durch einen Kniff merklich beschleunigen, ohne dass das Ergebnis erst Jahre nach meinem Ableben feststeht? Vielen Dank schon mal |
|||||||
13.12.2018, 17:09 | Steffen Bühler | Auf diesen Beitrag antworten » | |||||
RE: Ackermann Funktion Berechnung mittels modulo Ich bin nicht so der Python-Experte, aber hier findet sich eine Bemerkung, dass a**t0 im Vergleich zu pow(a,t0) deutlich schneller sein soll. Vielleicht ist es einen Versuch wert. Viele Grüße Steffen |
|||||||
13.12.2018, 17:37 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Voran Danke für das Editieren des Links Den Link zu SE hab ich mir angeschaut. Es scheint tatsächlich so zu sein, dass x**y schneller ist als pow(x, y). Ich habe in meinem Problem allerdings den Fall, dass ich beim Potenzieren riesige Zahlen erhalte (bspw. o. ä.) und dann erst den Divisionsrest berechne. Durch modulare Exponentiation geht das sicherlich schneller und frisst weniger Speicher. |
|||||||
13.12.2018, 17:44 | Steffen Bühler | Auf diesen Beitrag antworten » | |||||
Ich bin eben nicht sicher, ob modulare Exponentiation grundsätzlich schneller ist. Und Speicher dürfte wohl vorhanden sein. Ich hab mich zwar länger nicht mit Tetration beschäftigt, aber die sollte prinzipiell auch ohne modulo funktionieren. Das ist immerhin ein Rechenschritt mehr, den man sparen könnte, genauso wie übrigens auch die jedesmal aufgerufene if-Anweisung sowie die Zuweisung an die zweite Variable t1. Mag alles nicht viel Zyklen fressen, aber diese Routine wird bei m>4 so oft aufgerufen, dass ich darüber nachdenken würde. |
|||||||
13.12.2018, 19:23 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Ich habe zumindest mal das if aus der Funktion tetration() gestrichen. Das ergab für ackermann(5, 2, modulo) eine Steigerung von 25 Sekunden (unter PyPy). Sieht also schon mal gut aus allerdings braucht das Ergebnis immer noch knapp 26 Minuten.... Deswegen ist meine Frage, ob sich auf mathematischer Ebene evtl. was verändern ließe, was die eigentliche Berechnung vereinfacht oder verkompliziert, aber trotzdem wesentlich verkürzt. Aus den Artikeln bei Wikipedia und Mathworld konnte ich nichts entnehmen. |
|||||||
19.12.2018, 16:41 | Hosenschlange | Auf diesen Beitrag antworten » | |||||
Nach mehreren Anläufen und Hin-und-her habe ich leider nichts gefunden, was das ganze erheblich schneller werden lässt. Eine andere Frage, die dabei aufgekommen war, ist, ob ich evtl über die Inverse Ackermann-Funktion irgendwas erreichen kann. Ganz sicher bin ich mir dabei nicht, aber vielleicht hat sich von euch mal jemand damit beschäftigt. |
|||||||
Anzeige | |||||||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |