I use the following six algorithms:fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
-- Mathematical Handbook 2nd ed., G. Korn, T. Korn, 1968. paragraph 8.7-2
Please note that some programmers, including Donald Knuth (volume 1), use a slightly different definition. The conversion between the two is trivial.
F(n) = F(n/2)2 + F(n/2-1)2 if n mod 2 = 0
F(n) = F(n-1/2)*F(n-1/2+1) + F(n-1/2)*F(n-1/2-1) if n mod 2 = 1
This gives us an algorithm:
The function λ(n) takes one number and returns two: F(n-1) and F(n). λ(n) recursively calls λ(n/2-1) if n is even λ(n) recursively calls λ((n-1)/2) if n is odd λ(n) takes the results of the call and calculates F(n) and F(n-1) using the two equations above. The recursion ends when n is 0, 1, or 2. The front-end function F(n) simply calls the function λ(n) and returns F(n).
Simply evaluate the following expression: | F(2n) | | 1 | | 1 1 | | | = A^n * | |, where A = | | | F(2n+1) | | 1 | | 1 2 |Not too many languages support matrix arithmetics right now, which makes most of the examples featuring this algorithm rather bulky. Still, it's a very elegant way to calculate Fibonacci numbers.
| Binary Recursion (the slowest) algorithm for the 45th Fibonacci number | ||
| Language | Translator [*] | Time, seconds |
|---|---|---|
| Assembly | GNU as 2.12.90.0.9 [c] | 32.25 |
| C | GNU gcc 2.95.3 [c] | 44.72 |
| Forth | Tektronix PFE 0.32.94 [i] | 594.92 |
| Joy | Joy1 by Manfred von Thun [i] | 1331.05 |
| PostScript | ESP Ghostscript 7.07.1 [i] | 1555.62 |
| MUF | FuzzBall MUCK 6.01 [b] | 4048.00 |
| Twice Recursive (slow) algorithms for 35th Fibonacci number | ||
| Language | Translator [*] | Time, seconds |
|---|---|---|
| Assembly | GNU as 2.9.1 [c] | 0.63 |
| Caml | Objective Caml 2.99 [c] | 0.74 |
| C | GCC 2.95.1 [c] | 0.92 |
| C++ | G++ 2.95.1 [c] | 0.99 |
| Scheme | MIT Scheme 7.5.0 [b] | 1.94 |
| Java | JDK 1.1.7B [b] | 10.17 |
| Forth | ThisForth 1.0.0d [i] | 14.57 |
| Haskell | NHC98 1.0 pre-prelease 14 [c] | 36.05 |
| PostScript | GhostScript 5.10 [i] | 42.98 |
| Joy | Joy0 by Manfred von Thun [i] | 50.41 |
| Perl | perl 5.005_003 [i] | 114.05 |
| Prolog | SWI-Prolog 3.3.10 [b] | 120.44 |
| AWK | by Brian Kernighan [i] | 212.30 |
| Hope | by Ross Paterson [i] | 512.46 |
| Tcl | TCL 8.2 [i] | 1468.49 |
| sh | GNU bash 1.14 [i] | 8792.43 |
| Fast algorithms for 50000th Fibonacci number (10451 decimal digits) | |||||
| Language | Infinite list | Once recursive | Non-recursive | Fast recursive | Matrix equation |
|---|---|---|---|---|---|
| Haskell | 2.83 | 2.68 | n/a | 1.48 | 1.51 |
| Scheme | mem | 4.79 | 4.82 | 0.19 | 0.53 |
| Java | 10.0 | 10.7 | 7.88 | 0.44 | 0.77 |
| perl | mem | mem | 1859.42 | 24.99 | 119.25 |
| Featured languages | ||||
| Concatenative | Logic | Functional | Object | Imperative |
|---|---|---|---|---|
|
Forth PostScript MUF Joy | Prolog |
Hope Scheme Caml Haskell |
Java C++ |
Fortran C AWK perl Tcl sh Assembly Languages |
Bugs, comments, and frequently asked questions
: fib ( n -- n ) DUP 2 U< IF DROP 1 EXIT THEN 1- DUP 1- RECURSE SWAP RECURSE + ; : fib45 ( -- ) ." 45th Fibonacci number is " 45 fib U. CR ; fib45Infinite List
: list_put ( a i -- )
OVER 1 CELLS + @ 0= IF
2 CELLS ALLOCATE THROW TUCK !
DUP ROT 1 CELLS + !
0 SWAP 1 CELLS + !
ELSE SWAP 1 CELLS + @ SWAP RECURSE THEN
;
: list_get ( a i -- n )
1+ OVER SWAP
0 DO DUP 1 CELLS + @
0= IF I 1- ROT TUCK SWAP RECURSE
SWAP DUP DUP I 2 - RECURSE
2SWAP SWAP ROT + list_put SWAP
THEN 1 CELLS + @
LOOP @ NIP
;
: fib ( n -- n )
2 CELLS ALLOCATE THROW 1 OVER ! 0 OVER 1 CELLS + !
DUP 1 list_put DUP 1 list_put
SWAP list_get
;
: fib45 ( -- )
." 45th Fibonacci number is " 45 fib U. CR
;
fib45
Simple Recursion
: lambda ( n1 n2 ni -- n ) ROT 1- DUP 0 U> INVERT IF 2DROP EXIT THEN OVER 2SWAP + RECURSE ; : fib ( n -- n ) 1 2 lambda ; : fib45 ( -- ) ." 45th Fibonacci number is " 45 fib U. CR ; fib45Non-recursive Loop
: fib ( n -- n ) 1 1 ROT 1 DO SWAP OVER + LOOP SWAP DROP ; : fib45 ( -- ) ." 45th Fibonacci number is " 45 fib U. CR ; fib45Fast Recursive
: lambda ( n -- n1 n2 )
DUP 2 U< IF DROP 1 1 ELSE
DUP 2 = IF DROP 2 1 ELSE
2 /MOD SWAP IF RECURSE
2DUP OVER * 2OVER + ROT * +
ROT DUP * ROT DUP * +
ELSE 1- RECURSE
2DUP OVER + TUCK * 2SWAP OVER * ROT +
ROT DUP * ROT DUP * + SWAP
THEN THEN THEN
;
: fib ( n -- n )
lambda DROP
;
: fib45 ( -- )
." 45th Fibonacci number is " 45 fib U. CR
;
fib45
Matrix Equation
: mmult ( A B -- C ) OVER 7 PICK * 8 PICK 5 PICK * + OVER 8 ROLL * 4 PICK 9 ROLL * + 3 ROLL 6 PICK * 7 PICK 6 ROLL * + 3 ROLL 5 ROLL * 4 ROLL 5 ROLL * + ; : mswap ( A B -- B A ) 7 ROLL 7 ROLL 7 ROLL 7 ROLL ; : mover ( A B -- A B A ) 7 PICK 7 PICK 7 PICK 7 PICK ; : fib ( n -- n ) 2 /MOD 1 2 1 1 1 1 0 0 1 9 PICK 9 PICK AND 0<> IF 2DROP 2DROP 2OVER 2OVER THEN BEGIN 8 PICK 10 PICK < WHILE mswap 2OVER 2OVER mmult mswap 8 ROLL 2* 9 1 DO 8 ROLL LOOP 9 PICK 9 PICK AND 0<> IF mover mswap mmult THEN REPEAT mswap 2DROP 2DROP 2DROP 2SWAP 2DROP ROT 0= IF DROP ELSE + THEN ; : fib45 ( -- ) ." 45th Fibonacci number is " 45 fib U. CR ;
/fib {dup 1 le {pop 1} {1 sub dup 1 sub fib exch fib add} ifelse} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (45th Fibonacci number is ) show
45 fib 10 string cvs show
showpage
Infinite List
/fib {dup 0 ne
{ dup 1 add array dup 0 1 put dup 1 1 put exch 2 exch 1 sub
{ dup 3 2 roll dup 3 2 roll 1 sub get 1 index 3 index 2 sub get
add 1 index exch 3 index exch put exch 1 add
} repeat 1 sub get
} {pop 1} ifelse
} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (45th Fibonacci number is ) show
45 fib 10 string cvs show
showpage
Simple Recursion
/fib-lambda {3 -1 roll 1 sub dup 0 le {pop pop}
{3 1 roll dup 3 2 roll add fib-lambda} ifelse
} def
/fib {1 2 fib-lambda} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (45th Fibonacci number is ) show
45 fib 10 string cvs show
showpage
Non-recursive Loop
/fib {dup 0 gt {1 sub} if 1 1 3 2 roll {dup 3 2 roll add} repeat exch pop} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (45th Fibonacci number is ) show
45 fib 10 string cvs show
showpage
Fast Recursion
/fib-lambda { dup 1 le {pop 1 1} {
dup 2 eq {pop 2 1} {
dup 2 mod 1 eq {
1 sub -1 bitshift fib-lambda
dup dup dup mul 4 -1 roll
dup dup dup dup mul 5 -1 roll
add exch 5 -1 roll add 3 -1 roll
mul 4 -2 roll mul add exch
} {
-1 bitshift 1 sub fib-lambda
dup 3 -1 roll dup dup dup dup
6 -1 roll add dup dup mul
4 -2 roll mul add 5 -2 roll mul
4 -2 roll mul add
} ifelse
} ifelse
} ifelse
} def
/fib {fib-lambda pop} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (45th Fibonacci number is ) show
45 fib 10 string cvs show
showpage
Matrix Equation
/mmult {
1 index 7 index mul 8 index 5 index mul add
1 index 9 -1 roll mul 4 index 10 -1 roll mul add
4 -1 roll 6 index mul 7 index 7 -1 roll mul add
4 -1 roll 6 -1 roll mul 5 -1 roll 6 -1 roll mul add
} def
/mswap { 8 -1 roll 8 -1 roll 8 -1 roll 8 -1 roll } def
/mover { 7 index 7 index 7 index 7 index } def
/mdup { 3 index 3 index 3 index 3 index } def
/fib {
dup 2 mod exch -1 bitshift 1 2 1 1 1 1 0 0 1
9 index 9 index and 0 ne { pop pop pop pop mdup } if
{ 8 index 10 index ge {exit} if mswap mdup mmult mswap
9 -1 roll 1 bitshift 9 1 roll
9 index 9 index and 0 ne {mover mswap mmult} if
} loop
mswap pop pop pop pop pop pop 3 -1 roll pop 3 -1 roll pop
3 -1 roll 0 eq {pop} {add} ifelse
} def
/Times-Roman findfont
20 scalefont setfont newpath 72 72 moveto (45th Fibonacci number is ) show
45 fib 10 string cvs show
showpage
: fib ( n -- n ) dup 2 < if pop 1 exit then 1 - dup 1 - fib swap fib + ; : fib45 ( -- ) me @ "45th Fibonacci number is " 45 fib intostr strcat notify ;Infinite list:
: fib-get ( n -- n )
dup intostr "fib/" swap strcat me @ swap getpropval
dup 0 = if
pop dup 1 - dup fib-get swap 1 - fib-get +
"fib/" rot intostr strcat me @ swap "" 4 pick addprop
else swap pop then
;
: fib ( n -- n )
me @ "fib/0" "" 1 addprop
me @ "fib/1" "" 1 addprop
fib-get
;
: fib45 ( -- )
me @ "45th Fibonacci number is " 45 fib intostr strcat notify
;
Simple Recursion
: fib-lambda ( ni n2 n1 -- n ) rot 1 - dup 0 > not if pop pop exit then swap rot over + fib-lambda ; : fib ( n -- n ) 1 2 fib-lambda ; : fib45 ( -- ) me @ "45th Fibonacci number is " 45 fib intostr strcat notify ;Non-recursive Loop
: fib ( n -- n )
1 1 rot begin
1 - dup 0 > while
swap rot over + rot
repeat pop swap pop
;
: fib45 ( -- )
me @ "45th Fibonacci number is " 45 fib intostr strcat notify
;
Fast Recursion
: fib-lambda ( n -- n1 n2 )
dup 2 < if pop 1 1 else
dup 2 = if pop 2 1 else
dup 2 / swap 2 % if fib-lambda
dup 3 pick + 3 pick * over 4 pick * +
swap dup * rot dup * +
else 1 - fib-lambda
dup 3 pick + dup 4 pick * rot 4 pick * +
swap dup * rot dup * + swap
then then then
;
: fib ( n -- n )
fib-lambda pop
;
: fib45 ( -- )
me @ "45th Fibonacci number is " 45 fib intostr strcat notify
;
Matrix Equation
: mmult ( A B -- C ) over 8 pick * 9 pick 6 pick * + over 9 rotate * 5 pick 10 rotate * + 4 rotate 7 pick * 8 pick 7 rotate * + 4 rotate 6 rotate * 5 rotate 6 rotate * + ; : mswap ( A B -- B A ) 8 rotate 8 rotate 8 rotate 8 rotate ; : mover ( A B -- A B A ) 8 pick 8 pick 8 pick 8 pick ; : mpop ( A -- ) pop pop pop pop ; : mdup ( A -- A A ) 4 pick 4 pick 4 pick 4 pick ; : fib ( n -- n ) dup 2 % swap 2 / 1 2 1 1 1 1 0 0 1 10 pick 10 pick bitand 0 = not if mpop mdup then begin 10 pick 10 pick < not while mswap mdup mmult mswap 9 rotate 2 * 8 begin dup while 10 rotate swap 1 - repeat pop 10 pick 10 pick bitand 0 = not if mover mswap mmult then repeat mswap mpop pop pop rot pop rot pop rot 0 = if pop else + then ; : fib45 ( -- ) me @ "45th Fibonacci number is " 45 fib intostr strcat notify ;
"45th Fibonacci number is " [putch] step 45 [small] [pop 1] [pred dup pred] [+] binrec .Infinite List
"45th Fibonacci number is " [putch] step 45 [1 1] [size >=] [dup dup size pred dupd dup swapd at [pred at] dip + [] cons concat] while of .Simple Recursion
"45th Fibonacci number is " [putch] step 45 [1 1] dip [small] [pop swap pop] [pred [dup [swap] dip +] dip] tailrec .Non-recursive Loop
"45th Fibonacci number is " [putch] step 45 [1 1] dip [dup [+] dip swap] times pop .Fast Recursion
"45th Fibonacci number is " [putch] step 45 [[[2 <][pop 1 1]] [[2 =][pop 2 1]] [[2 rem 1 =] [pred 2 /] [ dupd dupd dupd dup [+ *] dip swapd dup [* +] dip dup * rolldown dup * + ]] [[2 rem 0 =] [2 / pred] [ dupd dupd dup [+ dup dup * rolldown dup * + rotate] dip dupd * rollup * + ]] [[]] ] condlinrec pop.Matrix Equation
"mtrlib" libload. "45th Fibonacci number is " [putch] step 45 2 div null swap [[2 1] [1 1]] [[1 0] [0 1]] rolldown 2 div rollupd null [dupd] dip rotate choice [[dupd] dip rolldown null ] [[pop2] dip dup first first swap first second dupd + choice ] [[ dup mm-mul-m ] dip rolldown 2 div rollupd null [] [ dupd mm-mul-m ] branch ] tailrec .
fib(0,1).
fib(1,1).
fib(N,F) :-
N>1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+F2.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Infinite list:
flist(_,N,[1,1]) :- N<2.
flist(L1,N,[T|L1]) :-
length(L1,FLL), N =:= FLL, N1 is FLL-N+1, nth1(N1,L1,T1),
N2 is FLL-N+2, nth1(N2,L1,T2), T is T1+T2.
flist(L1,N,L2) :-
length(L1,FLL), N>FLL, N3 is N-1, flist(L1,N3,L3), flist(L3,N,L2).
fib(N,F) :-
flist([1,1],N,FL), length(FL,FLL), N1 is FLL-N, nth1(N1,FL,F).
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Once recursive:
fib(N,F) :- fib_lambda(1,1,N,F).
fib_lambda(F1,F2,N,F):-
N1>1, F3 is F1+F2, N2 is N-1, fib_lambda(F3,F1,N2,F);
N1<2, F is F1.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Non-recursive:
Not ApplicableFast recursive:
fib(N,F) :- fl(N,[F|_]).
fl(N,[F1|F2]) :-
N < 2, F1 is 1, F2 is 1;
N =:= 2, F1 is 2, F2 is 1;
Z1 is N mod 2, Z1 =:= 1, A1 is (N-1)/2, fl(A1,[K1|K2]),
F1 is K1*(K1+K2)+K1*K2, F2 is K1*K1+K2*K2;
Z1 is N mod 2, Z1 =:= 0, A2 is (N/2)-1, fl(A2,[L1|L2]),
F1 is (L1+L2)*(L1+L2)+L1*L1, F2 is (L1+L2)*L1+L1*L2.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
Matrix equation:
fib(N,F) :-
Z1 is N mod 2, Z1 =:= 0, mpow(N,[2,1,1,1],[1,0,0,1],_,C), nth1(1,C,F);
Z1 is N mod 2, Z1 =:= 1, mpow(N,[2,1,1,1],[1,0,0,1],_,C),
nth1(1,C,F1), nth1(2,C,F2), F is F1+F2.
mpow(N,A1,C1,A2,C2) :-
NH is N//2, T is NH /\ 1, T =:= 0, mpow(NH,1,A1,C1,A2,C2);
NH is N//2, T is NH /\ 1, T =\= 0, mpow(NH,1,A1,A1,A2,C2).
mpow(NH,BIT,A1,C1,A1,C1) :- BIT >= NH.
mpow(NH,BIT,A1,C1,A2,C2) :-
BIT < NH, mmult(A1,A1,AN), BIT2 is BIT*2, T is NH /\ BIT2,
T =\= 0, mmult(AN,C1,CN), mpow(NH,BIT2,AN,CN,A2,C2);
BIT < NH, mmult(A1,A1,AN), BIT2 is BIT*2, T is NH /\ BIT2,
T =:= 0, mpow(NH,BIT2,AN,C1,A2,C2).
mmult([A11,A12,A21,A22],[B11,B12,B21,B22],[C11,C12,C21,C22]) :-
C11 is A11*B11+A12*B21, C12 is A11*B12+A12*B22,
C21 is A21*B11+A22*B21, C22 is A21*B12+A22*B22.
fibb :-
write('35th Fibonacci number is '), fib(35,X), write(X), nl.
fibb.
dec fib : num -> num; --- fib 0 <= 1; --- fib 1 <= 1; --- fib(n+2) <= fib n + fib(n+1); write "35th Fibonacci number is "; write [fib 35];Infinite list:
uses lists; dec fibs : list num; --- fibs <= fs whererec fs == 1::1::map (+) (tail fs||fs); write "35th Fibonacci number is "; write [fibs@35];Once recursive:
dec fib : num -> num;
--- fib n <= fl(1,1,n)
whererec fl == \(a,b,c) => if c<2 then a else fl(a+b,a,c-1);
write "35th Fibonacci number is ";
write [fib 35];
Non-recursive:
Not ApplicableFast recursive:
dec fib : num -> num;
--- fib n <= a where (a,b) == fl(n)
whererec fl == \(n) => if n<2 then (1,1) else
if n=2 then (2,1) else
if n mod 2 = 1 then
(k1*(k1+k2)+k1*k2,k1*k1+k2*k2)
else
((l1+l2)*(l1+l2)+l1*l1,(l1+l2)*l1+l1*l2)
where (k1,k2) == fl((n-1)/2)
where (l1,l2) == fl((n/2)-1);
write "35th Fibonacci number is ";
write [fib 35];
Matrix equation:
uses lists;
dec bitandnotzero : num # num -> bool;
--- bitandnotzero (a,b) <=
if (a mod 2) + (b mod 2) = 2 then true
else if a=0 and b=0 then false
else bitandnotzero(a div 2,b div 2);
dec mmult : list(num) # list(num) -> list(num);
--- mmult([a11,a12,a21,a22],[b11,b12,b21,b22]) <=
[a11*b11+a12*b21 ,a11*b12+a12*b22 ,a21*b11+a22*b21 ,a21*b12+a22*b22];
dec mpow : num # list(num) # list(num) -> list(num) # list(num);
--- mpow(n,A,C) <= if bitandnotzero(n div 2,1) then mpow_l(n div 2,1,A,A)
else mpow_l(n div 2,1,A,C)
whererec mpow_l == \(nh,bit,A,C) =>
if bit >= nh then (A,C) else
if bitandnotzero(nh,(bit*2)) then
mpow_l(nh,bit*2,mmult(A,A),mmult(mmult(A,A),C))
else mpow_l(nh,bit*2,mmult(A,A),C);
dec fib : num -> num;
--- fib n <= if (n mod 2) = 0 then l@0 else l@0 + l@1
where (a,l) == mpow(n,[2,1,1,1],[1,0,0,1]) ;
write "35th Fibonacci number is ";
write [fib 35];
(define (fib n) (if (< n 2) 1 (+ (fib (- n 1)) (fib(- n 2))))) (write-string "35th Fibonacci number is ") (write-line (fib 35))Infinite list
(define (z-incr k)
(append k (list (+ (list-ref k (- (length k) 1))
(list-ref k (- (length k) 2))))))
(define (fibl n l)
(if (< n (length l))
(list-ref l n)
(fibl n (z-incr l))))
(define (fib n)
(fibl n '(1 1)))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
Once recursive
(define (fib n) (define (fl a b c) (if (< c 2) a (fl (+ a b) a (- c 1)))) (fl 1 1 n)) (write-string "35th Fibonacci number is ") (write-line (fib 35))Non-recursive
(define (fib n)
(do ((x1 1) (x2 1) (tmp 1) (i 1 (+ i 1))) ((> i n) x1)
(set! tmp (+ x1 x2))
(set! x1 x2)
(set! x2 tmp)))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
Fast recursive
(define (fib n)
(define (fl n)
(if (< n 2) (cons 1 1)
(if (= n 2) (cons 2 1)
(if (= (modulo n 2) 1)
(let ((k (fl (/ (- n 1) 2))))
(let ((k1 (car k)) (k2 (cdr k)))
(cons (+ (* k1 (+ k1 k2)) (* k1 k2))
(+ (* k1 k1) (* k2 k2)))))
(let ((k (fl (- (/ n 2) 1))))
(let ((k1 (car k)) (k2 (cdr k)))
(cons (+ (* (+ k1 k2) (+ k1 k2)) (* k1 k1))
(+ (* k1 (+ k2 k1)) (* k1 k2)))))))))
(car (fl n)))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
Matrix equation
(define (mmult l1 l2)
(cons (cons (+ (* (car (car l1)) (car (car l2)))
(* (cdr (car l1)) (car (cdr l2))))
(+ (* (car (car l1)) (cdr (car l2)))
(* (cdr (car l1)) (cdr (cdr l2)))))
(cons (+ (* (car (cdr l1)) (car (car l2)))
(* (cdr (cdr l1)) (car (cdr l2))))
(+ (* (car (cdr l1)) (cdr (car l2)))
(* (cdr (cdr l1)) (cdr (cdr l1)))))))
(define (fib n)
(define (mpow_l nh bit l1 l2)
(if (>= bit nh)
(cons l1 l2)
(if (zero? (fix:and nh (* 2 bit)))
(mpow_l nh (* 2 bit) (mmult l1 l1) l2)
(mpow_l nh (* 2 bit) (mmult l1 l1) (mmult (mmult l1 l1) l2)))))
(define (mpow n l1 l2)
(if (zero? (fix:and 1 (quotient n 2)))
(mpow_l (quotient n 2) 1 l1 l2)
(mpow_l (quotient n 2) 1 l1 l1)))
(define l1 (cdr (mpow n '((2 . 1) 1 . 1)
'((1 . 0) 0 . 1))))
(if (zero? (modulo n 2)) (car (car l1))
(+ (car (car l1)) (car (cdr l1)))))
(write-string "35th Fibonacci number is ")
(write-line (fib 35))
let rec fib = function 0 -> 1 | 1 -> 1 | x -> fib(x-1) + fib(x-2);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Infinite list:
let rec fib ?(:l=[1;1]) n =
try List.nth l n with Failure "nth" ->
fib l:(l@[(fib l:l (List.length(l)-1))
+ (fib l:l (List.length(l)-2))]) n;;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Once recursive:
let rec fib ?(:a=1) ?(:b=1) n =
if n<2 then a else fib a:(a+b) b:a (n-1);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Non-recursive:
let fib n =
let x1 = ref 1 in
let x2 = ref 1 in
let tmp = ref 0 in
for i = 1 to n do
tmp := !x1 + !x2;
x1 := !x2;
x2 := !tmp;
done;
!x1;;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Fast recursive:
let fib n = let rec fl n =
if n<2 then (1,1) else
if n=2 then (2,1) else
if (n mod 2) = 1 then
let (k1,k2) = fl((n-1)/2) in (k1*(k1+k2)+k1*k2,k1*k1+k2*k2)
else
let (l1,l2) = fl((n/2)-1) in ((l1+l2)*(l1+l2)+l1*l1,(l1+l2)*l1+l1*l2)
in fst (fl n);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
Matrix equation:
let fib n =
let mmult = function
[a11;a12;a21;a22],[b11;b12;b21;b22] ->
[a11*b11+a12*b21;a11*b12+a12*b22;a21*b11+a22*b21;a21*b12+a22*b22]
| _,_ -> [] in
let rec mpow_l(nh,bit,l1,l2) =
if bit >= nh then (l1,l2) else
let l11 = mmult(l1,l1) in
if ((bit*2) land nh)<>0
then mpow_l(nh,bit*2,l11,mmult(l11,l2))
else mpow_l(nh,bit*2,l11,l2) in
let mpow(n,l1,l2) =
if ((n/2) land 1)<>0 then mpow_l(n/2,1,l1,l1)
else mpow_l(n/2,1,l1,l2) in
let (_,l) = mpow(n,[2;1;1;1],[1;0;0;1]) in
if (n mod 2) = 0 then List.hd l
else List.hd l + List.hd (List.tl l);;
let main () = print_string("35th Fibonacci number is ");
print_int(fib 35);
print_newline();
exit 0;;
main ();;
module Main where
fib :: Int -> Int
fib x | x < 2 = 1
| x >= 2 = fib (x-1) + fib (x-2)
main = print ("35th Fibonacci number is " ++ show (fib 35))
Infinite List:
module Main where
fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)
main = print ("35th Fibonacci number is " ++ show (fib!!35))
Once recursive:
module Main where
fib :: Int -> Integer
fib n = fl 1 1 n where
fl :: Integer -> Integer -> Int -> Integer
fl a b c = if c<2 then a else fl (a+b) a (c-1)
main = print ("35th Fibonacci number is " ++ show (fib 35))
Non-recursive:
Not ApplicableFast recursive:
module Main where
fib :: Int -> Integer
fib n = fst (fl n) where
fl :: Int -> (Integer,Integer)
fl n | n<2 = (1,1)
| n==2 = (2,1)
| n>2 = if (rem n 2)==1 then (k1*(k1+k2)+k1*k2, k1*k1+k2*k2)
else ((l1+l2)*(l1+l2)+l1*l1, (l1+l2)*l1+l1*l2)
where (k1,k2) = fl (div (n-1) 2)
(l1,l2) = fl ((div n 2)-1)
main = print ("35th Fibonacci number is " ++ show (fib 35))
Matrix equation:
module Main where
fib :: Int -> Integer
fib n = if (mod n 2)==0 then head l else head l + head (tail l)
where (_,l) = mpow n [2,1,1,1] [1,0,0,1]
mpow :: Int -> [Integer] -> [Integer] -> ([Integer],[Integer])
mpow n l1 l2 = if bitandnz (div n 2) 1 then mpow_l (div n 2) 1 l1 l1
else mpow_l (div n 2) 1 l1 l2
mpow_l :: Int -> Int -> [Integer] -> [Integer] -> ([Integer],[Integer])
mpow_l nh bit a c = if bit >= nh then (a,c)
else if bitandnz nh (bit*2) then
mpow_l nh (bit*2) ama (mmult ama c)
else mpow_l nh (bit*2) ama c
where ama = mmult a a
bitandnz :: Int -> Int -> Bool
bitandnz a b = if (mod a 2)+(mod b 2)==2 then True
else if (a==0) && (b==0) then False
else bitandnz (div a 2) (div b 2)
mmult :: [Integer] -> [Integer] -> [Integer]
mmult [a11,a12,a21,a22] [b11,b12,b21,b22] =
[a11*b11+a12*b21, a11*b12+a12*b22, a21*b11+a22*b21, a21*b12+a22*b22]
main = print ("35th Fibonacci number is " ++ show (fib 35))
class fib {
private static long fib(long n) {
return n<2 ? 1 : fib(n-2)+fib(n-1);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Infinite list:
import java.math.BigInteger;
import java.util.Vector;
class FibArray {
private static Vector numbers;
public FibArray() {
numbers=new Vector();
numbers.addElement(new BigInteger("1"));
numbers.addElement(new BigInteger("1"));
}
public static BigInteger elementAt(int index) {
try {
return (BigInteger)numbers.elementAt(index);
} catch (ArrayIndexOutOfBoundsException r) {
numbers.addElement(
((BigInteger)numbers.elementAt(numbers.size()-2)).add(
(BigInteger)numbers.elementAt(numbers.size()-1))
);
return (elementAt(index-1).add(elementAt(index-2)));
}
}
}
class fib {
private static BigInteger fib(int n) {
return (new FibArray()).elementAt(n);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Once recursive:
import java.math.BigInteger;
class fib {
private static BigInteger fib_lambda(BigInteger x1, BigInteger x2, long c) {
return c<2 ? x1 : fib_lambda(x1.add(x2), x1, c-1);
}
private static BigInteger fib(long n) {
return fib_lambda(new BigInteger("1"),new BigInteger("1"),n);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Non-recursive:
import java.math.BigInteger;
class fib {
private static BigInteger fib(long n) {
BigInteger x1 = new BigInteger("1");
BigInteger x2 = new BigInteger("1");
BigInteger tmp;
for(long i=1;i<=n;i++) {
tmp=x1.add(x2);
x1=x2; x2=tmp;
}
return x1;
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Fast recursive
import java.math.BigInteger;
class fib {
private static BigInteger[] fl(long n) {
BigInteger[] k = new BigInteger[2];
BigInteger[] l = new BigInteger[2];
if(n<2) { k[0]=new BigInteger("1"); k[1]=new BigInteger("1"); return k; }
if(n==2) { k[0]=new BigInteger("2"); k[1]=new BigInteger("1"); return k; }
if((n%2)==1) {
k = fl((n-1)/2);
l[0]=k[0].multiply((k[0].add(k[1]))).add(k[0].multiply(k[1]));
l[1]=k[0].multiply(k[0]).add(k[1].multiply(k[1]));
} else {
k = fl((n/2)-1);
l[0]=(k[0].add(k[1])).multiply((k[0].add(k[1]))).add(k[0].multiply(k[0]));
l[1]=(k[0].add(k[1])).multiply(k[0]).add(k[0].multiply(k[1]));
}
return l;
}
private static BigInteger fib(long n) { return fl(n)[0]; }
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
Matrix equation
import java.math.BigInteger;
class fib {
private static BigInteger[][] matrix_mult(BigInteger[][] a,BigInteger[][] b)
{
BigInteger[][] c = new BigInteger[a.length][b[0].length];
for(int i=0;i<a.length;i++)
for(int j=0;j<b[0].length;j++) {
c[i][j] = new BigInteger("0");
for(int k=0;k<b.length;k++)
c[i][j] = c[i][j].add(a[i][k].multiply(b[k][j]));
}
return c;
}
private static BigInteger fib(int n) {
BigInteger[][] a = {{new BigInteger("2"),new BigInteger("1")},
{new BigInteger("1"),new BigInteger("1")}};
BigInteger[][] c = {{new BigInteger("1"),new BigInteger("0")},
{new BigInteger("0"),new BigInteger("1")}};
int nh=n/2; int bit=1;
if ((nh&bit)!=0) c=a;
while(bit<nh) {
a=matrix_mult(a,a);
bit<<=1;
if((nh&bit)!=0)
c=matrix_mult(a,c);
}
return (n%2)==0 ? c[0][0] : c[0][0].add(c[1][0]);
}
public static void main(String argv[]) {
System.out.println("35th Fibonacci number is " + fib(35));
}
}
#include <iostream>
using namespace std;
long fib(int x)
{
return x<2 ? 1 : fib(x-1) + fib(x-2);
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Infinite list:
#include <iostream>
#include <stl.h>
using namespace std;
long fib(int x)
{
vector<long> fib(2);
fib[0]=1;
fib[1]=1;
fib.reserve(x);
while(x>=fib.size())
fib.push_back(*(fib.end()-2) + *(fib.end()-1));
return fib[x];
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Once recursive:
#include <iostream>
using namespace std;
long fib(int x, long n1 = 1, long n2 = 1)
{
return x<2 ? n1 : fib(x-1,n2+n1,n1);
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Non recursive:
#include <iostream>
#include <stl.h>
using namespace std;
long fib(int x)
{
long x1=1;
for(long i=1,x2=1;i<=x;i++) {
x1+=x2;
swap(x1,x2);
}
return x1;
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Fast recursive:
#include <iostream>
using namespace std;
struct fib_pair {
long n1,n2;
fib_pair(long a = 1, long b = 1) { n1=a; n2=b; }
};
fib_pair* fl(int x)
{
if(x<=1) return new fib_pair;
if(x==2) return new fib_pair(2,1);
if(x%2) {
fib_pair* k = fl((x-1)/2);
return new fib_pair(k->n1*(k->n1+k->n2) + k->n1*k->n2
,k->n1*k->n1 + k->n2*k->n2);
} else {
fib_pair* k = fl((x/2)-1);
return new fib_pair( (k->n1+k->n2)*(k->n1+k->n2) + k->n1*k->n1
,(k->n1+k->n2)*k->n1 + k->n1*k->n2);
}
}
long fib(int x)
{
return fl(x)->n1;
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
Matrix equation:
#include <iostream>
#include <vector>
using namespace std;
template<class T>
class Matrix {
private:
vector<vector<T> > data;
public:
Matrix(int size) : data(vector<vector<T> >(size,vector<T>(size,0))) {}
size_t size(void) const { return data.size(); }
vector<T> & operator[] (int i) { return data[i]; }
const vector<T> & operator[] (int i) const { return data[i]; }
const Matrix operator*(const Matrix& b) const {
Matrix c(data.size());
for(int i=0; i<data.size(); i++)
for(int j=0; j<data.size(); j++)
for(int k=0; k<data.size(); k++)
c[i][j]+=data[i][k]*b[k][j];
return c;
}
};
long fib(int x)
{
Matrix<int> a(2); Matrix<int> b(2);
a[0][0]=2; a[0][1]=a[1][0]=a[1][1]=1;
b[0][0]=b[1][1]=1; b[0][1]=b[1][0]=0;
int nh = x/2; int bit=1;
if(nh&bit) b=a;
while(bit<nh) {
a=a*a; bit<<=1;
if(nh&bit) b=a*b;
}
return x%2 ? b[0][0]+b[0][1] : b[0][0];
}
int main()
{
cout << "35th Fibonacci number is " << fib(35) << endl;
return 0;
}
PROGRAM FIB19
INTEGER*4 I
I=19
CALL FIB (I)
PRINT *,'19th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
DIMENSION A(2**I), B(2**I)
DO1J=1,2**I
A(J)=0; B(J)=0
1 CONTINUE
A(1)=I+1;
IP=0;
4 J2=1
DO2J=1,2**IP
B(J2)=A(J)-1
B(J2+1)=A(J)-2
J2=J2+2
2 CONTINUE
DO3J=1,2**I
A(J)=B(J)
3 CONTINUE
IP=IP+1
IF(A(1).GT.1) GO TO 4
9 IP=IP-1
J2=1
DO5J=1,2**(IP-1)
IF(A(J2+1)-0)10,10,12
10 B(J)=A(J2)+1
GO TO 7
12 B(J)=A(J2)+A(J2+1)
7 J2=J2+2
5 CONTINUE
DO8J=1,2**(I-1)
A(J)=B(J)
8 CONTINUE
IF(IP.GT.1) GO TO 9
I=A(1)
RETURN
END SUBROUTINE
Infinite list:
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *,'35th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
DIMENSION A(I+1)
A(1)=1; A(2)=1
DO1J=3,I+1
A(J)=A(J-1)+A(J-2)
1 CONTINUE
I=A(I+1)
RETURN
END SUBROUTINE
Once recursive
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *, '35th Fibonacchi number is ', I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
I1=1; I2=1
DO 2 J=2,I
I3=I1+I2
I2=I1
I1=I3
2 I=I1
RETURN
END SUBROUTINE
Fast recursive
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *,'35th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
J1=LOG(I+1.)/LOG(2.)
JL=2**J1-2
JR=2**(J1+1)-2
JM=(JL+JR)/2
IF(I-JM)2,2,1
1 JL=JM
I1=2; I2=1; N=2
GO TO 3
2 JR=JM
I1=1; I2=1; N=1
3 IF(N-I)11,7,7
11 JM=(JL+JR)/2
IF(I-JM)5,5,4
4 JL=JM
N=(N+1)*2
ITMP=(I1+I2)**2+I1**2
I2=(I1+I2)*I1+I1*I2
I1=ITMP
GO TO 6
5 JR=JM
N=2*N+1
ITMP=I1*(I1+I2)+I1*I2
I2=I1**2+I2**2
I1=ITMP
6 IF(N-I)11,7,7
7 I=I1
RETURN
END SUBROUTINE
Matrix equation
PROGRAM FIB35
I=35
CALL FIB (I)
PRINT *,'35th Fibonacci number is',I
STOP
END PROGRAM
C
SUBROUTINE FIB(I)
DIMENSION A(2,2),B(2,2),C(2,2)
INTEGER L
A(1,1)=2; A(1,2)=1; A(2,1)=1; A(2,2)=1
B(1,1)=1; B(1,2)=0; B(2,1)=0; B(2,2)=1
J=I/2; J1=1
IF(AND(J,J1).NE.0) CALL MCOPY(A,B)
4 IF(J1.GE.J) GO TO 3
CALL MMULT (A,A,C)
CALL MCOPY (C,A)
J=J/2
IF(AND(J,J1).EQ.0) GO TO 4
CALL MMULT(A,B,C)
CALL MCOPY(C,B)
GO TO 4
3 IF(MOD(I,2).NE.0) GO TO 2
I=B(1,1)
RETURN
2 I=B(1,1)+B(1,2)
RETURN
END SUBROUTINE
C
SUBROUTINE MMULT(D,E,C)
DIMENSION D(2,2),E(2,2),C(2,2)
C(1,1)=D(1,1)*E(1,1)+D(1,2)*E(2,1);
C(1,2)=D(1,1)*E(1,2)+D(1,2)*E(2,2);
C(2,1)=D(2,1)*E(1,1)+D(2,2)*E(2,1);
C(2,2)=D(2,1)*E(1,2)+D(2,2)*E(2,2);
RETURN
END SUBROUTINE
C
SUBROUTINE MCOPY(D,E)
DIMENSION D(2,2),E(2,2)
E(1,1)=D(1,1); E(1,2)=D(1,2)
E(2,1)=D(2,1); E(2,2)=D(2,2)
RETURN
END SUBROUTINE
#include <stdio.h>
long fib(long x)
{
return x<2 ? 1 : fib(x-1)+fib(x-2);
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Infinite list:
#include <stdio.h>
#include <stdlib.h>
struct FL {
long i;
struct FL* next;
};
long flist_get(struct FL* flist, int n)
{
int i;
struct FL* flist_head;
long tmp_l;
flist_head=flist;
for(i=0; flist->next!=NULL; i++)
if (i==n) return flist->i; else flist=flist->next;
if(i==n) return flist->i;
tmp_l=flist_get(flist_head,i-1)+flist_get(flist_head,i);
flist->next=(struct FL*)calloc(1,sizeof(struct FL));
flist->next->i=tmp_l;
return flist_get(flist_head,n);
}
int main(void)
{
struct FL* flist;
flist = (struct FL*)calloc(1,sizeof(struct FL));
flist->i=1;
flist->next=(struct FL*)calloc(1,sizeof(struct FL));
flist->next->i=1;
printf("35th number is %ld\n",flist_get(flist,35));
return 0;
}
Once recursive:
#include <stdio.h>
long fib_lambda(long x1,long x2,long c)
{
return c<2 ? x1 : fib_lambda(x1+x2,x1,c-1);
}
long fib(long x)
{
fib_lambda(1,1,x);
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Non-recursive:
#include <stdio.h>
long fib(long x)
{
long i,x1=1,x2=1;
for(i=1;i<=x;i++) {
x1+=x2;
x1^=x2^=x1^=x2;
}
return(x1);
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Fast recursive:
#include <stdio.h>
void fib_lambda(long* n1,long* n2,long n)
{
long k1,k2;
if(n<=1) { *n1 = *n2 = 1; return; }
if(n==2) { *n1 = 2; *n2 = 1; return; }
if(n%2) {
fib_lambda(&k1,&k2,(n-1)/2);
*n1 = k1*(k1+k2) + k1*k2;
*n2 = k1*k1 + k2*k2;
} else {
fib_lambda(&k1,&k2,(n/2)-1);
*n1 = (k1+k2)*(k1+k2) + k1*k1;
*n2 = (k1+k2)*k1 + k1*k2;
}
}
long fib(long x)
{
long n1,n2;
fib_lambda(&n1,&n2,x);
return n1;
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
Matrix equation
#include <stdio.h>
void matrix_mult(long** mat1, long** mat2, long** result,long n)
{
long i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++) {
result[i][j] = 0;
for(k=0;k<n;k++)
result[i][j] += mat1[i][k] * mat2[k][j];
}
}
void matrix_copy(long** src, long** dest,long n)
{
long i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dest[i][j]=src[i][j];
}
long** matrix_new(long n)
{
long i,**a;
a=(long**)malloc(n*sizeof(long*));
for(i=0;i<n;i++)
a[i]=(long*)malloc(n*sizeof(long));
return a;
}
long fib(long n)
{
register bit=1,nh;
long **a,**b,**c,**d;
a=matrix_new(2); b=matrix_new(2);
c=matrix_new(2); d=matrix_new(2);
a[0][0]=2; a[0][1]=1;
a[1][0]=1; a[1][1]=1;
c[0][0]=1; c[0][1]=0;
c[1][0]=0; c[1][1]=1;
nh=n/2;
if(nh&bit) matrix_copy(a,c,2);
while(bit<nh) {
matrix_mult(a,a,b,2);
bit<<=1; if(nh&bit) {
matrix_mult(b,c,d,2);
matrix_copy(d,c,2);
}
matrix_copy(b,a,2);
}
return (n%2) ? c[0][0]+c[0][1] : c[0][0];
}
int main(void)
{
printf("35th Fibonacci number is %ld\n",fib(35));
return 0;
}
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) { return n<2 ? 1 : fib(n-1)+fib(n-2) }
Infinite list:
BEGIN { flist[0]=1 flist[1]=1
print "35th Fibonacci number is " fib(35) }
function fib(n) {
if(flist[n]==0) flist[n]=fib(n-1)+fib(n-2)
return flist[n]
}
Once recursive:
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) { return fl(1,1,n) }
function fl(x1,x2,c) { return c<2 ? x1 : fl(x1+x2,x1,c-1) }
Non-recursive:
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) {
x1=x2=1
for(i=1;i<=n;i++) {
tmp=x1+x2
x1=x2; x2=tmp
}
return x1
}
Fast recursive:
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n, k1, k2) {
if(n<2) return 1
if(n==2) return 2
if((n%2)==1) {
k1=fib((n-1)/2)
k2=fl_snd((n-1)/2)
return k1*(k1+2*k2)
} else {
k1=fib((n/2)-1)
k2=fl_snd((n/2)-1)
return (k1+k2)^2 + k1^2
}
}
function fl_snd(n, k1, k2) {
if(n<=2) return 1
if((n%2)==1) {
k1=fib((n-1)/2)
k2=fl_snd((n-1)/2)
return k1^2 + k2^2
} else {
k1=fib((n/2)-1)
k2=fl_snd((n/2)-1)
return k1*(k1+2*k2)
}
}
Matrix equation:
BEGIN { print "35th Fibonacci number is " fib(35) }
function mmultabb() {
c[1]=a[1]*b[1]+a[2]*b[3]
c[2]=a[1]*b[2]+a[2]*b[4]
c[3]=a[3]*b[1]+a[4]*b[3]
c[4]=a[3]*b[2]+a[4]*b[4]
for(i in c) b[i]=c[i]
}
function mmultaaa() {
c[1]=a[2]*a[3]+a[1]^2
c[2]=a[1]*a[2]+a[2]*a[4]
c[3]=a[3]*a[1]+a[4]*a[3]
c[4]=a[3]*a[2]+a[4]^2
for(i in c) a[i]=c[i]
}
function bitandnz(n1,n2) {
if (((n1%2)+(n2%2))==2) return 1
if ((n1==0) && (n2==0)) return 0
return bitandnz(int(n1/2),int(n2/2))
}
function fib(n) {
a[1]=2; a[2]=1; a[3]=1; a[4]=1
b[1]=1; b[2]=0; b[3]=0; b[4]=1
nh=int(n/2); bit=1
if (bitandnz(nh,bit))
for(i in a) b[i]=a[i]
while(bit<nh) {
mmultaaa()
bit=bit*2
if(bitandnz(nh,bit)) mmultabb()
}
if(n%2) return b[1]+b[2]
else return b[1]
}
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
return @_[0] < 2 ? new Math::BigInt("1") : fib(@_[0]-1) + fib(@_[0]-2)
}
Infinite list:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
@fl=(new Math::BigInt("1"),new Math::BigInt("1"));
$fl[$i+1]=$fl[$i-1]+$fl[$i] until $i++==@_[0];
return $fl[@_[0]]
}
Once recursive:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
return fl(new Math::BigInt("1"), new Math::BigInt("1"), @_[0])
}
sub fl {
return @_[2] < 2 ? @_[0] : fl(@_[0]+@_[1], @_[0], @_[2]-1);
}
Non-recursive:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
$x1=new Math::BigInt "1";
$x2=new Math::BigInt "1";
$tmp=new Math::BigInt "0";
for(;$i < @_[0]; $i++) {
$tmp=$x1+$x2; $x1=$x2; $x2=$tmp;
}
return $x1;
}
Fast recursive:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
my @a=fl(@_[0]);
return $a[0];
}
sub fl {
return (new Math::BigInt("1"),new Math::BigInt("1")) if @_[0]<=1;
return (new Math::BigInt("2"),new Math::BigInt("1")) if @_[0]==2;
if (@_[0] % 2) {
my @k = fl((@_[0]-1)/2);
return ($k[0]*($k[0]+$k[1]) + $k[0]*$k[1],
$k[0]*$k[0] + $k[1]*$k[1]);
} else {
my @k = fl((@_[0]/2)-1);
return (($k[0]+$k[1])*($k[0]+$k[1]) + $k[0]*$k[0],
($k[0]+$k[1])*$k[0] + $k[0]*$k[1]);
}
}
Matrix equation:
#!/usr/bin/perl
use Math::BigInt;
print "35th Fibonacci number is ", fib(35), "\n";
sub fib {
@a=(new Math::BigInt("2"),new Math::BigInt("1"),
new Math::BigInt("1"),new Math::BigInt("1"));
@b=(new Math::BigInt("1"),new Math::BigInt("0"),
new Math::BigInt("0"),new Math::BigInt("1"));
my $nh=@_[0]/2; my $bit=1;
@b=@a if ($nh & $bit);
while ($bit < $nh) {
@a=mmult(@a,@a); $bit<<=1;
@b=mmult(@a,@b) if $nh & $bit;
}
return @_[0] % 2 ? $b[0]+$b[1] : $b[0];
}
sub mmult {
my @a = (@_[0], @_[1], @_[2], @_[3]);
my @b = (@_[4], @_[5], @_[6], @_[7]);
$d[0]=$a[0]*$b[0]+$a[1]*$b[2];
$d[1]=$a[0]*$b[1]+$a[1]*$b[3];
$d[2]=$a[2]*$b[0]+$a[3]*$b[2];
$d[3]=$a[2]*$b[1]+$a[3]*$b[3];
return @d;
}
proc fib {n} {
if { $n < 2 } {return 1} else {
return [expr [fib [expr $n-1]] + [fib [expr $n-2]]]
}
}
puts [concat "35th Fibonacci number is " [fib 35]]
Infinite list:
proc fib {n l} {
set len [llength $l]
if {[expr $n>=$len]} {
set l [lappend l [expr [lindex $l [expr $len - 2]] + [lindex $l [expr $len - 1]]]]
return [fib $n $l]
}
return [lindex $l $n]
}
puts [concat "35th Fibonacci number is " [fib 35 [list 1 1]]]
Once recursive:
proc fl {x1 x2 c} {
if { $c < 2 } {return $x1} else {
return [fl [expr $x1+$x2] $x1 [expr $c-1]]
}
}
proc fib {n} { return [fl 1 1 $n] }
puts [concat "35th Fibonacci number is " [fib 35]]
Non-recursive:
proc fib {n} {
set x1 1
set x2 1
for {set i 1} {$i <= $n} {incr i} {
set tmp [expr $x1+$x2]
set x1 $x2; set x2 $tmp
}
return $x1
}
puts [concat "35th Fibonacci number is " [fib 35]]
Fast recursive:
proc fl {n} {
if {$n<2} {return [list 1 1]}
if {$n==2} {return [list 2 1]}
if {[expr $n % 2]} {
set kl [fl [expr ($n-1)/2]]
set k1 [lindex $kl 0]
set k2 [lindex $kl 1]
return [list [expr $k1*($k1+$k2)+$k1*$k2] [expr $k1*$k1+$k2*$k2]]
} else {
set kl [fl [expr ($n/2)-1]]
set k1 [lindex $kl 0]
set k2 [lindex $kl 1]
return [list [expr ($k1+$k2)*($k1+$k2)+$k1*$k1] [expr ($k1+$k2)*$k1+$k1*$k2]]
}
}
proc fib {n} { return [lindex [fl $n] 0] }
puts [concat "35th Fibonacci number is " [fib 35]]
Matrix equation:
proc mmult {a b} {
set c1 [expr [lindex $a 0]*[lindex $b 0]+[lindex $a 1]*[lindex $b 2]]
set c2 [expr [lindex $a 0]*[lindex $b 1]+[lindex $a 1]*[lindex $b 3]]
set c3 [expr [lindex $a 2]*[lindex $b 0]+[lindex $a 3]*[lindex $b 1]]
set c4 [expr [lindex $a 2]*[lindex $b 1]+[lindex $a 3]*[lindex $b 3]]
return [list $c1 $c2 $c3 $c4]
}
proc fib {n} {
set a {2 1 1 1}
set b {1 0 0 1}
set nh [expr $n/2]
set bit 1
if {[expr $nh & $bit]!=0} { set b $a }
while {$bit < $nh} {
set a [mmult $a $a]
set bit [expr $bit*2]
if {[expr $nh & $bit]!=0} { set b [mmult $a $b] }
}
if {[expr $n % 2]} {
return [expr [lindex $b 0] + [lindex $b 1]]
} else {
return [lindex $b 0] }
}
puts [concat "35th Fibonacci number is " [fib 35]]
#!/bin/sh
fib () {
if test $1 -lt 2; then
return 1
else
return $(($(fib $(($1-2));echo $?)+$(fib $(($1-1));echo $?)))
fi
}
fib 35
echo "35th Fibonacci number is" $?
Infinite list:
#!/bin/sh
fib () {
eval A='$'F$1
if test x$A != x; then
return $A
else
eval A='$'F$(($FL-1))
eval B='$'F$(($FL))
FL=$(($FL+1))
eval F$FL=$(($A+$B))
fib $1
fi
}
F0=1
F1=1
FL=1
fib 35
echo "35th Fibonacci number is" $?
Once recursive:
#!/bin/sh
fib () {
if test $1 -le 1; then
return $2
else
fib $(($1-1)) $(($2+$3)) $2
fi
}
fib 35 1 1
echo "35th Fibonacci number is" $?
Non-recursive:
#!/bin/sh
fib () {
N1=1
N2=1
I=1
while test $I -lt $1; do
I=$(($I+1))
TMP=$(($N1+$N2))
N2=$N1
N1=$TMP
done
return $N1
}
fib 35
echo "35th Fibonacci number is" $?
Fast recursive:
#!/bin/sh
fib () {
if test $1 -lt 2; then
return 1
elif test $1 -eq 2; then
return 2
elif test $(($1%2)) -eq 1; then
return $(($(fib $((($1-1)/2));echo $?)*($(fib $((($1-1)/2));echo $?)
+2*$(fl $((($1-1)/2));echo $?))))
else
return $((($(fib $(($1/2-1));echo $?)+$(fl $(($1/2-1));echo $?))
*($(fib $(($1/2-1));echo $?)+$(fl $(($1/2-1));echo $?))
+$(fib $(($1/2-1));echo $?)*$(fib $(($1/2-1));echo $?)))
fi
}
fl () {
if test $1 -le 2; then
return 1
elif test $(($1%2)) -eq 1; then
return $(($(fib $((($1-1)/2));echo $?)*$(fib $((($1-1)/2));echo $?)
+$(fl $((($1-1)/2));echo $?)*$(fl $((($1-1)/2));echo $?)))
else
return $(($(fib $(($1/2-1));echo $?)*($(fib $(($1/2-1));echo $?)
+2*$(fl $(($1/2-1));echo $?))))
fi
}
fib 35
echo "35th Fibonacci number is" $?
Matrix equation:
#!/bin/sh
fib () {
A11=2; A12=1; A21=1; A22=1
B11=1; B12=0; B21=0; B22=1
NH=$(($1/2))
BIT=1
if test $(($BIT & $NH)) -ne 0; then
B11=$A11; B12=$A12; B21=$A21; B22=$A22
fi
while test $BIT -lt $NH; do
BIT=$((2*$BIT))
mmultaaa
if test $(($BIT & $NH)) -ne 0; then
mmultabb
fi
done
if test $(($1%2)) -ne 0; then
return $(($B11+$B12))
else
return $B11
fi
}
mmultaaa () {
C11=$(($A12*$A21+$A11*$A11))
C12=$(($A11*$A12+$A12*$A22))
C21=$(($A21*$A11+$A22*$A21))
C22=$(($A21*$A12+$A22*$A22))
A11=$C11; A12=$C12; A21=$C21; A22=$C22
}
mmultabb () {
C11=$(($A12*$B21+$A11*$B11))
C12=$(($A11*$B12+$A12*$B22))
C21=$(($A21*$B11+$A22*$B21))
C22=$(($A21*$B12+$B22*$A22))
B11=$C11; B12=$C12; B21=$C21; B22=$C22
}
fib 35
echo "35th Fibonacci number is" $?
.globl _start
_start:
pushl $35
call fib
call print_eax
xorl %ebx,%ebx
movl $1,%eax
int $0x80
fib:
movl 4(%esp),%eax
cmpl $2,%eax
jl quitrec
decl %eax
pushl %eax
call fib
popl %edx
movl 4(%esp),%eax
movl %edx,4(%esp)
subl $2,%eax
pushl %eax
call fib
popl %eax
addl %eax,4(%esp)
ret
quitrec:
movl $1,4(%esp)
ret
print_eax:
movl $outbyte,%edi
movl 4(%esp),%eax
movl $10,%ebx
xorl %ecx,%ecx
divlp:
xorl %edx,%edx
divl %ebx
addb $48,%dl
pushl %edx
incl %ecx
testl %eax,%eax
jnz divlp
store:
popl %eax
stosb
loop store
movb $012,(%edi)
subl $outbyte,%edi
movl %edi,%edx
addl $outtxt_l,%edx
movl $outtxt,%ecx
movl $1,%ebx
movl $4,%eax
int $0x80
ret
.data
outtxt:
.ascii "35th Fibonacci number is "
outtxt_l = .-outtxt+1
outbyte:
.ascii "0000000000"
Infinite List.model tiny .code org 100h _start: mov ax,cs mov ds,ax mov es,ax cld push 23 call fib call print_eax ret fib: push bp mov bp,sp mov di,offset fib_array+2 mov cx,[bp+4] fib_loop: mov ax,[di-1] add ax,[di-2] inc di mov [di],ax loop fib_loop mov bx,[bp+4] mov ax,word ptr [bx+fib_array] mov [bp+4],ax pop bp ret print_eax: mov bp,sp mov di,offset outbyte mov ax,[bp+2] mov bx,10 xor cx,cx divlp: xor dx,dx div bx add dl,48 push dx inc cx test ax,ax jnz divlp store: pop ax stosb loop store mov byte ptr [di],'$' mov dx, offset outtxt mov ah,9 int 21h ret 2 outtxt db "23rd Fibonacci number is " outtxt_l = $-outtxt+1 outbyte db "00000000" fib_array db 1,1 end _startOnce recursive:
.section ".text"
.global _start
_start:
save %sp,-112,%sp
mov 35,%o2
mov 1,%o1
call fib_lambda,1
mov 1,%o0
call print_o0
nop
mov 1,%g1
ta 8
fib_lambda:
save %sp,-112,%sp
st %i2,[%fp+68]
ld [%fp+68],%o2
cmp %o2,2
bl lambda_ends
nop
st %i0,[%fp+68]
ld [%fp+68],%o1
add %o1,%i1,%o0
call fib_lambda,1
dec %o2
st %o0,[%fp+68]
ld [%fp+68],%i0
lambda_ends:
ret
restore
print_o0:
save %sp,-112,%sp
st %i0,[%fp+68]
ld [%fp+68],%o0
sethi %hi(outbyte_end),%l2
or %l2,%lo(outbyte_end),%l2
print_o0_loop:
clr %l1
o0_div_10_loop:
sub %o0,10,%o0
cmp %o0,0
bge o0_div_10_loop
inc %l1
add %o0,10+'0',%o0
stb %o0,[%l2]
dec %l1
mov %l1,%o0
cmp %l1,0
bne print_o0_loop
dec %l2
mov 1,%o0
sethi %hi(outtext),%o1
or %o1,%lo(outtext),%o1
mov outtext_l,%o2
mov 4,%g1
ta 8
mov 1,%o0
sethi %hi(outbyte),%o1
or %o1,%lo(outbyte),%o1
mov outbyte_l,%o2
mov 4,%g1
ta 8
ret
restore %g0,0,%o0
.section ".data"
outtext:
.ascii "35th Fibonacchi number is "
outtext_l = .-outtext
outbyte:
.ascii "0000000000"
.byte 012
outbyte_end = .-1
outbyte_l = .-outbyte
Non-recursive:.toc outtext_a: .tc outtext[TC],outtext outbyte_a: .tc outbyte_l[TC],outbyte_l .csect __start[DS] .globl __start __start: .long .__start, TOC[tc0], 0 .csect .text[PR] .__start: li 3,35 li 7,1 li 8,1 fib_loop: add 11,7,8 mr 7,8 mr 8,11 subi 3,3,1 cmpwi 3,0 bgt fib_loop lwz 9,outbyte_a(2) lwz 9,0(9) li 10,10 div_loop: divwu 3,7,10 mr 6,3 mullw 3,3,10 subf 3,3,7 mr 7,6 addi 3,3,'0' stb 3,0(9) subi 9,9,1 cmpwi 6,0 bgt div_loop li 3,1 lwz 4,outtext_a(2) li 5,outtext_l li 0,26 sc li 3,7 li 0,9 sc .csect .data[RW] outtext: .byte "35th Fibonacci number is " .byte "00000000" outbyte: .byte 10 outtext_l = .-outtext outbyte_l: .long outbyte-1Fast recursive:
.globl start .text start: mov $0,(sp) mov $27,-(sp) jsr pc, lambda print_r1: mov $outbyte,r3 div_loop: sxt r0 div $12,r0 add $60,r1 movb r1,-(r3) mov r0,r1 tst r1 jne div_loop mov $1,r0 sys 4; outtext; 37 mov $1,r0 sys 1 lambda: mov 2(sp),r1 cmp $2,r1 beq gottwo bgt gotone sxt r0 div $2,r0 tst r1 beq even odd: mov 2(sp),r1 dec r1 sxt r0 div $2,r0 mov r0,-(sp) jsr pc,lambda add $2,sp mov r0,r3 mov r1,r2 mov r3,r4 mul r2,r4 mov r5,r1 mov r3,r4 add r2,r4 mul r2,r4 add r5,r1 mul r3,r3 mov r3,r0 mul r2,r2 add r3,r0 rts pc even: mov 2(sp),r1 sxt r0 div $2,r0 dec r0 mov r0,-(sp) jsr pc,lambda add $2,sp mov r0,r3 mov r1,r2 mov r2,r4 mul r2,r4 mov r5,r1 mov r2,r4 add r3,r4 mul r4,r4 add r5,r1 mov r2,r4 add r3,r4 mul r2,r4 mov r5,r0 mul r2,r3 add r3,r0 rts pc gotone: mov $1,r0 mov $1,r1 rts pc gottwo: mov $1,r0 mov $2,r1 rts pc .data outtext: .byte 62,63,162,144,40,106,151,142,157,156 .byte 141,143,143,151,40,156,165,155 .byte 142,145,162,40,151,163,40 .byte 60,60,60,60,60 outbyte: .byte 12Matrix equation:
Navigation: [Up] [Index] This page:/serious/fibonacci.html
Page maintained by Sergei Zubkov
Page done with ISO 15445:2000 HTML
Last revision: $Date: 2003/09/30 04:07:07 $