Ackermann function: Difference between revisions

{{trans|Python}}

R I m == 0 {(n + 1)

} E I m == 1 {(n + 2)

print(ack2(0, 0))

print(ack2(3, 4))

{{out}}

The OS/360 linkage is a bit tricky with the S/360 basic instruction set.

To simplify, the program is recursive not reentrant.

&LAB XDECO &REG,&TARGET

.*-----------------------------------------------------------------*

STACKLEN EQU *-STACK

YREGS

{{out}}

<pre style="height:20ex">

This implementation is based on the code shown in the computerphile episode in the youtube link at the top of this page (time index 5:00).

; Ackermann function for Motorola 68000 under AmigaOs 2+ by Thorham

;

outString

=={{header|8080 Assembly}}==

and <code>n ∊ [0,9)</code>, on a real 8080 this takes a little over two minutes.

jmp demo

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

db '*****' ; Placeholder for number

pnum: db 9,'$'

{{out}}

This code does 16-bit math just like the 8080 version.

bits 16

org 100h

db '*****' ; Placeholder for ASCII number

pnum: db 9,'$'

{{out}}

=={{header|8th}}==

\ Ackermann function, illustrating use of "memoization".

4 1 ackOf

{{out|The output}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}

/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */

/* program ackermann64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{Output}}

<pre>

=={{header|ABAP}}==

REPORT zhuberv_ackermann.

lv_result = zcl_ackermann=>ackermann( m = pa_m n = pa_n ).

WRITE: / lv_result.

=={{header|Action!}}==

Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.

CARD ARRAY stack(MAXSIZE)

CARD stacksize=[0]

OD

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Ackermann_function.png Screenshot from Atari 8-bit computer]

=={{header|ActionScript}}==

{

if (m == 0)

return ackermann(m - 1, ackermann(m, n - 1));

=={{header|Ada}}==

procedure Test_Ackermann is

New_Line;

end loop;

The implementation does not care about arbitrary precision numbers because the Ackermann function does not only grow, but also slow quickly, when computed recursively.

{{out}} the first 4x7 Ackermann's numbers:

{{works with|Agda|2.5.2}}

{{libheader|agda-stdlib v0.13}}

open import Data.Nat

open import Data.Nat.Show

main = run (putStrLn (show (ack 3 9)))

Note the unicode ℕ characters, they can be input in emacs agda mode using "\bN". Running in bash:

agda --compile Ackermann.agda

./Ackermann

{{out}}

=={{header|ALGOL 60}}==

{{works with|A60}}

integer procedure ackermann(m,n);value m,n;integer m,n;

ackermann:=if m=0 then n+1

outstring(1,"\n")

end

{{out}}

<pre>

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

BEGIN

PROC ackermann = (INT m, n)INT:

OD

END # test ackermann #;

{{out}}

<pre>

=={{header|ALGOL W}}==

{{Trans|ALGOL 60}}

integer procedure ackermann( integer value m,n ) ;

if m=0 then n+1

for n := 1 until 6 do writeon( ackermann( m, n ) );

end for_m

{{out}}

<pre>

=={{header|APL}}==

{{works with|Dyalog APL}}

0=1⊃⍵:1+2⊃⍵

0=2⊃⍵:∇(¯1+1⊃⍵)1

∇(¯1+1⊃⍵),∇(1⊃⍵),¯1+2⊃⍵

=={{header|AppleScript}}==

if m is equal to 0 then return n + 1

if n is equal to 0 then return ackermann(m - 1, 1)

return ackermann(m - 1, ackermann(m, n - 1))

=={{header|Argile}}==

{{works with|Argile|1.0.0}}

for each (val nat n) from 0 to 6

return (n+1) if m == 0

return (A (m - 1) 1) if n == 0

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}

/* ARM assembly Raspberry PI or android 32 bits */

/* program ackermann.s */

/***************************************************/

.include "../affichage.inc"

{{Output}}

<pre>

=={{header|Arturo}}==

(m=0)? -> n+1 [

(n=0)? -> ackermann m-1 1

print ["ackermann" a b "=>" ackermann a b]

]

{{out}}

=={{header|ATS}}==

{m,n:nat} .<m,n>.

(m: int m, n: int n): Nat =

| (_, 0) =>> ackermann (m-1, 1)

| (_, _) =>> ackermann (m-1, ackermann (m, n-1))

=={{header|AutoHotkey}}==

If (m > 0) && (n = 0)

Return A(m-1,1)

; Example:

=={{header|AutoIt}}==

=== Classical version ===

If ($m = 0) Then

Return $n+1

EndIf

EndIf

=== Classical + cache implementation ===

This version works way faster than the classical one: Ackermann(3, 5) runs in 12,7 ms, while the classical version takes 402,2 ms.

Func Ackermann($m, $n)

If ($ackermann[$m][$n] <> 0) Then

Return $return

EndIf

=={{header|AWK}}==

{

if ( m == 0 ) {

}

}

=={{header|Babel}}==

{((0 0) (0 1) (0 2)

(0 3) (0 4) (1 0)

zero?!: { 0 = }

{{out}}

<pre>

=={{header|BASIC}}==

==={{header|Applesoft BASIC}}===

110 FOR M = 0 TO 3

120 FOR N = 0 TO 4

250 M = M(SP) : N = N(SP) : IF SP = 0 THEN RETURN

260 FOR SP = SP - 1 TO 0 STEP -1 : IF R%(SP) THEN M = M(SP) : N = N(SP) : NEXT SP : SP = 0 : RETURN

==={{header|BASIC256}}===

stack[0,0] = 3 # M

stack[0,1] = 7 # N

stack[lev-1,2] = stack[lev,2]

lev = lev-1

{{out}}

<pre>

</pre>

for m = 0 to 3

for n = 0 to 4

endif

end if

{{out}}

==={{header|BBC BASIC}}===

END

IF M% = 0 THEN = N% + 1

IF N% = 0 THEN = FNackermann(M% - 1, 1)

==={{header|QuickBasic}}===

BASIC runs out of stack space very quickly.

The call <tt>ack(3, 4)</tt> gives a stack error.

FUNCTION ack (m!, n!)

ack = ack(m - 1, ack(m, n - 1))

END IF

=={{header|Batch File}}==

Had trouble with this, so called in the gurus at [http://stackoverflow.com/questions/2680668/what-is-wrong-with-this-recursive-windows-cmd-script-it-wont-do-ackermann-prope StackOverflow]. Thanks to Patrick Cuff for pointing out where I was going wrong.

@echo off

set depth=0

set t=%errorlevel%

set /a depth-=1

Because of the <code>exit</code> statements, running this bare closes one's shell, so this test routine handles the calling of Ackermann.cmd

@echo off

cmd/c ackermann.cmd %1 %2

A few test runs:

<pre>D:\Documents and Settings\Bruce>ack 0 4

{{works with|OpenBSD bc}}

{{Works with|GNU bc}}

if ( m == 0 ) return (n+1);

if ( n == 0 ) return (ack(m-1, 1));

}

}

=={{header|BCPL}}==

LET ack(m, n) = m=0 -> n+1,

writef("ack(%n, %n) = %n*n", m, n, ack(m,n))

RESULTIS 0

=={{header|beeswax}}==

Iterative slow version:

>M?f@h@gMf@h3yzp if m>0 and n>0 => replace m,n with m-1,m,n-1

>@h@g'b?1f@h@gM?f@hzp if m>0 and n=0 => replace m,n with m-1,1

>I;

b < <

A functional and recursive realization of the version above. Functions are realized by direct calls of functions via jumps (instruction <code>J</code>) to the entry points of two distinct functions:

Each block of <code>1FJ</code> or <code>1fFJ</code> in the code is a call of the Ackermann function itself.

xI; x@g'p??@Mf1fFJ if m>0 and n=0 => run Ackermann (m-1,1)

xM@~gM??f~f@f1FJ if m>0 and n>0 => run Ackermann(m,Ackermann(m-1,n-1))

Highly optimized and fast version, returns A(4,1)/A(5,0) almost instantaneously:

>Mf@Ph?@g@2h@Mf@Php if m>4 and n>0 => replace m,n with m-1,m,n-1

>~4~L#1~2hg'd?1f@hgM?f2h p if m>4 and n=0 => replace m,n with m-1,1

z b < < <

d <

Higher values than A(4,1)/(5,0) lead to UInt64 wraparound, support for numbers bigger than 2^64-1 is not implemented in these solutions.

{{trans|ERRE}}

Since Befunge-93 doesn't have recursive capabilities we need to use an iterative algorithm.

@v:\<vp0 0:-1<\+<

^>00p>:#^_$1+\:#^_$.

===Befunge-98===

{{works with|CCBI|2.1}}

>v

j

^ v:\_$1+

\^v_$1\1-

The program reads two integers (first m, then n) from command line, idles around funge space, then outputs the result of the Ackerman function.

Since the latter is calculated truly recursively, the execution time becomes unwieldy for most m>3.

=={{header|BQN}}==

A 0‿n: n+1;

A m‿0: A (m-1)‿1;

A m‿n: A (m-1)‿(A m‿(n-1))

Example usage:

<lang> A 0‿3

11

A 3‿4

=={{header|Bracmat}}==

The value of A(4,1) cannot be computed due to stack overflow.

It can compute A(3,9) (4093), but probably not A(3,10)

= m n

. !arg:(?m,?n)

| Ack$(!m+-1,Ack$(!m,!n+-1))

)

The second version is a purely non-recursive solution that easily can compute A(4,1).

The program uses a stack for Ackermann function calls that are to be evaluated, but that cannot be computed given the currently known function values - the "known unknowns".

Although all known values are stored in the hash table, the converse is not true: an element in the hash table is either a "known known" or an "unknown unknown" associated with an "known unknown".

= m n value key eq chain

, find insert future stack va val

& !value

)

