Ackermann Function

[James D Jarvis]

Looks like you are getting a stack overflow due to the depth of the recursion.

Yes, but the overflow should not occur at A(4, 1).

The program crashes sometime after 70,609,342(but less than 70,899,999,999) recursive calls to the function. The result itself may well be within the limits of the data type but the number of recursive calls required to get there is extremely high according to the logic used.  

Here's how I found that number of recursive calls.

Code: (Select All)

'Ackermann Funktion - 15. Juli 2022
'Absturz schon bei 4, 1 = 65533 (?)

Option _Explicit

Declare Function ackermann(m as long, n as long) as long

Dim m, n As Long
Dim i, j As Long
Dim Shared c As Long
Dim Shared aa$, ask$

Print
Print "Ackermann Funktion - Geben Sie zwei Zahlen ein"
Print
Input "Zahl 1: ", m
Input "Zahl 2: ", n
Print

i = 0: j = 0
For i = 0 To m
    For j = 0 To n
        Print Using "Ackermann (#, #) = ####"; i, j, ackermann(i, j)
    Next j
Next i

End

Function ackermann (m As Long, n As Long)
    c = c + 1
    Print c
    aa$ = InKey$
    If aa$ <> "" Then
        Input "quit?"; ask$
        If ask$ = "y" Then End
    End If

    If m = 0 Then ackermann = n + 1

    If m > 0 And n = 0 Then
        ackermann = ackermann(m - 1, 1)
    End If
    If m > 0 And n > 0 Then
        ackermann = ackermann(m - 1, ackermann(m, n - 1))


    End If

End Function

[Kernelpanic]

Thanks for your help!

But why do one get the result 65533 in "C" at A(4,1) (not with myself), but here: Ackermann Funktion in C

I've had enough for today! It's 02:15 here. 

[James D Jarvis]

those aren't the same functions are they? (!x) means "NOT X" in raw logic doesn't it?

if (!n) return ackermann(m - 1, 1);

isn't

If m > 0 And n = 0 Then ackermann = ackermann(m - 1, 1)

[bplus]

I suspect this line here is the trouble maker:
ackermann = ackermann(m - 1, ackermann(m, n - 1))

[James D Jarvis]

The original program certainly runs into a stack overflow due to the use of the recursive function.

I was able to calculate a(4,1)  using the following code adapted from the basic256 version as that doesn't have recursive functions built in. I takes a couple minutes to calculate but it works. I have no idea if it can calculate A(4,2).

Code: (Select All)

Dim stack(50000000, 3) As _Integer64
Dim lev, m, n, a, b As _Integer64
Input "1st #"; a
Input "2nd #"; b
stack(0, 0) = a
stack(0, 1) = b
lev = 0

GoSub ackermann
Print "A("; stack(0, 0); ","; stack(0, 1); ") ="; stack(0, 2)
End

ackermann:
If stack(lev, 0) = 0 Then
    stack(lev, 2) = stack(lev, 1) + 1
    Return
End If
If stack(lev, 1) = 0 Then
    lev = lev + 1
    stack(lev, 0) = stack(lev - 1, 0) - 1
    stack(lev, 1) = 1
    GoSub ackermann
    stack(lev - 1, 2) = stack(lev, 2)
    lev = lev - 1
    Return
End If
lev = lev + 1
stack(lev, 0) = stack(lev - 1, 0)
stack(lev, 1) = stack(lev - 1, 1) - 1
GoSub ackermann
stack(lev, 0) = stack(lev - 1, 0) - 1
stack(lev, 1) = stack(lev, 2)
GoSub ackermann
stack(lev - 1, 2) = stack(lev, 2)
lev = lev - 1
Return

[bplus]

Yeah I noticed the 4 levels skipped at RC by most the PL's attempting Akermann.

[Kernelpanic]

The original program certainly runs into a stack overflow due to the use of the recursive function.

I was able to calculate a(4,1)  using the following code adapted from the basic256 version as that doesn't have recursive functions built in. I takes a couple minutes to calculate but it works. I have no idea if it can calculate A(4,2).

The program works great! I've tried adding a timer, but the damn thing do not want. I assume that has to do with "Gosub". - I tried it out for two hours. 

The stack overflow can't be true. Here's a page that computes A(4, 1) in no time. One would have to be able to see the source code for it.

Ackermann function

Code: (Select All)

'Ackermann Funktion von Basic256 angepasst James D. Jarvis
'Zeitmessung funktioniert nicht
'16. Juli 2022

Option _Explicit

Dim stack(50000000, 3) As _Integer64
Dim lev, a, b As _Integer64
Dim t_start As Single

Input "1st #"; a
Input "2nd #"; b

'Zeitmessung starten
t_start = Timer

stack(0, 0) = a
stack(0, 1) = b
lev = 0

GoSub ackermann
Print "A("; stack(0, 0); ","; stack(0, 1); ") ="; stack(0, 2)
End

ackermann:
If stack(lev, 0) = 0 Then
  stack(lev, 2) = stack(lev, 1) + 1
  Return
End If

If stack(lev, 1) = 0 Then
  lev = lev + 1
  stack(lev, 0) = stack(lev - 1, 0) - 1
  stack(lev, 1) = 1
  GoSub ackermann

  stack(lev - 1, 2) = stack(lev, 2)
  lev = lev - 1
  Return
End If

lev = lev + 1
stack(lev, 0) = stack(lev - 1, 0)
stack(lev, 1) = stack(lev - 1, 1) - 1
GoSub ackermann

stack(lev, 0) = stack(lev - 1, 0) - 1
stack(lev, 1) = stack(lev, 2)
GoSub ackermann

stack(lev - 1, 2) = stack(lev, 2)
lev = lev - 1
Return

't_ende = Timer

Print
Print Timer - t_start;
Print " Sekunden."

End

[Kernelpanic]

I suspect this line here is the trouble maker:
ackermann = ackermann(m - 1, ackermann(m, n - 1))

But that is the case in all programs that I have found. It works too, but it only causes trouble from A(4, 1). And that is not too big.

See the link above.

[Jack]

hello Kernelpanic
as others have stated, you run out of stack, but you can increase the stack size
open internal\c\makeline_win.txt
add: -Wl,--stack,10485760
your opening post needs a couple of small corrections

Code: (Select All)

'Ackermann Funktion - 15. Juli 2022
'Absturz schon bei 4, 1 = 65533 (?)

Option _Explicit

Declare Function ackermann(m as Integer, n as Integer) as Long

Dim m, n As Long
Dim i, j As Integer

Print
Print "Ackermann Funktion - Geben Sie zwei Zahlen ein"
Print
Input "Zahl 1: ", m
Input "Zahl 2: ", n
Print

i = 0: j = 0
For i = 0 To m
    For j = 0 To n
        Print Using "Ackermann (#, #) = ######"; i, j, ackermann(i, j)
    Next j
Next i

End

Function ackermann (m As _Unsigned Integer, n As _Unsigned Integer)
    If m = 0 Then ackermann = n + 1

    If m > 0 And n = 0 Then
        ackermann = ackermann(m - 1, 1)
    End If
    If m > 0 And n > 0 Then
        ackermann = ackermann(m - 1, ackermann(m, n - 1))
    End If

End Function

[Kernelpanic]

Thanks for your trouble, but . . .

Is it the system? I have 16GB of RAM. But maybe I didn't get it either.