Languages: [English] [Russian]
Mirrors: [USA] [Russia]

45th Fibonacci number in many languages

In 2000-2002 I tought a course on computer programming, and at the first lecture I would show several different programming languages and explain to the students that all of them can be used to code a given algorithm with pretty much equal amount of hassle. This was one of the several thoughts I would show before leading to the idea that the choice of language is secondary to the choice of algorithm. The algorithm I used at the first example was calculation of Fibonacci numbers.
At some point I realized that I this could make a nice little web page. So, here it is, the web page showing how to calculate the 45th Fibonacci number in some languages I know using six different algorithms.
I AM IN PROCESS OF UPDATING THIS PAGE from 35th to 45th number

Theory

Fibonacci numbers used here are defined as follows

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.

I use the following six algorithms:

New Benchmarks

Benchmarked on Intel Pentium 4 2.20GHz running Linux 2.5.75
Binary Recursion (the slowest) algorithm for the 45th Fibonacci number
LanguageTranslator [*]Time, seconds
AssemblyGNU as 2.12.90.0.9 [c]32.25
CGNU gcc 2.95.3 [c]44.72
ForthTektronix PFE 0.32.94 [i]594.92
JoyJoy1 by Manfred von Thun [i]1331.05
PostScriptESP Ghostscript 7.07.1 [i]1555.62
MUFFuzzBall MUCK 6.01 [b]4048.00
[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter
Execution time is user time as reported by GNU time(1) except for MUF

Old Benchmarks

Benchmarked on Pentium Celeron 600 running Linux 2.2.5
Twice Recursive (slow) algorithms for 35th Fibonacci number
LanguageTranslator [*]Time, seconds
AssemblyGNU as 2.9.1 [c]0.63
CamlObjective Caml 2.99 [c]0.74
CGCC 2.95.1 [c]0.92
C++G++ 2.95.1 [c]0.99
SchemeMIT Scheme 7.5.0 [b]1.94
JavaJDK 1.1.7B [b]10.17
ForthThisForth 1.0.0d [i]14.57
HaskellNHC98 1.0 pre-prelease 14 [c]36.05
PostScriptGhostScript 5.10 [i]42.98
JoyJoy0 by Manfred von Thun [i]50.41
Perlperl 5.005_003 [i]114.05
PrologSWI-Prolog 3.3.10 [b]120.44
AWKby Brian Kernighan [i]212.30
Hopeby Ross Paterson [i]512.46
TclTCL 8.2 [i]1468.49
shGNU bash 1.14 [i]8792.43
[*] - [c] for Compiler, [b] for Bytecode intepreter, [i] for Interpreter

 

Fast algorithms for 50000th Fibonacci number (10451 decimal digits)
LanguageInfinite listOnce recursiveNon-recursiveFast recursiveMatrix equation
Haskell2.832.68n/a1.481.51
Schememem4.794.820.190.53
Java10.010.77.880.440.77
perlmemmem1859.4224.99119.25

Implementations

Featured languages
ConcatenativeLogicFunctionalObjectImperative
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

Some functions/methods/words/procedurs/subroutines presented here hang or crash when given a negative number.
I fix this only when it can be done without altering the program - like when I just have to change one equals sign with one less-or-equals. Otherwise this bug is left out - the original mathematical definition doesn't deal with negative arguments.
Program make no checks about overflows.
I don't fix this, but if a language provides arbitrary precision integer numbers (Java, Haskell, Scheme, perl), I use them. Writing large integer packages for every language is beyond the scope of this page.
There are no comments in the program code listings.
Saying the same thing over and over was too boring to me.
Why 45th number?
45th Fibonacci number is 1836311903 (0x6d73e55f), and is the largest Fibonacci number that fits into Signed 32-bit data type. 46th fibonacci number is 2971215073 (0xb11924e1). Besides, it already takes a long time to calculate using Binary Recursion.
Which language is my favorite?
I tend to treat most languages equally, but I have a definite likeness for Forth. And the new language Joy left me in complete awe. I would love to see it getting more exposure.
Of course I am not an expert in every language I use, and if you see me doing something wrong with your favorite language - send a better style version to me - write me.

Concatenative Languages:

FORTH

Date: 1960 (Finalized in ANSI X3.215-1994)
Usage: embedded systems, OS loaders, anything written by its fans, everything written for forth-processors
Binary Recursion 
: 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
;
fib45
Infinite List
(this example uses a linked 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
;
fib45
Non-recursive Loop 
: fib ( n -- n )
  1 1 ROT 1 DO SWAP OVER + LOOP SWAP DROP
;
: fib45 ( -- )
  ." 45th Fibonacci number is " 45 fib U. CR
;
fib45
Fast 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
;

PostScript

Date: 1982
Usage: PostScript-printers, PostScript interpreters, any graphical programs that can read or write PostScript files
Binary Recursion 
/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
(this example uses a dynamically allocated fixed-length array) 
/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

MUF

Date: 1989
Usage: internal language for TinyMUCK and FuzzBall virtual multiuser environments
Binary Recursion 
: 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:
(this example uses a property 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
;

Joy

Date: 1999
Usage: academic
Binary Recursion 
"45th Fibonacci number is " [putch] step 45
[small] [pop 1] [pred dup pred] [+] binrec .
Infinite List
(this example uses a simple list because Joy's lazy evaluation library so far supports only single argument constructors) 
"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
(I hope Joy will include the integer power of a matrix into mtrlib soon, to let me write this program even shorter) 
"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 .

Logic Languages:

Prolog

Date: 1971
Usage: artificial intellect, fuzzy logic, natural language processing, and more
Twice recursive: 
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:
(lazy evaluation does not exist in this language. List is used instead) 
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 Applicable
Fast 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.

Functional Languages:

Hope

Date: 1978
Usage: academic
Twice recursive: 
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 Applicable
Fast 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];

Scheme

Date: 1975
Usage: academic, also scripting language for some software packages
(Note that all examples use arbitrary precision integer numbers)
Twice recursive 
(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
(lazy evaluation does not exist in this language. List is used instead) 
(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))

Caml

Date: 1989
Usage: special applications (for example FFTW library), parallel, time-critical, and other productions where functional programming is applicable
Twice recursive: 
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:
(lazy evaluation does not exist in this language. Exceptions are used to emulate it) 
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 ();;

Haskell

Date: 1990
Usage: growing, becoming *the* functional language
(Note that all examples except twice recursive use arbitrary precision integer numbers)
Twice recursive: 
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 Applicable
Fast 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))

Object-Oriented Languages:

Java

Date: 1996(?)
Usage: Web applications, though targeted and marketed for much more
(Note that all examples except twice recursive use arbitrary precision integer numbers)
Twice recursive: 
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:
(lazy evaluation does not exist in this language. Exceptions are used to emulate it) 
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));
 }
}

