Ackermann-exponent

Ik heb nog een blauwe maandag gewerkt bij Bureau Micro Software in Delft, dan na mijn vertrek de naam aannam van zijn enige product: Grote Beer Software.
Een van mijn collega's schreef de volgende formules op het whiteboard. (Ter zijde: het kan iets afwijken; op het web vind ik kleine variaties):

• Regel A: G(1,k,j)=k*j
• Regel B: G(n+1,1,j)=j
• Regel C: G(n+1,k+1,j)=G(n,G(n+1,k,j),j)

Volgens de collega was dit de functie van Ackermann. Later las ik Ackermann-exponent, en dat vind ik wel zo'n aardige naam.

Op het whiteboard stond nog een vraag: wat is G(10,10,10) ?
Met de kennis van nu denk ik: grapjas. Deze functie neemt extreem snel toe, tot 10 kom je nooit:

• G(1,1,1) = 1
• G(2,2,2) = 4
• G(3,3,3) = 7625597484987
• G(3,3,4) = 1.3407807929942597e+154
• G(4,3,3) en G(3,4,3) kunnen niet worden berekend door mijn computer

Het blijkt dat een groeiende n de waarde flink opvoert:

• G(1,k,j) = k*j (inderdaad, de definitie)
• G(2,k,j) = j^k
• G(3,k,j) = j^^k
  Dit is mijn notatie voor tetratie, oftewel herhaald machtsverheffen: j^^2 = j^j, j^^3=j^j^j, j^^4=j^j^j^j, etc.
  G(3,2,j) = j^j geeft nog redelijke resultaten, maar G(3,3,j) vliegt al gauw uit de bocht; hoger dan j=4 kan mijn computer niet aan.
  • Gevonden in 573 stappen: G(3,2,143) = 1.6332525972973923e+308
  • Gevonden in 577 stappen: G(3,2,144) = Infinity met daarbinnen:
      G(1,3.072372558895053e+306,144) = Infinity
  Microsoft meldt dat ze gebruik maken van de IEEE Floating-Point Representation. Het drijvende komma getal met dubbele precisie heeft een tekenbit, een 11-bit exponent en een 52-bit significand of mantisse. Omdat de exponent zelf ook een tekenbit heeft, is de grootste waarde van het getal gelijk aan 2^(2^10 - 1) = 2^1023 = 10^308 (bij benadering).

In het onderstaande wordt G(n,k,j) niet alleen uitgerekend, maar worden ook alle tussenstappen getoond. In de tabel hieronder zie je 4 kolommen:

Stap	Dit is een volgnummer, die wordt gebruikt om (1) aan te geven hoeven stappen nodig zijn en (2) om bij berekening volgens methode C in de kolom "Verwijzing" te plaatsen
Niveau	De begin- en eindstap hebben niveau 0. Alle tussenliggende stappen hebben een niveau groter dan 0. Dit wordt verderop uitgelegd.
Formule	De onderhanden formule.
Verklaring	Zie verderop.

Als in de onderstaande invoervelden getal n of k gelijk zijn aan 1, dan ben je 1 stap klaar: dit is regel A of B.
In de praktijk zal je echter beginnen met regel C. Na een serie tussenstappen wordt dit opgelost door regels A of B, waarna het niveau met 1 wordt verlaagd.

In geval van regel C, is het aantal tussenstappen afhankelijk van n, k en j, maar er zijn wel vastliggende begin- en eindstappen, die worden vermeld in onderstaande grafiek. (NOOT: de variablen x, y, z, a, p, q, n, k en j hebben in de praktijk een waarde.)

Uitleg	Stap	Niveau	Formule	Verklaring
Nu worden 2 niveaus aangemaakt. Niveau a+1 wordt pas later zichtbaar. Het bevat G(n,G(n+1,k,j),j)	x	a	G(n+1,k+1,j) = G(n,G(n+1,k,j),j)	Regel C
Op niveau a+2 wordt de binnenste formule uitgewerkt	x+1	a+2	G(n+1,k,j) = ???	Regel A, B of C
Onbekend aantal tussenregels	...	...	...	...
Deze is opgelost Merk op dat y=x+1 voor regel A of B	y	a+2	G(n+1,k,j) = p	hangt af van Regel A, B of C
Nu kunnen we een niveau terug	y+1	a+1	G(n,G(n+1,k,j),j) = G(n,p,j)	stap y invullen in rechterterm van stap x
We kunnen uitwerken	y+2	a+1	G(n,p,j) = ???	Regel A, B of C
Onbekend aantal tussenregels	...	...	...	...
Ook deze is opgelost Merk op dat z=y+2 voor regel A of B	z	a+1	G(n,p,j) = q	hangt af van Regel A, B of C
Het eindantwoord:	z+1	a	G(n+1,k+1,j) = G(n,G(n+1,k,j),j) = G(n,p,j) = q	combineer stappen x, y+1 en z

Veel Ackermann-plezier. Voor de duidelijkheid nogmaals de formules:

Regel A:	G(1,k,j)=k*j
Regel B:	G(n+1,1,j)=j
Regel C:	G(n+1,k+1,j)=G(n,G(n+1,k,j),j)

getal n
getal k
getal j

HALLO, DAAR ZIJN WE WEER