{{out|Some results}}

<pre>

</pre>

The last solution is a recursive solution that employs some extra formulas, inspired by the Common Lisp solution further down.

= m n

. !arg:(?m,?n)

| AckFormula$(!m+-1,AckFormula$(!m,!n+-1))

)

{{Out|Some results}}

<pre>AckFormula$(4,1):65533

=={{header|Brat}}==

when { m == 0 } { n + 1 }

{ m > 0 && n == 0 } { ackermann(m - 1, 1) }

}

=={{header|C}}==

Straightforward implementation per Ackermann definition:

int ackermann(int m, int n)

return 0;

{{out}}

<pre>A(0, 0) = 1

A(4, 1) = 65533</pre>

Ackermann function makes <i>a lot</i> of recursive calls, so the above program is a bit naive. We need to be slightly less naive, by doing some simple caching:

#include <stdlib.h>

#include <string.h>

return 0;

{{out}}

<pre>A(0, 0) = 1

A couple of alternative approaches...

#include <conio.h>

//getch();

return 0;

A couple of more iterative techniques...

#include <conio.h>

//getch();

return 0;

A few further tweaks/optimizations may be possible.

===Basic Version===

class Program

{

}

}

{{out}}

<pre>

===Efficient Version===

using System;

using System.Numerics;

}

}