C++

Date: 1986 (Finalized in ISO/IEC 14882:1998)
Usage: Wide variety of mediocre software.
Twice recursive: 
#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:
(lazy evaluation does not exist in this language. Vector is used instead) 
#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;
}

Imperative Languages:

FORTRAN

Date: 1954 (Finalized in ANSI X3.9-1978 and ISO/IEC 1539-1:1997)
Usage: huge libraries of scientific/math code are written in this language and are sometimes still used.
Twice recursive
FORTRAN 77 does not support recursion. It was hard to re-write double recursion into simple loops and keep the same level of inefficiency. I also couldn't make it compile 35th number, the best it could do was 19th. 
      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:
FORTRAN 77 does not support lazy evaluation. Computed size array used instead. 
      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
FORTRAN 77 does not support recursion. Re-writing this algorithm to use a simple loop gives a program which is fully equivalent to "non-recursive". Non-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
FORTRAN 77 does not support recursion. However, I re-wrote this algorithm to use a simple loop. It is not even too ugly, by fortran standards. 
      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

C

Date: 1972 (Finalized in ANSI X3.159-1989 and ISO/IEC 9899:1990)
Usage: everything written for UNIX-related operating systems, and the most of system and application software everywhere
Twice recursive: 
#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:
(lazy evaluation does not exist in this language. Linked list is used instead) 
#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;
}

AWK

Date: 1978
Usage: original text processing on UNIX systems (currently being overrun by perl)
Twice recursive: 
BEGIN { print "35th Fibonacci number is " fib(35) }
function fib(n) { return n<2 ? 1 : fib(n-1)+fib(n-2) }
Infinite list:
(lazy evaluation does not exist in this language. Array is used instead) 
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]
}

perl

Date: 1987
Usage: text processing language, used mainly for CGI programs
Twice recursive: 
#!/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:
(lazy evaluation does not exist in this language. Array is used instead) 
#!/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;
}

Tcl

Date: 1990
Usage: scripting language for many software packages, main part of Tcl/Tk GUI developement package
Twice recursive: 
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:
(lazy evaluation does not exist in this language. List is used instead) 
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]]

sh

Date: 1972
Usage: scripting language of the UNIX shell
(these examples are done with The Open Group Single UNIX 2 XCU standard shell language - if your particular shell fails on them (like bash 2.0) - try another one (like bash 1.14)
Twice recursive: 
#!/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:
(lazy evaluation does not exist in this language. Many variables are used instead) 
#!/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" $?

Assembly Languages

Date: 1952
Usage: basic low level language on any system
(examples use different platforms and dialects, for diversity)
Twice recursive:
(AT&T Assembly Language for x86, Linux syscalls, ELF output) 
	.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
(Intel Assembly Language for x86, MS-DOS syscalls, COM output) 
	.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 _start
Once recursive:
(Sun Assembly Language for SPARC, SunOS/Solaris syscalls, ELF output) 
.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:
(Motorola Assembly Language for PPC, LynxOS syscalls, XCOFF output) 
	.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-1
Fast recursive:
(DEC Assembly Language for PDP-11, UNIX syscalls, a.out output) 
	.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 12
Matrix equation:
(as soon as I get access to a new plaform (an account, anyone?)) 




TO BE CONTINUED...













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 $