Rosetta Code

Ackermann function: Difference between revisions

Page Discussion

Ackermann function (view source)

Revision as of 09:49, 30 March 2024

8,846 bytes added ,  1 month ago
added RPL
(added RPL)
(34 intermediate revisions by 17 users not shown)
Line 786:
WRITE: / lv_result.
</syntaxhighlight>
 
=={{header|ABC}}==
<syntaxhighlight lang="ABC">HOW TO RETURN m ack n:
SELECT:
m=0: RETURN n+1
m>0 AND n=0: RETURN (m-1) ack 1
m>0 AND n>0: RETURN (m-1) ack (m ack (n-1))
 
FOR m IN {0..3}:
FOR n IN {0..8}:
WRITE (m ack n)>>6
WRITE /</syntaxhighlight>
{{out}}
<pre> 1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 10
3 5 7 9 11 13 15 17 19
5 13 29 61 125 253 509 1021 2045</pre>
 
=={{header|Acornsoft Lisp}}==
{{trans|Common Lisp}}
 
<syntaxhighlight lang="lisp">
(defun ack (m n)
(cond ((zerop m) (add1 n))
((zerop n) (ack (sub1 m) 1))
(t (ack (sub1 m) (ack m (sub1 n))))))
</syntaxhighlight>
 
{{Out}}
 
<pre>
Evaluate : (ack 3 5)
 
Value is : 253
</pre>
 
=={{header|Action!}}==
Line 916 ⟶ 951:
 
=={{header|Agda}}==
{{works with|Agda|2.56.23}}
{{libheader|agda-stdlib v0v1.137}}
<syntaxhighlight lang="agda">
open import Data.Nat
open import Data.Nat.Show
open import IO
module Ackermann where
 
open import Data.Nat using (ℕ ; zero ; suc ; _+_)
ack : ℕ -> ℕ -> ℕ
 
ack : ℕ → ℕ → ℕ
ack zero n = n + 1
ack (suc m) zero = ack m 1
ack (suc m) (suc n) = ack m (ack (suc m) n)
 
main = run (putStrLn (show (ack 3 9)))
open import Agda.Builtin.IO using (IO)
open import Agda.Builtin.Unit using (⊤)
open import Agda.Builtin.String using (String)
open import Data.Nat.Show using (show)
 
postulate putStrLn : String → IO ⊤
{-# FOREIGN GHC import qualified Data.Text as T #-}
{-# COMPILE GHC putStrLn = putStrLn . T.unpack #-}
 
main : IO ⊤
main = putStrLn (show (ack 3 9))
 
 
-- Output:
-- 4093
</syntaxhighlight>
 
NoteThe the unicode ℕUnicode characters, they can be inputentered in emacsEmacs agdaAgda modeas usingfollows: "\bN". Running in bash:
* ℕ : \bN
* → : \to
* ⊤ : \top
 
Running in Bash:
 
<syntaxhighlight lang="bash">
Line 1,030 ⟶ 1,083:
 
=={{header|AppleScript}}==
 
<syntaxhighlight lang="applescript">on ackermann(m, n)
if m is equal to 0 then return n + 1
Line 1,049 ⟶ 1,101:
return (A (m - 1) 1) if n == 0
A (m - 1) (A m (n - 1))</syntaxhighlight>
 
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
Line 1,217 ⟶ 1,270:
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">ackermann: function [m,n][
(m=0)? -> n+1 [
Line 1,230 ⟶ 1,282:
]
]</syntaxhighlight>
 
{{out}}
 
<pre>ackermann 0 0 => 1
ackermann 0 1 => 2
Line 1,366 ⟶ 1,416:
if }
 
zero?!: { 0 = }</syntaxhighlight>
</syntaxhighlight>
{{out}}
<pre>A(0 0 ) = 1
A(0 0 ) = 1
A(0 1 ) = 2
A(0 2 ) = 3
Line 1,391 ⟶ 1,439:
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
{{works with|Chipmunk Basic}}
<syntaxhighlight lang="basic">100 DIM R%(2900),M(2900),N(2900)
110 FOR M = 0 TO 3
Line 1,451 ⟶ 1,500:
return</syntaxhighlight>
{{out}}
<pre> A(3,7) = 1021</pre>
<pre>
A(3,7) = 1021
</pre>
 
