Ackermann Funktion Berechnung mittels modulo

Neue Frage »

Hosenschlange Auf diesen Beitrag antworten »
Ackermann Funktion Berechnung mittels modulo
Bei http://programmingpraxis.com/2012/05/25/...n/#comment-8950 (Könnte ein Moderator den Link bitte korrigieren? Danke! Bitte. Steffen) bin ich auf eine Programmieraufgabe zur Ackermann-Funktion A(m, n) gestoßen. Die vielversprechendste Lösung war die unter o. g. Kommentar. Nun ist ja bekannt, dass die Ergebnisse für Werte gigantische Ausmaße annehmen. Ich will nun die Werte durch modulo-Operationen kleinhalten. Dazu hab ich, auch aus Geschwindigkeitsgründen, für n = 4 eine gesonderte Funktion "Tetration" eingefügt, um die entsprechende Stufe der Rekursion zu umgehen. In Python sieht das dann so aus:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
def tetration(a, b, mod):
    ''
    t0 = 1

    while b > 0:
        t1 = pow(a, t0, mod)
        if (t0 == t1):
            break
        t0 = t1
        b -= 1

    return t1

def hyper(n, a, b, mod):
    ''
    if n == 0:
        return (b + 1) % mod
    if n == 1:
        return (a + b) % mod
    if n == 2:
        return (a * b) % mod
    if n == 3:
        return pow(a, b, mod)
    if n == 4:
        return tetration(a, b, mod)

    if b == 0:
        return 1

    x = a
    for _ in range(b - 1):
        x = hyper(n-1, a, x, mod)

    return x % mod

def ackermann(m, n, mod):
    ''
    return hyper(m, 2, n + 3, mod) - (3 % mod)

if __name__ == "__main__":
    ''
    print (ackermann(4, 2, 10**9 + 7))


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 Freude
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
 
 
Hosenschlange Auf diesen Beitrag antworten »

Voran Danke für das Editieren des Links Freude

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.
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. Augenzwinkern

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.
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 Freude 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.
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »