+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://qb64phoenix.com/forum/forumdisplay.php?fid=3)
+---- Forum: Works in Progress (https://qb64phoenix.com/forum/forumdisplay.php?fid=9)
+---- Thread: Ackermann Function (/showthread.php?tid=617)
RE: Ackermann Function - James D Jarvis - 07-15-2022
(07-15-2022, 11:19 PM)Kernelpanic Wrote:(07-15-2022, 10:40 PM)James D Jarvis Wrote: 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 FunctionRE: Ackermann Function - Kernelpanic - 07-16-2022
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.
RE: Ackermann Function - James D Jarvis - 07-16-2022
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)
RE: Ackermann Function - bplus - 07-16-2022
I suspect this line here is the trouble maker:
ackermann = ackermann(m - 1, ackermann(m, n - 1))
RE: Ackermann Function - James D Jarvis - 07-16-2022
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
ReturnRE: Ackermann Function - bplus - 07-16-2022
Yeah I noticed the 4 levels skipped at RC by most the PL's attempting Akermann.
RE: Ackermann Function - Kernelpanic - 07-16-2022
Quote: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."
EndRE: Ackermann Function - Kernelpanic - 07-16-2022
(07-16-2022, 01:02 AM)bplus Wrote: 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.
RE: Ackermann Function - Jack - 07-16-2022
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 FunctionRE: Ackermann Function - Kernelpanic - 07-16-2022
Thanks for your trouble, but . . .
Is it the system? I have 16GB of RAM. But maybe I didn't get it either.
![[Image: Jack-Ackermann2022-07-17-004915.jpg]](https://i.ibb.co/qm7wQFx/Jack-Ackermann2022-07-17-004915.jpg)