<syntaxhighlight lang="basic256"># BASIC256 since 0.9.9.1 supports functions
Line 1,474 ⟶ 1,521:
end if
end function</syntaxhighlight>
 
{{out}}
<pre>0 0 1
0 0 1
0 1 2
0 2 3
Line 1,506 ⟶ 1,551:
IF N% = 0 THEN = FNackermann(M% - 1, 1)
= FNackermann(M% - 1, FNackermann(M%, N%-1))</syntaxhighlight>
 
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="qbasic">100 for m = 0 to 4
110 print using "###";m;
120 for n = 0 to 6
130 if m = 4 and n = 1 then goto 160
140 print using "######";ack(m,n);
150 next n
160 print
170 next m
180 end
190 sub ack(m,n)
200 if m = 0 then ack = n+1
210 if m > 0 and n = 0 then ack = ack(m-1,1)
220 if m > 0 and n > 0 then ack = ack(m-1,ack(m,n-1))
230 end sub</syntaxhighlight>
 
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">FUNCTION ack(m, n)
IF m = 0 THEN LET ack = n+1
IF m > 0 AND n = 0 THEN LET ack = ack(m-1, 1)
IF m > 0 AND n > 0 THEN LET ack = ack(m-1, ack(m, n-1))
END FUNCTION
 
FOR m = 0 TO 4
PRINT USING "###": m;
FOR n = 0 TO 8
! A(4, 1) OR higher will RUN OUT of stack memory (default 1M)
! change n = 1 TO n = 2 TO calculate A(4, 2), increase stack!
IF m = 4 AND n = 1 THEN EXIT FOR
PRINT USING "######": ack(m, n);
NEXT n
PRINT
NEXT m
 
END</syntaxhighlight>
 
==={{header|QuickBasic}}===
Line 1,668 ⟶ 1,750:
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|Binary Lambda Calculus}}==
 
The Ackermann function on Church numerals (arbitrary precision), as shown in https://github.com/tromp/AIT/blob/master/fast_growing_and_conjectures/ackermann.lam is the 63 bit BLC
program
 
<pre>010000010110000001010111110101100010110000000011100101111011010</pre>
 
=={{header|BQN}}==
Line 1,799 ⟶ 1,888:
 
p ackermann 3, 4 #Prints 125</syntaxhighlight>
 
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">:import std/Combinator .
:import std/Number/Unary U
:import std/Math .
 
# unary ackermann
ackermann-unary [0 [[U.inc 0 1 (+1u)]] U.inc]
 
:test (ackermann-unary (+0u) (+0u)) ((+1u))
:test (ackermann-unary (+3u) (+4u)) ((+125u))
 
# ternary ackermann (lower space complexity)
ackermann-ternary y [[[=?1 ++0 (=?0 (2 --1 (+1)) (2 --1 (2 1 --0)))]]]
 
:test ((ackermann-ternary (+0) (+0)) =? (+1)) ([[1]])
:test ((ackermann-ternary (+3) (+4)) =? (+125)) ([[1]])</syntaxhighlight>
 
=={{header|C}}==
Line 2,785 ⟶ 2,891:
 
=={{header|Coq}}==
===Standard===
<syntaxhighlight lang="coq">Require Import Arith.
<syntaxhighlight lang="coq">
Fixpoint A m := fix A_m n :=
Fixpoint ack (m : nat) : nat -> nat :=
match m with
fix ack_m |(n 0: =>nat) n: +nat 1:=
|match Sm pm =>with
match| n0 with=> S n
| S | 0pm => A pm 1
|match Sn pn => A pm (A_m pn)with
end | 0 => ack pm 1
| S pn => ack pm (ack_m pn)
end.</syntaxhighlight>
end
end.
 
 
(*
Example:
A(3, 2) = 29
*)
 
Eval compute in ack 3 2.
</syntaxhighlight>
 
{{out}}
<pre>
= 29
: nat
</pre>
 
===Using fold===
<syntaxhighlight lang="coq">Require Import Utf8.
<syntaxhighlight lang="coq">
Require Import Utf8.
 
Section FOLD.
Context {A : Type} (f : A → A) (a : A).
Fixpoint fold (n : nat) : A :=
match n with
| O => a
| S n'k => f (fold n'k)
end.
End FOLD.
Line 3,036 ⟶ 3,161:
 
