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)

[Reply To Message #81076]

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)

[Reply To Message #81077]
> [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.
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 #81078]
> [Reply To Message #81077]
> > [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",
please see here:
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)

[Reply To Message #81077]
> [Reply To Message #81076]
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

Re: Ackermann function (2018-04-14 01:24 by bspinoza #81087)

[Reply To Message #81086]
> [Reply To Message #81077]
> > [Reply To Message #81076]
> instead of using OPTION ARITHMETIC DECIMAL_HIGH use OPTION ARITHMETIC RATIONAL for arbitrary precision integers
Thank you Jack for this tip! Of course, this helped very much! I don't thought on this mode.
Répondre à #81086

Répondre à 81087×

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