Possibly the most efficient implementation of Ackermann in C#. It successfully runs Ack(4,2) when executed in Visual Studio. Don't forget to add a reference to System.Numerics.

===Basic version===

unsigned int ackermann(unsigned int m, unsigned int n) {

}

}

===Efficient version===

C++11 with boost's big integer type. Compile with:

g++ -std=c++11 -I /path/to/boost ackermann.cpp.

#include <sstream>

#include <string>

<< text.substr(0, 80) << "\n...\n"

<< text.substr(text.length() - 80) << "\n";

<pre>

<pre>

=={{header|Chapel}}==

if m == 0 then

return n + 1;

else

return A(m - 1, A(m, n - 1));

=={{header|Clay}}==

if(m == 0)

return n + 1;

return ackermann(m - 1, ackermann(m, n - 1));

=={{header|CLIPS}}==

'''Functional solution'''

(?m ?n)

(if (= 0 ?m)

)

)

{{out|Example usage}}

<pre>CLIPS> (ackerman 0 4)

</pre>

'''Fact-based solution'''

(solve 0 4)

(solve 1 4)

(retract ?solve)

(printout t "A(" ?m "," ?n ") = " ?result crlf)

When invoked, each required A(m,n) needed to solve the requested (solve ?m ?n) facts gets generated as its own fact. Below shows the invocation of the above, as well as an excerpt of the final facts list. Regardless of how many input (solve ?m ?n) requests are made, each possible A(m,n) is only solved once.

<pre>CLIPS> (reset)