=={{header|EasyLang}}==
<syntaxhighlight lang="text">func ackerm m n . r .
func ifackerm m =n 0.
if rm = n + 10
elif return n =+ 01
elif calln ackerm= m - 1 1 r0
return ackerm (m - 1) 1
else
else
call ackerm m n - 1 h
call return ackerm (m - 1) hackerm rm (n - 1)
.
.
callprint ackerm 3 6 r
print r</syntaxhighlight>
 
=={{header|Egel}}==
Line 3,094 ⟶ 3,219:
 
=={{header|Elena}}==
ELENA 46.x :
<syntaxhighlight lang="elena">import extensions;
 
ackermann(m,n)
{
if(n < 0 || m < 0)
{
InvalidArgumentException.raise()
};
m =>
0 { ^n + 1 }
:! {
n =>
0 { ^ackermann(m - 1,1) }
:! { ^ackermann(m - 1,ackermann(m,n-1)) }
}
}
 
public program()
{
for(int i:=0,; i <= 3,; i += 1)
{
for(int j := 0,; j <= 5,; j += 1)
{
console.printLine("A(",i,",",j,")=",ackermann(i,j))
}
};
 
console.readChar()
}</syntaxhighlight>
{{out}}
Line 3,178 ⟶ 3,303:
(t (ackermann (1- m)
(ackermann m (1- n))))))</syntaxhighlight>
 
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun ackermann = int by int m, int n
return when(m == 0,
n + 1,
when(n == 0,
ackermann(m - 1, 1),
ackermann(m - 1, ackermann(m, n - 1))))
end
for int m = 0; m <= 3; ++m
for int n = 0; n <= 6; ++n
writeLine("Ackermann(" + m + ", " + n + ") = " + ackermann(m, n))
end
end
</syntaxhighlight>
{{out}}
<pre>
Ackermann(0, 0) = 1
Ackermann(0, 1) = 2
Ackermann(0, 2) = 3
Ackermann(0, 3) = 4
Ackermann(0, 4) = 5
Ackermann(0, 5) = 6
Ackermann(0, 6) = 7
Ackermann(1, 0) = 2
Ackermann(1, 1) = 3
Ackermann(1, 2) = 4
Ackermann(1, 3) = 5
Ackermann(1, 4) = 6
Ackermann(1, 5) = 7
Ackermann(1, 6) = 8
Ackermann(2, 0) = 3
Ackermann(2, 1) = 5
Ackermann(2, 2) = 7
Ackermann(2, 3) = 9
Ackermann(2, 4) = 11
Ackermann(2, 5) = 13
Ackermann(2, 6) = 15
Ackermann(3, 0) = 5
Ackermann(3, 1) = 13
Ackermann(3, 2) = 29
Ackermann(3, 3) = 61
Ackermann(3, 4) = 125
Ackermann(3, 5) = 253
Ackermann(3, 6) = 509
</pre>
 
=={{header|Erlang}}==
Line 3,793 ⟶ 3,965:
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Ackermann_function}}
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
 
[[File:Fōrmulæ - Ackermann function 01.png]]
 
'''Test case'''
 
[[File:Fōrmulæ - Ackermann function 02.png]]
Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
[[File:Fōrmulæ - Ackermann function 03.png]]
In '''[https://formulae.org/?example=Ackermann_function this]''' page you can see the program(s) related to this task and their results.
 
=={{header|Gambas}}==
Line 4,955 ⟶ 5,133:
=={{header|jq}}==
{{ works with|jq|1.4}}
'''Also works with gojq, the Go implementation of jq.'''
 
Except for a minor tweak to the line using string interpolation, the following have also been tested using jaq, the Rust implementation of jq, as of April 13, 2023.
 
For infinite-precision integer arithmetic, use gojq or fq.
===Without Memoization===
<syntaxhighlight lang="jq"># input: [m,n]
Line 5,025 ⟶ 5,208:
def A(m;n): [m,n,{}] | ack | .[0];
</syntaxhighlight>
'''Examples:'''
'''Example:'''<syntaxhighlight lang="jq">A(4,1)</syntaxhighlight>
<syntaxhighlight lang="jq">A(4;1)</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh">65533</syntaxhighlight>
 
