Posts: 660
Threads: 142
Joined: Apr 2022
Reputation:
58
(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 Function
Posts: 1,000
Threads: 50
Joined: May 2022
Reputation:
27
07-16-2022, 12:16 AM
(This post was last modified: 07-16-2022, 12:17 AM by 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.
Posts: 660
Threads: 142
Joined: Apr 2022
Reputation:
58
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)
Posts: 3,925
Threads: 175
Joined: Apr 2022
Reputation:
213
I suspect this line here is the trouble maker:
ackermann = ackermann(m - 1, ackermann(m, n - 1))
b = b + ...
Posts: 660
Threads: 142
Joined: Apr 2022
Reputation:
58
07-16-2022, 03:09 PM
(This post was last modified: 07-16-2022, 03:22 PM by 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
Posts: 3,925
Threads: 175
Joined: Apr 2022
Reputation:
213
Yeah I noticed the 4 levels skipped at RC by most the PL's attempting Akermann.
b = b + ...
Posts: 1,000
Threads: 50
Joined: May 2022
Reputation:
27
07-16-2022, 08:29 PM
(This post was last modified: 07-16-2022, 08:41 PM by Kernelpanic.)
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."
End
Posts: 1,000
Threads: 50
Joined: May 2022
Reputation:
27
(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.
Posts: 422
Threads: 27
Joined: Apr 2022
Reputation:
26
07-16-2022, 10:16 PM
(This post was last modified: 07-16-2022, 10:17 PM by 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
Posts: 1,000
Threads: 50
Joined: May 2022
Reputation:
27
Thanks for your trouble, but . . .
Is it the system? I have 16GB of RAM. But maybe I didn't get it either.
|