=={{header|Clojure}}==

(cond (zero? m) (inc n)

(zero? n) (ackermann (dec m) 1)

=={{header|CLU}}==

ack = proc (m, n: int) returns (int)

if m=0 then return(n+1)

stream$putl(po, "")

end

{{out}}

<pre> 1 2 3 4 5 6 7 8 9

=={{header|COBOL}}==

PROGRAM-ID. Ackermann.

GOBACK

=={{header|CoffeeScript}}==

if m is 0 then n + 1

else if m > 0 and n is 0 then ackermann m - 1, 1

=={{header|Comal}}==

0020 // Ackermann function

0030 //

0150 PRINT

0160 ENDFOR m#

{{out}}

<pre>1 2 3 4 5

=={{header|Common Lisp}}==

(cond ((zerop m) (1+ n))

((zerop n) (ackermann (1- m) 1))

More elaborately:

(case m ((0) (1+ n))

((1) (+ 2 n))

(loop for m from 0 to 4 do

(loop for n from (- 5 m) to (- 6 m) do

{{out}}<pre>A(0, 5) = 6

A(0, 6) = 7

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE NpctAckerman;

END NpctAckerman.

Execute: ^Q NpctAckerman.Do<br/>

<pre>

=={{header|Coq}}==

Fixpoint A m := fix A_m n :=

match m with

| S pn => A pm (A_m pn)

end

Section FOLD.

Definition ackermann : nat → nat → nat :=

fold (λ g, fold g (g (S O))) S.

=={{header|Crystal}}==

{{trans|Ruby}}

if m == 0

n + 1

puts (0..6).map { |n| ack(m, n) }.join(' ')

end

{{out}}

=={{header|D}}==

===Basic version===

if (m == 0)

return n + 1;

void main() {

assert(ackermann(2, 4) == 11);

===More Efficient Version===

{{trans|Mathematica}}

BigInt ipow(BigInt base, BigInt exp) pure nothrow {

writefln("ackermann(4, 2)) (%d digits):\n%s...\n%s",

a.length, a[0 .. 94], a[$ - 96 .. $]);

{{out}}

=={{header|Dart}}==

no caching, the implementation takes ages even for A(4,1)

main() {

print(A(3,5));

print(A(4,0));

=={{header|Dc}}==

This needs a modern Dc with <code>r</code> (swap) and <code>#</code> (comment). It easily can be adapted to an older Dc, but it will impact readability a lot.

+ 1 + # n+1

q

] sA

{{out}}

<pre>

=={{header|Delphi}}==

begin

if m = 0 then

else

Result := Ackermann(m-1, Ackermann(m, n - 1));

=={{header|Draco}}==

proc ack(word m, n) word:

if m=0 then n+1

writeln()

od

{{out}}

<pre> 1 2 3 4 5 6 7 8 9

=={{header|DWScript}}==

begin

if m = 0 then

Result := Ackermann(m-1, 1)

else Result := Ackermann(m-1, Ackermann(m, n-1));

=={{header|Dylan}}==

n + 1

end;

define method ack(m :: <integer>, n :: <integer>)

ack(m - 1, if (n == 0) 1 else ack(m, n - 1) end)

=={{header|E}}==

return if (m <=> 0) { n+1 } \

else if (m > 0 && n <=> 0) { A(m-1, 1) } \

else { A(m-1, A(m,n-1)) }

=={{header|EasyLang}}==

.

call ackerm 3 6 r

=={{header|Egel}}==

def ackermann =

[ 0 N -> N + 1

| M 0 -> ackermann (M - 1) 1

| M N -> ackermann (M - 1) (ackermann M (N - 1)) ]

=={{header|Eiffel}}==

[https://github.com/ljr1981/rosettacode_answers/blob/main/testing/rc_ackerman/rc_ackerman_test_set.e Test of Example code]

class

ACKERMAN_EXAMPLE

end

=={{header|Ela}}==

ack m 0 = ack (m - 1) 1

=={{header|Elena}}==

ELENA 4.x :

ackermann(m,n)

console.readChar()

{{out}}

<pre>

=={{header|Elixir}}==

def ack(0, n), do: n + 1

def ack(m, 0), do: ack(m - 1, 1)

Enum.each(0..3, fn m ->

IO.puts Enum.map_join(0..6, " ", fn n -> Ackermann.ack(m, n) end)

{{out}}

=={{header|Emacs Lisp}}==

(cond ((zerop m) (1+ n))

((zerop n) (ackermann (1- m) 1))

(t (ackermann (1- m)

=={{header|Erlang}}==

-module(ackermann).

-export([ackermann/2]).

ackermann(M, N) when M > 0 andalso N > 0 ->

ackermann(M-1, ackermann(M, N-1)).

=={{header|ERRE}}==

substituted with the new ERRE control statements.

PROGRAM ACKERMAN

END FOR

END PROGRAM

Prints a list of Ackermann function values: from A(0,0) to A(3,9). Uses a stack to avoid

=={{header|Euler Math Toolbox}}==

>M=zeros(1000,1000);

>function map A(m,n) ...

3 5 7 9 11 13

5 13 29 61 125 253

=={{header|Euphoria}}==

This is based on the [[VBScript]] example.

if m = 0 then

return n + 1

end for

puts( 1, "\n" )

=={{header|Ezhil}}==

நிரல்பாகம் அகெர்மன்(முதலெண், இரண்டாமெண்)

முடி

=={{header|F_Sharp|F#}}==

The following program implements the Ackermann function in F# but is not tail-recursive and so runs out of stack space quite fast.

match m, n with

| 0, n -> n + 1

do

Transforming this into continuation passing style avoids limited stack space by permitting tail-recursion.

let rec acker (m, n, k) =

match m,n with

| m, 0 -> acker ((m - 1), 1, k)

| m, n -> acker (m, (n - 1), (fun x -> acker ((m - 1), x, k)))

=={{header|Factor}}==

IN: ackermann

{ [ n 0 = ] [ m 1 - 1 ackermann ] }

[ m 1 - m n 1 - ackermann ackermann ]

=={{header|Falcon}}==

if m == 0: return( n + 1 )

if n == 0: return( ackermann( m - 1, 1 ) )

end

>

The above will output the below.

Formating options to make this pretty are available,

=={{header|FALSE}}==

\$$[%

1-\$@@a;! { i j -> A(i-1, A(i, j-1)) }

]?]a: { j i }

=={{header|Fantom}}==

{

// assuming m,n are positive

}

}

{{out}}

<pre>

=={{header|FBSL}}==

Mixed-language solution using pure FBSL, Dynamic Assembler, and Dynamic C layers of FBSL v3.5 concurrently. '''The following is a single script'''; the breaks are caused by switching between RC's different syntax highlighting schemes:

TestAckermann()

END FUNCTION

int Ackermann(int m, int n)

{

{

return Ackermann(m, n);

END DYNC

ENTER 0, 0

INVOKE Ackermann, m, n

LEAVE

RET 8

{{out}}

=={{header|Fermat}}==

{{out}}

<pre>

=={{header|Forth}}==

over 0= IF nip 1+ EXIT THEN

swap 1- swap ( m-1 n -- )

dup 0= IF 1+ recurse EXIT THEN

{{out|Example of use}}

<pre>FORTH> 0 0 acker . 1 ok

FORTH> 3 4 acker . 125 ok</pre>

An optimized version:

over ( case statement)

0 over = if drop nip 1+ else

then

then then then then

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

IMPLICIT NONE

END FUNCTION Ackermann

=={{header|Free Pascal}}==

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' to do A(4, 2) the stack size needs to be increased

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 0 1 2 3 4 5 6 7 8 9 10 11

=={{header|FunL}}==

ackermann( 0, n ) = n + 1

ackermann( m, 0 ) = ackermann( m - 1, 1 )

for m <- 0..3, n <- 0..4

{{out}}

=={{header|Futhark}}==

fun ackermann(m: int, n: int): int =

if m == 0 then n + 1

else if n == 0 then ackermann(m-1, 1)

else ackermann(m - 1, ackermann(m, n-1))

=={{header|FutureBasic}}==

include "NSLog.incl"

HandleEvents

Output:

=={{header|Gambas}}==

If m = 0 Then

Return n + 1

Next

Next

=={{header|GAP}}==

if m = 0 then

return n + 1;

return fail;

fi;

=={{header|Genyris}}==

cond

(equal? m 0)

else

A (- m 1)