XProfan

Deutsch

p.specht

Wilhelm Friedrich Ackermann (* 1896 in Schönebecke (Herscheid); † 1962 in Lüdenscheid) war ein deutscher Mathematiker, der mit seiner Funktion 1926 eine These seines Lehrers David Hilbert zu Fall brachte, derzufolge alle berechenbaren Funktionen auch rekursiv berechenbar seien. Ackermann's Funktion wurde 1955 von der Ungarin Rózsa Péter vereinfacht.

Für Benchmark-Timingzwecke wird üblicherweise A(3,6) herangezogen.

Kompilieren Markieren Separieren

' (D) Demoware, 2013-03 von C nach XProfan-11 by K. Orkenzieher
' Beweist auch, daß etwas Rekursion auch in XProfan funktioniert.
' Quelle (Orig.): https://www.xgc.com/benchmarks/ackermann_c.htm
' Updated May 11, 2005. Copyright (C-Version): XGC Software
' Begleittext des C-Vorbildes:
'   Ackermann's function "is an example of a recursive function which
'   is not primitive recursive". It is interesting from the point of
'   view of benchmarking because it "grows faster than any primitive
'   recursive function" and gives us a lot of nested function calls
'   for little effort.
'   It is defined as follows:
'   A(0, n) = n+1
'   A(m, 0) = A(m-1, 1)
'   A(m, n) = A(m-1, A(m, n-1))
'   We use A(3,6) as the benchmark. This used to take long enough to
'   confirm the execution time with a stopwatch. Nowadays that's out
'   of the question. The value of A(4,2) has 19729 digits!
'   A (3,6) gives us 172233 calls, with a nesting depth of 511.
'
var m&=3
var n&=6
Declare ans!,t1&,t2&
Windowtitle "Ackermann-Péter A("+str$(m&)+","+str$(n&)+")-Benchmark"
CLS
t1&=&gettickcount
ans! = A(m&,n&)
t2&=&gettickcount
print " Ergebnis: ";format$("%g",ans!)
case (m&=3) and (n&=6) and (ans!<>509) :print "Resultat ";ans!;" falsch,  509 muss rauskommen!"
case (m&=3) and (n&=7) and (ans!<>1021):print "Resultat ";ans!;" falsch, 1021 muss rauskommen!"
print format$(" Benchmark-Zeit = %g Sekunden",(t2&-t1&)/1000)
waitinput
End

proc A

    parameters m&,n&

    if m&=0

        return n&+1

    elseif n&=0

        return A(m&-1,1)

    else

        return A(m&-1,A(m&,n&-1))

    endif

endproc

P.S.: Mein Lappi (Zweikerner 1.86 GHz) liefert:
A(2,200)=403: Interpreter 7,305 sec, Compiler 1,264 sec;
A(3,6)=509: Interpreter 14.445 sec, Compiler 2.663 sec; nProc: 0.002 sec
A(3,7)=1021: Interpreter 61.976 sec, Compiler 11.123 sec; nProc: 0.015 sec
A(3,8)=2045: Interpreter 261.45 sec, Compiler 45.864 sec; nProc: 0.062 sec
A(3,9)=4093: Interpreter und Compiler brechen wegen zu hoher Rekursionstiefe ab; nProc: 0,265 sec
A(3,10)=8189: nP: 1,092 sec
A(3,11)=16381: nP: 4,212 sec
A(3,12)=32765: nP: 17,019 sec
A(3,13)=65533: nP: 67,47 sec
A(3,n)=2^(n+3)-3
A(4,1)=65533 : nP: 66,737 sec
A(4,2)=2^65536−3 ... nicht ermitelt

XProfan 11
Computer: Gerät, daß es in Mikrosekunden erlaubt, 50.000 Fehler zu machen, zB 'daß' statt 'das'...

09.05.2021 ▲

Vollständiges Zitat

Absatzweise zitieren Zeilenweise zitieren

p.specht

Ackermann-Funktion etwas flotter
-------------------------------------------
Da sie auf Long-Integers definiert ist, läuft das in XProfan-11 recht rasch in den Überlaufbereich (Kennzeichen: Die Zahlen werden negativ). Damit letzteres nicht so schnell passiert, hier eine Definition auf ganzzahllige Float-Variablen.
Vorsicht: Ackermann(4,2) führt selbst auf Supercomputern ins "Nirwana"...

Kompilieren Markieren Separieren

WindowTitle "Ackermann-Funktion, auf FLoats definiert"
'durch die ungar. Mathematikerin Roza Peters beschleunigte Version
set("decimals",0):CLS:declare i!,j!

whileloop 0,5:i!=&Loop

    whileloop 0,6:j!=&Loop

        print " ACKERMANN(";i!;",";j!;") = ";ACK(i!,j!)

    endwhile

endwhile

print "---"
waitinput
END

Proc ACK :parameters m!,n!:declare ans!

    if nearly(m!,0,5):ans!=n!+1

    elseif nearly(n!,0,5):ans!=ACK(m!-1,1)

        else :ans!=ACK(m!-1,ack(m!,n!-1))

    endif

    return ans!

endproc