Using gojq:
<syntaxhighlight lang="jq">A(4;2), A(3;1000000) | tostring | length</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh">
19729
301031
</syntaxhighlight>
 
=={{header|Jsish}}==
Line 5,095 ⟶ 5,287:
 
=={{header|K}}==
{{works with|Kona}}
See [https://github.com/kevinlawler/kona/wiki the K wiki]
<syntaxhighlight lang="k"> ack:{:[0=x;y+1;0=y;_f[x-1;1];_f[x-1;_f[x;y-1]]]}
ack[2;2]</syntaxhighlight>
7
ack[2;7]
17</syntaxhighlight>
 
=={{header|Kdf9 Usercode}}==
Line 5,453 ⟶ 5,648:
{{out}}
<pre>61 </pre>
 
=={{header|MACRO-11}}==
<syntaxhighlight lang="macro11"> .TITLE ACKRMN
.MCALL .TTYOUT,.EXIT
ACKRMN::JMP MKTBL
 
; R0 = ACK(R0,R1)
ACK: MOV SP,R2 ; KEEP OLD STACK PTR
MOV #ASTK,SP ; USE PRIVATE STACK
JSR PC,1$
MOV R2,SP ; RESTORE STACK PTR
RTS PC
1$: TST R0
BNE 2$
INC R1
MOV R1,R0
RTS PC
2$: TST R1
BNE 3$
DEC R0
INC R1
BR 1$
3$: MOV R0,-(SP)
DEC R1
JSR PC,1$
MOV R0,R1
MOV (SP)+,R0
DEC R0
BR 1$
.BLKB 4000 ; BIG STACK
ASTK = .
 
; PRINT TABLE
MMAX = 4
NMAX = 7
MKTBL: CLR R3
1$: CLR R4
2$: MOV R3,R0
MOV R4,R1
JSR PC,ACK
JSR PC,PR0
INC R4
CMP R4,#NMAX
BLT 2$
MOV #15,R0
.TTYOUT
MOV #12,R0
.TTYOUT
INC R3
CMP R3,#MMAX
BLT 1$
.EXIT
; PRINT NUMBER IN R0 AS DECIMAL
PR0: MOV #4$,R1
1$: MOV #-1,R2
2$: INC R2
SUB #12,R0
BCC 2$
ADD #72,R0
MOVB R0,-(R1)
MOV R2,R0
BNE 1$
3$: MOVB (R1)+,R0
.TTYOUT
BNE 3$
RTS PC
.ASCII /...../
4$: .BYTE 11,0
.END ACKRMN</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 5 7 9 11 13 15
5 13 29 61 125 253 509</pre>
 
=={{header|MAD}}==
Line 5,545 ⟶ 5,815:
ACK(3,7) = 1021
ACK(3,8) = 2045</pre>
 
 
 
 
=={{header|Maple}}==
Line 7,829 ⟶ 8,096:
]
]</pre>
 
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout 'A(3,9) = ' <A 3 9>>;
};
 
A {
0 s.N = <+ s.N 1>;
s.M 0 = <A <- s.M 1> 1>;
s.M s.N = <A <- s.M 1> <A s.M <- s.N 1>>>;
};</syntaxhighlight>
{{out}}
<pre>A(3,9) = 4093</pre>
 
=={{header|ReScript}}==
Line 8,231 ⟶ 8,511:
Ackermann(3, 4) = 125</pre>
 
=={{header|RiscRISC-V Assembly}}==
the basic recursive function, because memorization and other improvements would blow the clarity.
<syntaxhighlight lang="risc-v">ackermann: #x: a1, y: a2, return: a0
Line 8,261 ⟶ 8,541:
jr t0, 0
</syntaxhighlight>
 
=={{header|RPL}}==
{{works with|RPL|HP49-C}}
« '''CASE'''
OVER NOT '''THEN''' NIP 1 + '''END'''
DUP NOT '''THEN''' DROP 1 - 1 <span style="color:blue">ACKER</span> '''END'''
OVER 1 - ROT ROT 1 - <span style="color:blue">ACKER</span> <span style="color:blue">ACKER</span>
'''END'''
» '<span style="color:blue">ACKER</span>' STO
 
3 4 <span style="color:blue">ACKER</span>
{{out}}
<pre>
1: 125
</pre>
Runs in 7 min 13 secs on a HP-50g. Speed could be increased by replacing every <code>1</code> by <code>1.</code>, which would force calculations to be made with floating-point numbers, but we would then lose the arbitrary precision.
 
=={{header|Ruby}}==
Line 8,474 ⟶ 8,770:
 
=={{header|Seed7}}==
===Basic version===
<syntaxhighlight lang="seed7">const func integer: ackermann (in integer: m, in integer: n) is func
result
Line 8,487 ⟶ 8,784:
end func;</syntaxhighlight>
Original source: [http://seed7.sourceforge.net/algorith/math.htm#ackermann]
===Improved version===
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
const func bigInteger: ackermann (in bigInteger: m, in bigInteger: n) is func
result
var bigInteger: ackermann is 0_;
begin
case m of
when {0_}: ackermann := succ(n);
when {1_}: ackermann := n + 2_;
when {2_}: ackermann := 3_ + 2_ * n;
when {3_}: ackermann := 5_ + 8_ * pred(2_ ** ord(n));
otherwise:
if n = 0_ then
ackermann := ackermann(pred(m), 1_);
else
ackermann := ackermann(pred(m), ackermann(m, pred(n)));
end if;
end case;
end func;
const proc: main is func
local
var bigInteger: m is 0_;
var bigInteger: n is 0_;
var string: stri is "";
begin
for m range 0_ to 3_ do
for n range 0_ to 9_ do
writeln("A(" <& m <& ", " <& n <& ") = " <& ackermann(m, n));
end for;
end for;
writeln("A(4, 0) = " <& ackermann(4_, 0_));
writeln("A(4, 1) = " <& ackermann(4_, 1_));
stri := str(ackermann(4_, 2_));
writeln("A(4, 2) = (" <& length(stri) <& " digits)");
writeln(stri[1 len 80]);
writeln("...");
writeln(stri[length(stri) - 79 ..]);
end func;</syntaxhighlight>
Original source: [https://seed7.sourceforge.net/algorith/math.htm#bigInteger_ackermann]
 
{{out}}
<pre>
A(0, 0) = 1
A(0, 1) = 2
A(0, 2) = 3
A(0, 3) = 4
A(0, 4) = 5
A(0, 5) = 6
A(0, 6) = 7
A(0, 7) = 8
A(0, 8) = 9
A(0, 9) = 10
A(1, 0) = 2
A(1, 1) = 3
A(1, 2) = 4
A(1, 3) = 5
A(1, 4) = 6
A(1, 5) = 7
A(1, 6) = 8
A(1, 7) = 9
A(1, 8) = 10
A(1, 9) = 11
A(2, 0) = 3
A(2, 1) = 5
A(2, 2) = 7
A(2, 3) = 9
A(2, 4) = 11
A(2, 5) = 13
A(2, 6) = 15
A(2, 7) = 17
A(2, 8) = 19
A(2, 9) = 21
A(3, 0) = 5
A(3, 1) = 13
A(3, 2) = 29
A(3, 3) = 61
A(3, 4) = 125
A(3, 5) = 253
A(3, 6) = 509
A(3, 7) = 1021
A(3, 8) = 2045
A(3, 9) = 4093
A(4, 0) = 13
A(4, 1) = 65533
A(4, 2) = (19729 digits)
20035299304068464649790723515602557504478254755697514192650169737108940595563114
...
84717124577965048175856395072895337539755822087777506072339445587895905719156733
</pre>
 
=={{header|SETL}}==
Line 9,021 ⟶ 9,410:
3 5 7 9 11 13 15
5 13 29 61 125 253 509</pre>
 
=={{header|Ursalang}}==
<syntaxhighlight lang="ursalang">let A = fn(m, n) {
if m == 0 {n + 1}
else if m > 0 and n == 0 {A(m - 1, 1)}
else {A(m - 1, A(m, n - 1))}
}
print(A(0, 0))
print(A(3, 4))
print(A(3, 1))</syntaxhighlight>
 
=={{header|Ursala}}==
Line 9,326 ⟶ 9,726:
 
=={{header|Wren}}==
<syntaxhighlight lang="ecmascriptwren">// To use recursion definition and declaration must be on separate lines
var Ackermann
Ackermann = Fn.new {|m, n|
Aerobar
1,150

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/332437...363056"