Albedo
Joined 24 August 2022
languages added
m (→Binary Digits: example output added) |
(languages added) |
||
| (4 intermediate revisions by the same user not shown) | |||
Line 1:
{{mylangbegin}}
{{mylang|Piet|
{{mylang|Julia|
{{mylang|Cardinal|
{{mylang|DUP|Intermediate}}
{{mylang|FALSE|Intermediate}}
{{mylang|Beeswax|Creator}}
{{mylang|Glee|Beginner}}
{{mylang|Q'Nial|Beginner}}
{{mylangend}}
Line 380 ⟶ 385:
|}
Program flow (see explanation of the shorthand codes at the top of the page), with labels:
l1 l3
↓ ↓
1X2X-nn2X1X@=1X=->!#2X1X@=1X=-
. l2→? >
. 2 !
................X1-X1?#
. X l4↑2←l5
. 1 X
. X 1
. @ X
. = @
. 1 =
. ~ X 3
. N = X
. + - 1
. X 2 X
. 1 X @
. l6→? 1 1
.+X1@X1X2#>@X X
. l7↑ -
...............-X1@X1X3
Explanation with stack for the Ackermann Function(2,0):
(for the meaning of the square brackets, please read below)
[A] [B]
1 1
1 1 1 0 1 1 1 0
2 2 2 2 2 2 1 0 2 2 0 0 0 0 0 1
0 0 0 [2] 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 1 [1]
2 2 2 2 2 [0] 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 1 [1]
1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
———————————————————————————————————————————————————————————————————————————————————————
1X2X - n n 2X 1X @ = 1X = - > ! # 2X 1X @ = 1X = - > ! # ? 1X - 1X
↑ ↑ ↑
l1 l3 l4
---------------------------------------------------------------------------------------
explanation: correct order m>0? yes n>0? no A(m-1,1)
of m,n
[B] [C]
1 1 1 1
1 1 1 0 1 1 1 0 1 3 3 1 3 3 1
2 2 1 1 1 1 1 0 2 2 1 1 1 1 1 0 2 2 1 1 1 1 1 0 0 0 1 1 [0]
1 1 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 [1]
1 1 [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 [0]
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
——————————————————————————————————————————————————————————————————————————————————————————————————————
2X 1X @ = 1X = - > ! # 2X 1X @ = 1X = - > ! # 2X 1X @ = 3X 1X @ 1X - 3X 1X @ 1X -
↑ ↑ ↑
l1 l3 l5
-------------------------------------------------------------------------------------------------------
correct order m>0? yes n>0? yes A(m-1,A(m,n-1))
of m,n
[D]
1 1 1
1 1 1 0 1 1 1 0 1 1 0
2 2 1 1 1 1 1 0 2 2 0 0 0 0 0 1 2 2 0 0 0 0 0 1
0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 [1] 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 [0] 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [0] 0 0 0 0 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
—————————————————————————————————————————————————————————————————————————————————————————————————————
2X 1X @ = 1X = - > ! # 2X 1X @ = 1X = - > ! # ? 1X - 1X 2X 1X @ = 1X = - > ! #
↑ ↑ ↑ ↑
l1 l3 l4 l1
-----------------------------------------------------------------------------------------------------
correct order m>0? yes n>0? no A(m-1,1) correct order m>0?
of m,n for inner inner for inner f.
function function
1
1 2 2 1
1 1 1 0 0 0 0 1 1 1 1 0
2 2 0 0 0 0 0 0 0 0 2 2 1 2 2 0 0 0 0 0 1
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 2 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 2 2 2 2 2 2 2 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
———————————————————————————————————————————————————————————————————————————————————
? 2X 1X @ = 1X = - 2X 1X @ > # 2X 1X @ 1X + 2X 1X @ = 1X = - > ! #
↑ ↑ ↑
l2 l7 l1
output 3
—————————————————————————————————————————————————————
1
1 2 2
1 1 1 0 0 0 -1
2 2 -1 -1 -1 -1 -1 -1 0 1
2 2 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1
-1 -1 -1 2 2 2 2 2 2 2 2 2 2 2 2 3
—————————————————————————————————————————————————————
? 2X 1X @ = 1X = - 2X 1X @ > # ? 1X + N ~
↑ ↑
l2 l6
Which leads to the result Ackermann(2,0) = 3
What the program actually does is working through the whole steps of calculating the A(m,n) functions, according to:
A(2,0) = A(1,1) ,A(m,n)= A(m-1,1) if m>0 and n=0
A(1,1) = A(0,A(1,0)) ,A(m,n)= A(m-1,A(m,n-1)) if m>0 and n>0
A(0,A(1,0)) = A(0,A(0,1)) ,A(m,n)= A(m,n-1) if m>1 and n=0, for the inner function
A(0,A(0,1)) = A(0,2) ,A(m,n)= n+1 if m=0, for the inner function
A(0,2) = 3 ,A(m,n)= n+1 if m=0
The coefficients and the results can be found on the stack. See the places marked with square brackets [] and Labels in the program/stack flow above.
At each turn, the upper two values on the stack are flipped, so they are in the proper order for computing inner functions. For highly nested A(...,(A(A(A(...))))) functions the stack can grow to enormous proportions very fast, then computing its way outwards again, from innermost functions outwards. The innermost coefficients are always on top of the stack.
Checks for the appropriate substitute function and branching structures take the largest part of the program.
==Binary Digits==
| |||