### Forums: Forum of Decimal BASIC (Thread #39420)

#### Ackermann function (2018-04-12 22:48 by bspinoza #81076)

Playing a little with the Ackermann function:

'===============================================
' The Ackermann Function
' ~~~~~~~~~~~~~~~~~~~~~~
' Function named after Wilhelm Ackermann (1926):
' ack(a,b,0) = a+b
' ack(a,0,n+1) = psi(a,n)
' ack(a,b+1,n+1) = ack(a,ack(a,b,n+1),n)
' R¢zsa P‚ter defined 1955 a simple two-argument Version,
' the Ackermann-P‚ter function:
' a(0,n) = n+1
' a(m+1,0) = a(m,1)
' a(m+1,n+1) = a(m,a(m+1,n))
' ~~~~~~~~~~~~~~~~~~~~~~
OPTION ARITHMETIC DECIMAL_HIGH
OPTION BASE 1
PRINT " Function Ackermann (M, N) :"
INPUT PROMPT "M": x
INPUT PROMPT "N": y
FOR I = 1 TO x ! This is M
FOR J = 1 TO y ! This is N
PRINT "Ackermann(" & STR\$(I) & "," & STR\$(J) & ")="; ackermann(I, J)
NEXT J
NEXT I
function ackermann(m, n)
if (m = 0) then
LET ackermann = (n + 1)
elseif (n = 0) then
LET ackermann = ackermann((m - 1), 1)
else
LET ackermann = ackermann((m - 1), ackermann(m, (n - 1)))
END if
end function
END
'===============================================
My program calculates until Ackermann (3,9).
Ackermann (3,10) doesn't work and also Ackermann(4,1)!
Is there a possibillity to improve this ?

#### Répondre à 81076×

You can not use Wiki syntax
Vous n'êtes pas connecté. Pour distinguer vos messages en provenance du reste, vous devez choisir un surnom. (L'unicité du surnom est pas réservé. Il est possible que quelqu'un d'autre pourrait utiliser exactement le même surnom. Si vous voulez l'assurance de votre identité, nous vous recommandons de vous connecter avant de poster.) Connexion

#### Re: Ackermann function (2018-04-13 04:00 by bspinoza #81077)

Found an improvement by myself:

! ===============================================
! The Ackermann Function
! ~~~~~~~~~~~~~~~~~~~~~~
! Function named after Wilhelm Ackermann (1926):
! ack(a,b,0) = a+b
! ack(a,0,n+1) = psi(a,n)
! ack(a,b+1,n+1) = ack(a,ack(a,b,n+1),n)
! Rózsa Péter defined 1955 a simple two-argument Version,
! the Ackermann-Péter function:
! a(0,n) = n+1
! a(m+1,0) = a(m,1)
! a(m+1,n+1) = a(m,a(m+1,n))
! ~~~~~~~~~~~~~~~~~~~~~~
OPTION ARITHMETIC DECIMAL_HIGH
OPTION BASE 1
PRINT " Function Ackermann (M, N) :"
INPUT PROMPT "M": x
INPUT PROMPT "N": y
FOR I = 1 TO x ! This is M
FOR J = 1 TO y ! This is N
PRINT "Ackermann(" & STR\$(I) & "," & STR\$(J) & ")="; ackermann(I, J)
NEXT J
NEXT I
function ackermann(m, n)
IF M = 0 THEN
LET ackermann = n+1
ELSEIF M = 1 THEN
LET ackermann = n+2
ELSEIF M=2 THEN
LET ackermann = 2*n+3
ELSEIF M=3 THEN
LET ackermann = 8 * 2^n - 3
ELSEIF N=0 THEN
LET ackermann = ackermann (m-1,1)
ELSE
LET ackermann = ackermann (m-1,ackermann (m,n-1))
END IF
END FUNCTION
END
Répondre à #81076

#### Répondre à 81077×

You can not use Wiki syntax
Vous n'êtes pas connecté. Pour distinguer vos messages en provenance du reste, vous devez choisir un surnom. (L'unicité du surnom est pas réservé. Il est possible que quelqu'un d'autre pourrait utiliser exactement le même surnom. Si vous voulez l'assurance de votre identité, nous vous recommandons de vous connecter avant de poster.) Connexion

#### Re: Ackermann function (2018-04-13 04:26 by toml12953 #81078)

>
> Found an improvement by myself:

How does it improve on the original? Is it faster? I'm always interested in benchmarking programming techniques.
Répondre à #81077

#### Répondre à 81078×

You can not use Wiki syntax
Vous n'êtes pas connecté. Pour distinguer vos messages en provenance du reste, vous devez choisir un surnom. (L'unicité du surnom est pas réservé. Il est possible que quelqu'un d'autre pourrait utiliser exactement le même surnom. Si vous voulez l'assurance de votre identité, nous vous recommandons de vous connecter avant de poster.) Connexion

#### Re: Ackermann function (2018-04-13 12:40 by bspinoza #81082)

> > [Reply To Message #81076]
> >
> > Found an improvement by myself:
>
> How does it improve on the original? Is it faster? I'm always interested in benchmarking programming techniques.

I found this in the "Rosetta Code",
https://rosettacode.org/wiki/Ackermann_function
Répondre à #81078

#### Répondre à 81082×

You can not use Wiki syntax
Vous n'êtes pas connecté. Pour distinguer vos messages en provenance du reste, vous devez choisir un surnom. (L'unicité du surnom est pas réservé. Il est possible que quelqu'un d'autre pourrait utiliser exactement le même surnom. Si vous voulez l'assurance de votre identité, nous vous recommandons de vous connecter avant de poster.) Connexion

#### Re: Ackermann function (2018-04-14 00:37 by jack #81086)

instead of using OPTION ARITHMETIC DECIMAL_HIGH use OPTION ARITHMETIC RATIONAL for arbitrary precision integers
Répondre à #81077

#### Répondre à 81086×

You can not use Wiki syntax
Vous n'êtes pas connecté. Pour distinguer vos messages en provenance du reste, vous devez choisir un surnom. (L'unicité du surnom est pas réservé. Il est possible que quelqu'un d'autre pourrait utiliser exactement le même surnom. Si vous voulez l'assurance de votre identité, nous vous recommandons de vous connecter avant de poster.) Connexion