Results 1 to 1 of 1

Thread: Ackermann function

  1. #1
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152

    Ackermann function

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

    http://community.thinbasic.com/index...cseen#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.)


    Dan :P

    [code=thinbasic]'------------------------------------------------------------------
    '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

    '------------------------------------------------------------------
    [/code]
    Attached Files Attached Files
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Similar Threads

  1. Python 3 --> Ackermann Function
    By danbaron in forum Scripting
    Replies: 5
    Last Post: 17-06-2010, 22:48

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •