Fibonacci Numbers
Assembler x86 Fasm/Linux, Variant 1
;RUN IT BY
; fasm FN.asm; time ./FN
format ELF executable 3
segment readable executable
entry $
mov eax,41 ;an argument
push eax
call fib
pop eax
call todec ;form string for output
mov edx,msgend-msg+1
mov ecx,msg
.l2: cmp byte [ecx],0 ;skip leading zeros
jnz .l1
dec edx
inc ecx
jmp .l2
.l1: mov ebx,1 ;STDOUT
mov eax,4 ;sys_write
int 0x80
xor ebx,ebx ;exit code 0
mov eax,1 ;sys_exit
int 0x80
fib: cmp eax,2
ja .l1
mov dword [esp+4],1
ret
.l1: dec eax
push eax
call fib
pop edx
mov eax,[esp+4]
mov [esp+4],edx
dec eax
dec eax
push eax
call fib
pop eax
add eax,[esp+4]
mov [esp+4],eax
ret
todec: mov ebx,msgend-1
mov ecx,10
.l1: xor edx,edx
div ecx
add dl,48
mov [ebx],dl
dec ebx
or eax,eax
jnz .l1
ret
segment readable writeable
msg db 0,0,0,0,0,0,0,0,0,0
msgend db 10
Assembler x86 Fasm/Linux, Variant 2
format ELF executable 3
segment readable executable
entry $
mov eax,41 ;an argument
push eax
call fib
mov eax,ecx
call todec ;form string for output
mov edx,msgend-msg+1
mov ecx,msg
.l2: cmp byte [ecx],0 ;skip leading zeros
jnz .l1
dec edx
inc ecx
jmp .l2
.l1: mov ebx,1 ;STDOUT
mov eax,4 ;sys_write
int 0x80
xor ebx,ebx ;exit code 0
mov eax,1 ;sys_exit
int 0x80
fib: cmp eax,2 ;in: eax; out: ecx
ja .l1
mov ecx,1
ret
.l1: dec eax
push eax
call fib
pop eax
push ecx
dec eax
call fib
pop eax
add ecx,eax
ret
Assembler x86-64 Fasm/Linux, Variant 1
format ELF64 executable 3
segment readable executable
entry $
mov eax,41 ;an argument
push rax
call fib
pop rax
call todec ;form string for output
mov rdx,msgend-msg+1
mov rsi,msg
.l2: cmp byte [rsi],0 ;skip leading zeros
jnz .l1
dec rdx
inc rsi
jmp .l2
.l1: mov edi,1 ;STDOUT
mov rax,1 ;sys_write
syscall
xor edi,edi ;exit code 0
mov eax,60 ;sys_exit
syscall
fib: cmp rax,2
ja .l1
mov qword [rsp+8],1
ret
.l1: dec rax
push rax
call fib
pop rdx
mov rax,[rsp+8]
mov [rsp+8],rdx
dec rax
dec rax
push rax
call fib
pop rax
add rax,[rsp+8]
mov [rsp+8],rax
ret
todec: mov rbx,msgend-1
mov ecx,10
.l1: xor rdx,rdx
div rcx
add dl,48
mov [rbx],dl
dec rbx
or rax,rax
jnz .l1
ret
segment readable writeable
msg db 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
msgend db 10
Assembler x86-64 Fasm/Linux, Variant 2
format ELF64 executable 3
segment readable executable
entry $
mov eax,41 ;an argument
call fib
mov rax,rcx
call todec ;form string for output
mov rdx,msgend-msg+1
mov rsi,msg
.l2: cmp byte [rsi],0 ;skip leading zeros
jnz .l1
dec rdx
inc rsi
jmp .l2
.l1: mov edi,1 ;STDOUT
mov rax,1 ;sys_write
syscall
xor edi,edi ;exit code 0
mov eax,60 ;sys_exit
syscall
fib: cmp rax,2 ;in: rax; out: rcx
ja .l1
mov rcx,1
ret
.l1: dec rax
push rax
call fib
pop rax
push rcx
dec rax
call fib
pop rax
add rcx,rax
ret
AWK
# time gawk -f fib.awk
# time mawk -f fib.awk
# time busybox awk -f fib.awk
function fib (n) {
if (n < 3) return 1;
return fib(n - 1) + fib(n - 2);
}
BEGIN {print fib(31)}
BASH
# time bash fib.sh
fib() {
case $1 in
[12]) echo 1;;
*) echo $(($(fib $(($1 - 1))) + $(fib $(($1 - 2)))));;
esac
}
fib 15
Visual BASIC
'RUN IT AT LIBRE OFFICE, OPEN OFFICE, OR MICROSOFT OFFICE
function fib(n)
if n < 3 then
fib = 1
else
fib = fib(n-2)+fib(n-1)
end if
end function
sub Main
dim t1 as long, f as long
t1 = timer
f = fib(32)
print timer-t1
print f
end sub
GAMBAS3 BASIC
'COMPILE IT AT GAMBAS3 ENVIRONMENT
'THEN RUN AT COMMAND LINE BY
' time ./FN
Function fib(n As Integer) As Long
If n < 3 Then
Return 1
Else
Return fib(n - 2) + fib(n - 1)
End If
End
Public Sub Main()
Print fib(32)
End
C
/*RUN IT BY (GNU compiler)
gcc -O3 FN.c; time ./a.out
OR (without optimisation)
gcc FN.c; time ./a.out
OR (Intel compiler)
icc -fast FN.c; time ./a.out
OR (LLVM compiler)
clang -O3 FN.c; time ./a.out
OR (Amsterdam Compiler Kit)
ack -mlinux386 -O4 -o fib fib.c; time ./fib
*/
#include <stdio.h>
int fib (int n) {
return n < 3 ? 1 : fib(n - 1) + fib(n - 2);
}
main() {
int k = 41;
printf("%d %d\n", k, fib(k));
}
C - the extended version
#include <stdio.h>
long count, nl, maxnl;
long fib(int n) {
long t;
++count;
if (++nl > maxnl) maxnl = nl;
if (n < 3) return --nl, 1;
t = fib(n - 1) + fib(n - 2);
--nl;
return t;
}
main(int argc, char *argv[]) {
int p = atoi(argv[1]);
printf("fib(%d) = %ld, ", p, fib(p));
if (nl)
puts("Error!");
else
printf("times=%ld depth=%ld\n", count, maxnl);
}
Dino
// time dino fib.d
func fib(n) {
if (n < 3) return 1;
return fib(n - 1) + fib(n - 2);
}
putln (fib(33));
Erlang
% erlc fib.erl; time echo 'fib:start().'|erl
-module(fib).
-export([start/0]).
fib(0) -> 0;
fib(1) -> 1;
fib(2) -> 1;
fib(N) -> fib(N - 1) + fib(N - 2).
start() -> fib(36).
Haskell
-- ghc -O fib.hs; time ./fib
-- time runhugs fib.hs
fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n - 2)
main = print (fib(25))
Java
// javac fib.java;time java fib
public class fib {
static int fibc(int n) {
if (n < 3)
return 1;
return fibc(n - 1) + fibc(n - 2);
}
public static void main(String[] args) {
System.out.println(fibc(40));
}
}
JavaScript with www-browser
<!--OPEN IT AT ANY WWW-BROWSER WITH JAVASCRIPT SUPPORT-->
<script>
function fib(n){if(n<3)return 1;return fib(n-1)+fib(n-2);}
var d=new Date();
var f=fib(39);
var e=new Date();
document.write(f,' ',e.getTime()-d.getTime());
</script>
JavaScript with console
//RUN IT BY
// time node fib.js
function fib(n){if(n<3)return 1;return fib(n-1)+fib(n-2);}
console.log(fib(40));
Lisp
; time clisp fib.lsp
; time sbcl --load fib.lsp
(defun fib (n)
(cond
((< n 3) 1)
((+ (fib (- n 1)) (fib (- n 2))))))
(print (fib 30))
(quit)
Lua
-- time lua fib.lua
function fib (n)
if (n < 3) then
return 1
else
return fib(n - 1) + fib(n - 2)
end
end
print(fib(33))
Metapost/Metafont
% time mpost fib.mp
% time mf fib.mp
def fib(expr n) =
if n < 3:
1
else:
fib(n-1) + fib(n-2)
fi
enddef;
show fib(23)
end
MSE
c time mse -t fib.mse /dev/null
c this script is almost functional equivalent to the next C-program
c #include <stdio.h>
c int r;
c void fib (int n) {
c if (n < 3)
c ++r;
c else {
c fib(n - 1);
c fib(n - 2);
c }
c }
c main() {
c fib(28);
c printf("%d\n", r);
c }
define(fib) > '!' sub(3) '1' out(3)
begin > '*!'
'28' c an argument
store(0) '0' endstore
store(d) '0123456789' endstore
group(1)
'' > back(1)
'!' > store(3) use(2)
'*' > out(0) nl
group(2)
any(d) fol(d) > dup
any(d) > dup endstore
ifgt(3) '2'
do(fib) do(fib)
else
add(0) '1'
endif
back(1)
use(1)
Pascal
(*
fpc -O3 fib.pas; time ./fib
*)
function fib (n:byte): longint;
begin
if n < 3 then
fib := 1
else
fib := fib(n - 1) + fib(n - 2);
end;
begin
writeln(fib(40));
end.
Classical Old Pascal
(*
ack -mlinux386 -O4 -o fib fib.p; time ./fib
*)
program fibo(output);
function fib(n: integer): integer;
begin
if n < 3 then
fib := 1
else
fib := fib(n - 1) + fib(n - 2)
end;
begin
writeln(fib(40))
end.
Perl
# time perl fib.pl
sub fib {
my $n = shift;
if ($n < 3) {return 1;}
return fib($n-1) + fib($n-2);
}
print fib(30), "\n"
PHP
<?php
// time php fib.php
function fib ($n) {
if ($n < 3) return 1;
return fib($n - 1) + fib($n - 2);
}
echo fib(30)."\n"
?>
PostScript
% time gs fib.ps
/fib {
dup 3 lt
{pop 1}
{1 sub dup 1 sub fib exch fib add} ifelse
} def
32 fib =
quit
Prolog
% time gprolog --init-goal "['fib.pro'],fib"
% time swipl -g "['fib.pro'],fib"
fib :- fib(30,R), write(R), nl, halt.
fib(N,M) :- N<3, M=1, !;
N1 is N-1, fib(N1,M1), N2 is N-2, fib(N2,M2), M is M1+M2.
Python
# time python fib.py
def fib(n):
if n < 3: return 1
return fib(n - 1) + fib(n - 2)
print fib(31)
Ruby
# time ruby fib.rb
def fib(n)
if n < 3
1
else
fib(n - 1) + fib(n - 2)
end
end
print fib(31), "\n"
SED
#Run it by
# time echo 29|sed -f fib.sed
#This script is taken from http://rosettacode.org/wiki/Fibonacci_numbers#sed
#Its algorithm is 10-20% faster than for other languages, see details at MSE topic
# First we need to convert each number into the right number of ticks
# Start by marking digits
s/[0-9]/<&/g
# We have to do the digits manually.
s/0//g; s/1/|/g; s/2/||/g; s/3/|||/g; s/4/||||/g; s/5/|||||/g
s/6/||||||/g; s/7/|||||||/g; s/8/||||||||/g; s/9/|||||||||/g
# Multiply by ten for each digit from the front.
:tens
s/|</<||||||||||/g
t tens
# Done with digit markers
s/<//g
# Now the actual work.
:split
# Convert each stretch of n >= 2 ticks into two of n-1, with a mark between
s/|\(|\+\)/\1-\1/g
# Convert the previous mark and the first tick after it to a different mark
# giving us n-1+n-2 marks.
s/-|/+/g
# Jump back unless we're done.
t split
# Get rid of the pluses, we're done with them.
s/+//g
# Convert back to digits
:back
s/||||||||||/</g
s/<\([0-9]*\)$/<0\1/g
s/|||||||||/9/g;
s/|||||||||/9/g; s/||||||||/8/g; s/|||||||/7/g; s/||||||/6/g;
s/|||||/5/g; s/||||/4/g; s/|||/3/g; s/||/2/g; s/|/1/g;
s/</|/g
t back
s/^$/0/
TCL
# time tclsh fib.tcl
proc fib n {
if $n<3 {return 1}
expr [fib [expr $n-1]]+[fib [expr $n-2]]
}
puts [fib 25]
TEX
% time tex fib.tex
\def\fib#1{%
\ifnum#1<3\global\count0=1%
\else%
\count1=#1\advance\count1by-1%
\edef\z{{\the\count1}}%
\expandafter\fib\z%
\count1=#1\advance\count1by-2%
\edef\z{{\the\count1}}%
{\count2=\count0%
\expandafter\fib\z%
\global\advance\count0by\count2}\fi}
\fib{27}\message{\the\count0}
\bye
Ackermann Function
Assembler x86 Fasm/Linux
format ELF executable 3
segment readable executable
entry $
mov eax,5 ;n
mov ebx,2 ;x
mov ecx,3 ;y
call ack
mov eax,edx
call todec ;form decimal string for output
mov edx,msgend-msg+1
mov ecx,msg
.l2: cmp byte [ecx],0 ;skip leading zeros
jnz .l1
dec edx
inc ecx
jmp .l2
.l1: mov ebx,1 ;STDOUT
mov eax,4 ;sys_write
int 0x80
xor ebx,ebx ;exit code 0
mov eax,1 ;sys_exit
int 0x80
ack: or eax,eax ;in: eax; out: ecx
jne .l1
mov edx,ecx
inc edx
ret
.l1: or ecx,ecx
jne .l2
dec eax
jne .l3
mov edx,ebx
ret
.l3: xor edx,edx
dec eax
jne .l4
ret
.l4: inc edx
ret
.l2: push eax
push ebx
dec ecx
call ack
pop ebx
pop eax
dec eax
mov ecx,edx
jmp ack
todec: mov ebx,msgend-1
mov ecx,10
.l1: xor edx,edx
div ecx
add dl,48
mov [ebx],dl
dec ebx
or eax,eax
jnz .l1
ret
segment readable writeable
msg db 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
msgend db 10
Assembler x86-64 Fasm/Linux
format ELF64 executable 3
segment readable executable
entry $
mov eax,5 ;n
mov ebx,2 ;x
mov ecx,3 ;y
call ack
mov rax,rdx
call todec ;form decimal string for output
mov rdx,msgend-msg+1
mov rsi,msg
.l2: cmp byte [rsi],0 ;skip leading zeros
jnz .l1
dec rdx
inc rsi
jmp .l2
.l1: mov edi,1 ;STDOUT
mov eax,1 ;sys_write
syscall
xor edi,edi ;exit code 0
mov eax,60 ;sys_exit
syscall
ack: or rax,rax ;in: rax; out: rcx
jne .l1
mov rdx,rcx
inc rdx
ret
.l1: or rcx,rcx
jne .l2
dec rax
jne .l3
mov rdx,rbx
ret
.l3: xor rdx,rdx
dec rax
jne .l4
ret
.l4: inc rdx
ret
.l2: push rax
push rbx
dec rcx
call ack
pop rbx
pop rax
dec rax
mov rcx,rdx
jmp ack
todec: mov rbx,msgend-1
mov ecx,10
.l1: xor rdx,rdx
div rcx
add dl,48
mov [rbx],dl
dec rbx
or rax,rax
jnz .l1
ret
segment readable writeable
msg db 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
msgend db 10
AWK
function ack (n, x, y) {
if (n == 0) return y + 1;
if (y == 0) {
if (n == 1) return x;
if (n == 2) return 0;
return 1;
}
return ack(n - 1, x, ack(n, x, y - 1));
}
BEGIN {print ack(5, 2, 3)}
BASH, Variant 1
ack() {
case $1 in
0) echo $(($3 + 1));;
*) case $3 in
0) case $1 in
1) echo $2;;
2) echo 0;;
*) echo 1;;
esac;;
*) echo $(ack $(($1 - 1)) $2 $(ack $1 $2 $(($3 - 1))));;
esac;;
esac
}
ack 1 1 50
BASH, Variant 2
ack() {
if [ $1 -eq 0 ];
then echo $[$3 + 1]
elif [ $3 -eq 0 ]; then
if [ $1 -eq 1 ]; then echo $2;return;fi
if [ $1 -eq 2 ]; then echo 0;return;fi
echo 1
else echo $(ack $(($1 - 1)) $2 $(ack $1 $2 $(($3-1))))
fi
}
ack 1 1 100
Visual BASIC
Function ack(n As Integer, x As Integer, y As Integer) As Long
If n = 0 Then
ack = y + 1
Else If y = 0 Then
If n = 1 Then
ack = x
Else If n = 2 Then
ack = 0
Else
ack = 1
End If
Else
ack = ack(n - 1, x, ack(n, x, y - 1))
End If
End Function
Public Sub Main()
Print ack(1, 1, 1000)
End Sub
GAMBAS3 BASIC
Function ack(n As Integer, x As Integer, y As Integer) As Long
If n = 0 Then
Return y + 1
Else If y = 0 Then
If n = 1 Then
Return x
Else If n = 2 Then
Return 0
Else
Return 1
End If
Else
Return ack(n - 1, x, ack(n, x, y - 1))
End If
End
Public Sub Main()
Print ack(1, 1, 1000)
End
C
#include <stdio.h>
long ack(long n, long x, long y) {
if (n == 0) return y + 1;
if (y == 0)
switch (n) {
case 1: return x;
case 2: return 0;
default: return 1;
}
return ack(n - 1, x, ack(n, x, y - 1));
}
main() {
printf("%ld\n", ack(5, 2, 3));
}
C - the extended version
#include <stdio.h>
long count, nl, maxnl;
long ack(long n, long x, long y) {
long t;
++count;
if (++nl > maxnl) maxnl = nl;
if (n == 0) return --nl, y + 1;
if (y == 0) {
--nl;
switch (n) {
case 1: return x;
case 2: return 0;
default: return 1;
}
}
t = ack(n - 1, x, ack(n, x, y - 1));
--nl;
return t;
}
main(int argc, char *argv[]) {
int p1 = atoi(argv[1]), p2 = atoi(argv[2]), p3 = atoi(argv[3]);
printf("ack(%d,%d,%d) = %ld, ", p1, p2, p3, ack(p1, p2, p3));
if (nl)
puts("Error!");
else
printf("times=%ld depth=%ld\n", count, maxnl);
}
Dino
func ack(n, x, y) {
if (n == 0) return y + 1;
if (y == 0) {
if (n == 1) return x;
if (n == 2) return 0;
return 1;
}
return ack(n - 1, x, ack(n, x, y - 1));
}
putln (ack(5, 2, 3));
Erlang
% erlc ack.erl; time echo 'ack:start().'|erl
-module(ack).
-export([start/0]).
ack(0, _, Y) -> Y + 1;
ack(1, X, 0) -> X;
ack(2, _, 0) -> 0;
ack(_, _, 0) -> 1;
ack(N, X, Y) -> ack(N - 1, X, ack(N, X, Y - 1)).
start() -> ack(5, 2, 3).
Haskell
ack 0 x y = y + 1
ack 1 x 0 = x
ack 2 x 0 = 0
ack n x 0 = 1
ack n x y = ack (n - 1) x (ack n x (y - 1))
main = print (ack 5 2 3)
Java
public class ack {
static int ackc(int n, int x, int y) {
if (n == 0) return y + 1;
if (y == 0) {
if (n == 1) return x;
if (n == 2) return 0;
return 1;
}
return ackc(n - 1, y, ackc(n, x, y - 1));
}
public static void main(String[] args) {
System.out.println(ackc(1, 1, 8000));
}
}
JavaScript with www-browser
<script>
function ack(n,x,y){
if(n==0)return y+1;
if(y==0){
if(n==1)return x;
if(n==2)return 0;
return 1;
}
return ack(n-1,x,ack(n,x,y-1));
}
var d=new Date();
var f=ack(1,1,30000);
var e=new Date();
document.write(f,' ',e.getTime()-d.getTime());
</script>
JavaScript with console
function ack(n,x,y){
if(n==0)return y+1;
if(y==0){
if(n==1)return x;
if(n==2)return 0;
return 1;
}
return ack(n-1,x,ack(n,x,y-1));
}
console.log(ack(1,1,9500));
Lisp
(defun ack (n x y)
(cond
((= n 0) (+ y 1))
((= y 0)
(cond
((= n 1) x)
((= n 2) 0)
(1)))
((ack (- n 1) x (ack n x (- y 1))))))
(print (ack 1 1 5400))
(quit)
Lua
function ack(n, x, y)
if (n == 0) then return y + 1 end
if (y == 0) then
if (n == 1) then return x end
if (n == 2) then return 0 end
return 1
end
return ack(n - 1, x, ack(n, x, y - 1))
end
print(ack(5, 2, 3))
Metapost/Metafont
def ack(expr n, x, y) =
if n = 0:
y + 1
else: if y = 0:
if n = 1:
x
else: if n = 2:
0
else:
1
fi fi
else:
ack(n - 1, x, ack(n, x, y - 1))
fi fi
enddef;
show ack(1, 1, 4095)
end
Pascal
function ack (n: byte; x: longint; y: longint): longint;
begin
if n = 0 then
ack := y + 1
else if y = 0 then
if n = 1 then
ack := x
else if n = 2 then
ack := 0
else
ack := 1
else
ack := ack(n - 1, x, ack(n, x, y - 1));
end;
begin
writeln(ack(5, 2, 3));
end.
Perl
sub ack {
my $n = shift;
my $x = shift;
my $y = shift;
if ($n == 0) {return $y + 1;}
if ($y == 0) {
if ($n == 1) {return $x;}
if ($n == 2) {return 0;}
return 1;
}
return ack($n-1, $x, ack($n, $x, $y - 1));
}
print ack(5, 2, 3), "\n"
PHP
<?php
function ack ($n, $x, $y) {
if ($n == 0) return $y + 1;
if ($y == 0) {
if ($n == 1) return $x;
if ($n == 2) return 0;
return 1;
}
return ack($n - 1, $x, ack($n, $x, $y - 1));
}
echo ack(5, 2, 3)."\n"
?>
PostScript
/ack {
2 index 0 eq {
1 add exch pop exch pop
} {
dup 0 eq {
pop exch dup 1 eq {
pop
} {
2 eq {0} {1} ifelse exch pop
} ifelse
} {
1 sub 2 index exch 2 index exch ack 3 2 roll 1 sub 3 1 roll ack
} ifelse
} ifelse
} def
1 1 5000 ack = quit
Prolog
% time gprolog --init-goal "['ack.pro'],ack"
% time swipl -g "['ack.pro'],ack"
ack :- ack(5,2,3,R), write(R), nl,!,halt.
ack(N,X,Y,R) :- N=0, R is Y+1,!;
Y=0, (N=1,R=X,!;
N=2,R=0,!;
R=1,!);
Y1 is Y-1, ack(N,X,Y1,R1),
N1 is N-1, ack(N1,X,R1,R).
Python
def ack(n, x, y):
if n == 0: return y + 1
if y == 0:
if n == 1: return x
if n == 2: return 0
return 1
return ack(n - 1, x, ack(n, x, y - 1))
print ack(1, 1, 1000)
Ruby
def ack(n,x,y)
if n == 0
y + 1
elsif y == 0
if n == 1
x
elsif n == 2
0
else
1
end
else
ack(n - 1, x, ack(n, x, y - 1))
end
end
print ack(1,1,6600), "\n"
TCL
proc ack {n x y} {
if $n==0 {return [expr $y+1]}
if $y==0 {
if $n==1 {return $x}
if $n==2 {return 0}
return 1
}
ack [expr $n-1] $x [ack $n $x [expr $y-1]]
}
puts [ack 1 1 999]
TEX
\def\ack#1#2#3{%n,x,y
\ifcase#1\count0=#3\advance\count0by1%
\else\ifcase#3\ifcase#1
\or\count0=#2%
\or\count0=0%
\else\count0=1\fi
\else\count1=#3\advance\count1by-1%
\edef\p{{#1}{#2}{\the\count1}}%
\expandafter\ack\p
\count1=#1\advance\count1by-1%
\edef\p{{\the\count1}{#2}{\the\count0}}%
\expandafter\ack\p
\fi\fi}
\ack1{1}{3400}\message{\the\count0}
\bye