cubbi.com: Fibonacci numbers in many programming languages languages: [english] [русский]
serious stuff
  www.cubbi.com
personal
programming
  fibonacci numbers
    algorithms
    benchmarks
    forth examples
    postscript examples
    muf examples
    joy examples
    j examples
    scheme examples
    hope examples
    ocaml examples
    haskell examples
    prolog examples
    c++ examples
    java examples
    assembly language examples
    fortran examples
    c examples
    sh examples
    awk examples
    perl examples
    tcl examples
  asmix
  hacker test
  resume
science
martial arts
fun stuff
  www.cubbi.org
                                                    

Fibonacci numbers are defined as follows

F(0) = 1
F(1) = 1
F(n) = F(n-1) + F(n-2)
-- Mathematical Handbook 2nd ed., G. Korn, T. Korn, 1968. paragraph 8.7-2
Please note that there exists a different definition, with F(0) = 0 and F(1) = 1. The conversion between the two is trivial.

ALGORITHMS AND BENCHMARKS SUMMARY

All implemented algorithms are discussed in detail on a ALGORITHMS page.
The benchmarks are discussed and analyzed in detail on a BENCHMARKS page too.
 
1. EXPONENTIAL COMPLEXITY
ALGORITHM 1A
Binary Recursion.		 Top 3 languages
T(46)
Recursively calculate F(n-1),
recursively calculate F(n-2),
and return the sum of the results.
  1. OCaml
    49.3
  2. Assembly
    55.4
  3. C
    66.2
 
2. LINEAR COMPLEXITY
ALGORITHM 2A
Data Structure.		 Top 3 languages
T(150,000)		 ALGORITHM 2B
Simple Recursion.		 Top 3 languages
T(500,000)		 ALGORITHM 2C
Non-recursive Loop.		 Top 3 languages
T(500,000)
The previously calculated Fibonacci Numbers may be stored in a data structure, which elminiates the need for binary recursion.
  • 2A-1: Infinite list.
  • 2A-2: Infinite list with exceptions.
  • 2A-3: Simple list
  1. Haskell
    10.7
  2. OCaml
    13.2
  3. perl
    383.0
Only two values have to be remembered to calculate the next Fibonacci number. This algorithm keeps them as parameters of a recursive funciton.
  1. OCaml
    28.0
  2. Haskell
    35.8
  3. Scheme
    37.7
Here the two previous Fibonacci numbers are stored in writable variables
  1. OCaml
    27.4
  2. Scheme
    37.8
  3. Java
    91.0
 
3. LOGARITHM COMPLEXITY
ALGORITHM 3A
Matrix Equation.		 Top 3 languages
T(1,000,000)		 ALGORITHM 3B
Fast Recursion.		 Top 3 languages
T(1,000,000)		 ALGORITHM 3C
Binet's Formula.		 
|F(n)   F(n-1)| |1 1|^n
|             |=|   |
|F(n-1) F(n-2)| |1 0|
  1. OCaml
    16.53
  2. Scheme
    30.30
  3. Prolog
    54.97
F(n)=F(n/2)2+F(n/2-1)2 for even n
F(n)=F((n-1)/2)*F((n-1)/2+1)+F((n-1)/2)*F((n-1)/2-1) for odd n
  1. OCaml
    11.56
  2. Scheme
    12.85
  3. Prolog
    47.75
F(n) = (φn+1-(1-φ)n+1)/sqrt(5), where φ = (1+sqrt(5))/2

EXAMPLES

LanguagesAlgorithms
1A2A2B2C3A3B3C
concatenative languages
(program is a composition of functions applied to stack of arguments)
Forth (1960) OK OK OK OK OK OK OK
PostScript (1982) OK OK OK OK OK OK OK
MUF (1989) OK OK OK OK OK OK OK
Joy (1999) OK OK OK OK OK OK OK
Vector languages
(program is a composition of functions applied to an multidimentional array argument)
J (1990) OK OK OK OK OK OK OK
functional languages
(program is an application of functions)
Scheme (1975) OK OK OK OK OK OK OK
Hope (1978) OK OK OK N/A OK OK OK
OCaml (1989) OK OK OK OK OK OK OK
Haskell (1990) OK OK OK N/A OK OK OK
logic languages
(program is a list of logic statements)
Prolog (1971) OK OK OK N/A OK OK OK
object languages
(program is a list of data objects and their relationships)
C++ (1986) OK OK OK OK OK OK OK
Java (1995) OK OK OK OK OK OK OK
imperative languages
(program is a sequence of commands to the CPU)
Assembly (1952) OK OK OK OK TBD OK TBD
Fortran (1954) OK OK N/A OK OK OK OK
C (1972) OK OK OK OK OK OK OK
sh (1972) OK OK OK OK OK OK OK
awk (1978) OK OK OK OK OK OK OK
perl (1987) OK OK OK OK OK OK OK
Tcl (1990) OK OK OK OK OK OK OK
LINKS
Wolfram's MathWorld entry
OEIS entry
 
[Made by Cubbi] http://cubbi.com/fibonacci.html
Page maintained by Sergey Zubkov
Last revision: $Date: 2006/02/23 19:11:28 $
[Valid CSS!]
[Valid ISO-HTML!] 		[Powered by Linux]