Ackermann function

[danbaron]

[font=courier new]Petr programmed the Ackermann function,

http://community.thinbasic.com/index.php?topic=3397.msg25290;topicseen#msg25290 .

He was showing different types of recursion.
I looked at his code (which is correct), and I couldn't understand what was going on.

So, I looked up the Ackermann function,

http://en.wikipedia.org/wiki/Ackermann_function .

It is famous.
It grows almost unbelievably fast.

ack(4, 2), has 19,729 digits.

I decided to try to program it without using recursion (without the function calling itself).
It seemed hard to do, because, when I looked at the recursive version, it appeared that if you removed the recursion, then
nothing would remain.

This script shows both versions.

(The script should take approximately one minute to run. It will tell you when it is done.)

:oops:
Dan :x :P


'------------------------------------------------------------------
'file = ackermann.tbasicc
'------------------------------------------------------------------

Uses "Console"

%stackincrement = 1000

Global stack(1) As Quad
Global sindex As DWord = 1

'------------------------------------------------------------------

Function TBMain()
Local m, n, a1, a2 As Quad
Local s, sm, sn, sa1, sa2 As String

Console_WriteLine(" ack1 ack2")
Console_WriteLine()

For m = 0 To 3
For n = 0 To 7

a1 = ack1(m, n)
a2 = ack2(m, n)

sm = Format$(m, "0")
sn = Format$(n, "0")
sa1 = Format$(a1, "0000")
sa2 = Format$(a2, "0000")
s = "ack(" & sm & ", " & sn & ") = " & sa1 & " " & sa2

Console_WriteLine(s)

Next
Next

'Do it once more (below), to get ack(4, 0).
'If you go any higher, ack1() will overflow the function stack, and ack2() will take forever.

m = 4
n = 0

a1 = ack1(m, n)
a2 = ack2(m, n)

sm = Format$(m, "0")
sn = Format$(n, "0")
sa1 = Format$(a1, "0000")
sa2 = Format$(a2, "0000")
s = "ack(" & sm & ", " & sn & ") = " & sa1 & " " & sa2

Console_WriteLine(s)

Console_WriteLine()
Console_WriteLine("Done.")
Console_WriteLine("Press a key.")

WaitKey

End Function

'------------------------------------------------------------------

Function ack1(m As Quad, n As Quad) As Quad
'Uses recursion.

If m < 0 Then Return -1
If n < 0 Then Return -1

If m = 0 Then Return n + 1
If n = 0 Then Return ack1(m - 1, 1)
Return ack1(m - 1, ack1(m, n - 1))

End Function

'------------------------------------------------------------------

Function ack2(m As Quad, n As Quad) As Quad
'No recursion.

If m < 0 Then Return -1
If n < 0 Then Return -1

Do

If m = 0 Then
If emptystack() Then
Return n + 1
Else
m = pop()
n += 1
Iterate Do
EndIf
EndIf

If n = 0 Then
m -= 1
n = 1
Iterate Do
EndIf

push(m - 1)
n -= 1

Loop
End Function

'------------------------------------------------------------------

Sub push(q As Quad)
If sindex > UBound(stack) Then
ReDim Preserve stack(sindex + %stackincrement)
End If
stack(sindex) = q
Incr sindex
End Sub

'------------------------------------------------------------------

Function pop() As Quad
Decr sindex
Return stack(sindex)
End Function

'------------------------------------------------------------------

Function emptystack() As Byte
If sindex = 1 Then Return TRUE
Return FALSE
End Function

'------------------------------------------------------------------