Algorithm Implementation/Mathematics/Fibonacci Number Program

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Fibonacci is similar to a "hello world" for many functional programming languages, since it can involve paradigms like pattern matching, memoization, and bog-standard tail recursion (which is equivalent to iteration). However, iteration or tail-recursion in linear time is only the first step: more clever exponentiation runs in logarithmic time.

Although the Binet/Lucas formula is technically also exponentiation, ita use of floating-point numbers makes it less attractive than the matrix-based solution. In addition, the above discussion of complexity and indeed most of the code here assumes that both addition and multiplication are done in a single step, which is not the case for big, exponentially-growing numbers easily created by fibonacci calculation.

C[edit | edit source]

An explanation of many of the following above can be found in nayuki's post.

Recursive version[edit | edit source]

unsigned int fib(unsigned int n) {
    // This is exactly the same as a ternary expression
    if (n < 2)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

Tail recursive version[edit | edit source]

// C++ default arguments used. If implemented in C, call with fib(n, 0, 1) instead.
unsigned int fib(unsigned int n, unsigned int acc = 0, unsigned int prev = 1) {
    if (n < 1)
        return acc;
    else
        return fib(n - 1, prev + acc, acc);
}

Using Binet's formula[edit | edit source]

#include <math.h>

const static double phi = (1 + sqrt(5)) / 2;
long fib(unsigned int n) {
    return (pow(phi, n) - pow(1 - phi, n)) / sqrt(5);
}

Iterative version[edit | edit source]

unsigned int fib(unsigned int n) {
    unsigned int i = 0, j = 1, t;
    if (n == 0)
        return 0;
    for (k = 1; k < n; ++k) {
        t = i + j;
        i = j;
        j = t;
    }
    return j;
}

Alternate iterative version[edit | edit source]

// This version is more "parallel" in the sense of a more unrolled loop.
unsigned int fib(int n) {
    unsigned int i = 0, j = 1, k = 1;
    for (; n >= 3; n -= 3) {
        i = j + k;
        j = i + k;
        k = i + j;
    }
    return n == 0 ? i :
           n == 1 ? j :
           k;
}

Matrix exponentiation by squaring[edit | edit source]

// A 2x2 matrix: m00, m01; m10, m11.
typedef struct mat22_s {
    unsigned int m00, m01, m10, m11;
} mat22_t;

// Matrix multiplication.
inline static mat22_t mat22_mul(mat22_t a, mat22_t b) {
    return (mat22_t){
        a.m00 * b.m00 + a.m01 * b.m10, a.m00 * b.m01 + a.m01 * b.m11,
        a.m10 * b.m00 + a.m11 * b.m10, a.m10 * b.m01 + a.m11 * b.m11};
}

// This is a less concise version written for clarity. The compiler should be able to optimize the boilerplate out.
unsigned int fib(unsigned int n) {
    // Matrix holds F(N-1), F(N); F(N), F(N+1).
    // This is an identity matrix, also the 0th power of matrix.
    mat22_t result = {1, 0, 0, 1};
    mat22_t matrix = {1, 1, 1, 0};
    for (; n > 0; n /= 2) {
        if (n % 2 == 1) {
            result = mat22_mul(matrix, result);
        }
        matrix = mat22_mul(matrix, matrix);
    }
    return result.m10;
}

Matrix exponentiation, compact[edit | edit source]

// A moderately compact version of the matrix calculation.
unsigned int fib(unsigned int n) {
    // [a b] is "result"; [c d] is "matrix".
    unsigned int a = 1, b = 0, c = 0, d = 1, t;
    if (n == 0)
        return 0;
    n = n - 1;
    while (n > 0) {
        if (n % 2 == 1) {
            t = d * (b + a) + c * b;
            a = d * b + c * a;
            b = t;
        }
        t = d * (2 * c + d);
        c = c * c + d * d;
        d = t;
        n = n / 2;
    }
    return a + b;
}

A similar alternative is based on Lucas numbers.

Matrix-derived fast doubling[edit | edit source]

// Nayuki's fast doubling code. Runs from high to low bits.
#include <limits.h>

static inline unsigned int log2i(unsigned int n) {
#if defined(__has_builtin) && __has_builtin(__builtin_clz)
    return sizeof (unsigned int) * CHAR_BIT - __builtin_clz(n) - 1;
#else
    return sizeof (unsigned int) * CHAR_BIT - 1; // pessimistic guess
#endif
}

unsigned int fib(unsigned int n) {
    // Two numbers for iteration. At the end, a = F(N) and b = F(N+1).
    unsigned int a = 0, b = 1;
    // log2i is not reliable for n = 0. We know better.
    unsigned int mask = n == 0 ? 0 : 1 << log2i(n);

    for (; mask > 0; mask /= 2) {
        // F(2k)   = F(k) * (2 * F(k+1) + F(k))
        unsigned int new_a = a * (b * 2 - a);
        // F(2k+1) = F(k+1)**2 + F(k)**2
        unsigned int new_b = a * a + b * b;
        a = new_a;  
        b = new_b;
        if (n & mask) {
             new_b = a + b;
             a = b;
             b = new_b;
        }
    }
    return a;
}

C#[edit | edit source]

C# code is essentially the same as C with some static method specifiers.

Iterative version[edit | edit source]

static int fib(int n) {
    int fib0 = 0, fib1 = 1;
    for (int i = 2; i <= n; i++) {
        int tmp = fib0;
        fib0 = fib1;
        fib1 = tmp + fib1;
    }
    return (n > 0 ? fib1 : 0);
}

Binet's formula[edit | edit source]

static int fibBINET(int n) {
    double sqrt5 = Math.Sqrt(5.0);
    double phi = (1 + sqrt5 ) / 2;
    return (int)((Math.Pow(phi, n) - Math.Pow(-phi, -n)) / sqrt5);
}

Using long numbers[edit | edit source]

static Num FibonacciNumber(int n) {
    Num n1 = new Num(0);
    Num n2 = new Num(1);
    Num n3 = new Num(1);
    for (int i = 2; i <= n; i++) {
        n3 = n2 + n1;
        n1 = n2;
        n2 = n3;
    }
    return n3;
}

struct Num {
    const int digit_base = 0x40000000; // 2^30
    List<int> digits;
    public int Length { get { return digits.Count; } }
    public int this[int index] { get { return digits[index]; } private set { digits[index] = value; } }

    public Num(int i) {
        digits = new List<int>();
        while (i > 0) {
            digits.Add(i % digit_base);
            i /= digit_base;
        }
    }

    public static Num operator +(Num a, Num b) {
        Num n = new Num();
        n.digits = new List<int>();
        int l = Math.Min(a.Length,b.Length);
        int remainder = 0;
        for (int i = 0; i < l; i++) {
            n.digits.Add((a[i] + b[i] + remainder) % digit_base);
            remainder = (a[i] + b[i] + remainder) / digit_base;
        }
        Num longer = a.Length > b.Length ? a : b;
        for (; l < longer.Length; l++) {
            n.digits.Add((longer[l] + remainder) % digit_base);
            remainder = (longer[l] + remainder) / digit_base;
        }
        if (remainder > 0) n.digits.Add(remainder);
        return n;
    }

    public override string ToString() {
        StringBuilder sb = new StringBuilder();
        for (int i = Length - 1; i >= 0; i--) {
            sb.AppendFormat("{0:D" + (digit_base.ToString().Length-1) + "}", this[i]);
        }
        return sb.ToString();
    }
}

D[edit | edit source]

Basic Recursive Version[edit | edit source]

ulong fib(uint n){
	return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}

Iterative Version[edit | edit source]

ulong fib(uint n) {
	ulong fib0 = 0;
	ulong fib1 = 1;
	for (auto i = 2; i <= n; i++) {
		auto tmp = fib0;
		fib0 = fib1;
		fib1 = tmp + fib1;
	}
	return (n > 0 ? fib1 : 0);
}

Memoized Recursive Version[edit | edit source]

ulong fib(uint n){
	static ulong[] memo;
	if (n < 0)
		return n;
	if (n < memo.length)
		return memo[n];
	auto result = (n < 2) ? n : fib(n - 1) + fib(n - 2);
	memo.length = n + 1;
	memo[n] = result;
	return result;
}

Erlang[edit | edit source]

 fib(0) -> 0;
 fib(1) -> 1;
 fib(N) -> fib(N-1) + fib(N-2).

Arithmetic version[edit | edit source]

 fib(N) ->
     S = math:sqrt(5),
     round(math:pow(((1 + S) / 2), N) / S).

algorithm taken from the Pascal "more efficient" version, below

F#[edit | edit source]

Simple recursive[edit | edit source]

 let rec fib x = if x < 2I then x else fib(x - 1I) + fib(x - 2I)

This version uses F# System.Numerics.BigInteger type

Memoized recursive[edit | edit source]

open System.Collections.Generic

let rec fib n =
    let memo = Dictionary<_, _>()
    let rec fibInner = function
        | n when n = 0I -> 0I
        | n when n = 1I -> 1I
        | n -> fib(n - 1I) + fib(n - 2I)
    if memo.ContainsKey(n) then memo.[n]
    else
       let res = fibInner n
       memo.[n] <- res
       res

Tail recursive[edit | edit source]

let fib n = 
    let rec fibInner (n, a, b) =
       if (n = 0I) then a
       else fibInner ((n - 1I), b, (a + b))
    fibInner (n, 0I, 1I)

Iterative[edit | edit source]

let fib n = 
    if n < 2I then
        n
    else
        let mutable fib1 = 0I
        let mutable fib2 = 1I
        let mutable i = 2I
        let mutable tmp = 0I
        while (i <= n) do
            i <- i + 1I
            tmp <- fib1
            fib1 <- fib2
            fib2 <- tmp + fib2
        fib2

Infinite Sequence Generator[edit | edit source]

let fibSeq =
    Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0I, 1I)

let fib n =
    fibSeq |> (Seq.skip n) |> Seq.head

Forth[edit | edit source]

: fib ( n -- fib )
  0 1 rot 0 ?do over + swap loop drop ;

Go[edit | edit source]

Recursive Solution[edit | edit source]

func fib(n int) int {
    if n < 2 {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

Iterative Solution[edit | edit source]

func fib(n int) int {
    if n == 0 {
        return 0
    }

    a, b := 0, 1

    for i := 1; i < n; i++ {
        a, b = b, a+b
    }
    return b
}

Haskell[edit | edit source]

List version[edit | edit source]

 fib n = fibs 0 1 !! n
     where
       fibs a b = a : fibs b (a + b)

Tail-recursive version[edit | edit source]

 fib n | n < 0     = undefined
       | otherwise = fib' n 0 1
     where
       fib' 0 a _ = a
       fib' n a b = fib' (n - 1) b (a + b)

Simple recursive version[edit | edit source]

 fib 0 = 0
 fib 1 = 1
 fib n = fib (n-1) + fib (n-2)

Awesome recursive version[edit | edit source]

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

Or :

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Or :

fibs = map fst $ iterate (\(a,b)->(b,a+b)) (0,1)

Closed-form version[edit | edit source]

Defines arithmetic operations on a custom data type, and then uses it to run the explicit formula without going via floating point - no rounding or truncation. Calculates the ten millionth fibonacci number in a few seconds (it has roughly two million digits).

module Fib where

-- A type for representing a + b * sqrt n
-- The n is encoded in the type.
data PlusRoot n a = a :+/ a
 deriving (Eq, Read, Show)
infix 6 :+/

-- Fetch the n in the root.
class WithRoot n where
  getRoot :: Num b => PlusRoot n a -> b

instance (WithRoot n, Num a) => Num (PlusRoot n a) where
  (a :+/ b) + (c :+/ d) = (a + c) :+/ (b + d)
  x@(a :+/ b) * (c :+/ d) = (a * c + getRoot x * b * d) :+/ (a * d + b * c)
  negate (a :+/ b) = negate a :+/ negate b
  fromInteger = (:+/ 0) . fromInteger

  -- I could implement these with (Ord a) but then we can't use the type
  -- with e.g. complex numbers.
  abs _ = error "PlusRoot.abs: unimplemented"
  signum _ = error "PlusRoot.signum: unimplemented"

instance (WithRoot n, Fractional a) => Fractional (PlusRoot n a) where
  fromRational = (:+/ 0) . fromRational
  recip x@(a :+/ b) = (a / r) :+/ (negate b / r)
   where
    r = a*a - getRoot x * b*b

-- Type parameter to PlusRoot. It would be easy to declare similar
-- types for Two or whatever, and get all the above arithmetic for free.
newtype Five = Five Five

instance WithRoot Five where
  getRoot _ = 5

-- The formula is phi^n - xi^n / sqrt 5
-- but it's always an integer, i.e. phi^n - xi^n is always a multiple
-- of sqrt 5, so the division isn't strictly necessary - just grab the
-- relevant coefficient.
fib :: Integer -> Integer
fib n = case phi^n - xi^n of
  -- The 'round' here is to make the types match; as discussed previously
  -- n must be an integer so no actual rounding is done.
  _ :+/ n -> round n
 where
  phi :: PlusRoot Five Rational
  phi = (1 :+/ 1) / 2
  xi = (1 :+/ negate 1) / 2


For other versions, see :

Dyalog APL[edit | edit source]

Basic Tail-Recursive Version[edit | edit source]

fibonacci?{    
   ??0 1
   ?=0:???
   (1??,+/?)? ?-1
}

Array-Oriented Version[edit | edit source]

fibonacci?{+/{?!??}(??)-?IO}

Other Versions[edit | edit source]

See Fibonacci at the Dynamic Functions Database

Io[edit | edit source]

Generic method version[edit | edit source]

 fib := method(n,
   if(n < 4,
     (n + n % 2) / 2,
     (n % 2 * 2 - 1) * fib((n + n % 3) / 2 - 1) ** 2 + fib((n - n % 3) / 2 + 1) ** 3
   )
 )

Polymorphic method version[edit | edit source]

  Number fibonacci := method((self - 1) fibonacci + (self -2) fibonacci)
  1 fibonacci = 1
  0 fibonacci = 0

Java[edit | edit source]

Recursive version[edit | edit source]

public void run(int n) {
    if (n <= 0) {
        return;
    }
    run(n, 1, 0);
}

private void run(int n, int eax, int ebx) {
    n--;
    if (n == 0) {
        System.out.println(eax + ebx);
        return;
    }
    run(n, ebx, eax + ebx);
}

Variations on the recursive version[edit | edit source]

/* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */
public long fib(long n) {
    if (n < 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

public long fib2(long n) {
    return (n < 2) ? n : getValue(n - 1) + getValue(n - 2);
}

Iterative version[edit | edit source]

/**
* Source based on 
* http://20bits.com/2007/05/08/introduction-to-dynamic-programming/
* as at 9-May-2007
*/
private long fibonacci(int n) {
    long n2 = 0;
    long n1 = 1;
    long tmp;
    for (int i = n; i >= 2; i--) {
        tmp = n2;
        n2 = n1;
        n1 = n1 + tmp;
    }
    return n2 + n1;
}

Simpler Iterative Version[edit | edit source]

/**
* returns the Nth number in the Fibonacci sequence
*/
public int fibonacci(int N) {
    int lo = 0;
    int hi = 1;
    for (int i = 0; i < N; i++) {
        hi = lo + hi;
        lo = hi - lo;
    }
    return lo;
}

Memoized version[edit | edit source]

private int[] fibs; // array for memoized fibonacci numbers

public int fib(int n) {
    if (n < 2) {
        return n;
    }
    if (fibs == null) { // initialise array to first size asked for
        fibs = new int[n + 1];
    } 
    else if (fibs.length < n) { // expand array
        int[] newfibs = new int[n + 1]; // inefficient if looping through values of n
        System.arraycopy(fibs, 0, newfibs, 0, fibs.length);
        fibs = newfibs;
    }
    if (fibs[n] == 0) {
        fibs[n] = fib(n - 1) + fib(n - 2);
    }
    return fibs[n];
}

Iterative Memoized version[edit | edit source]

public int fib(int n) {
    if (n < 2) {
        return n;
    }
    int[] f = new int[n + 1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}

Linotte[edit | edit source]

Fibonacci:
Principal :
Rôles :
	n :: nombre
Actions :
	"Entrez un nombre :" !
	n ?
	fibo(n) !

Fibo :
Rôles :
	* n :: nombre
Actions :
	si n < 2 alors retourne n
	retourne fibo(n-1) + fibo(n-2)

Lexico (in Spanish)[edit | edit source]

clase Fib
publicos:
mensajes:
Fib nop
Fibonacci(deme n es una cantidad) es_funcion cantidad
	{
	los objetos uno, dos, tres, i, respuesta son cantidades
 	copie 0 en uno
	copie 1 en dos
	variando i desde 1 hasta n haga:
		{
		copie uno en respuesta
		copie uno + dos en tres
		copie dos en uno
		copie tres en dos
		}
	retornar uno
	}
/**********************************/
tarea
{
el objeto f es un Fib
muestre "el 5: ", f.Fibonacci(doy 5)
}

Lua[edit | edit source]

 function fib(n)
   local a, b = 0, 1
   while n > 0 do
     a, b = b, a + b
     n = n - 1
   end
   return a
 end

Recursive version[edit | edit source]

 function fib(n)
   if n > 1 then n = fib(n - 1) + fib(n - 2) end
   return n
 end

Matlab[edit | edit source]

Recursive snippet[edit | edit source]

function F = fibonacci_recursive(n)
if n < 2 
    F = n;
else
    F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
end

Iterative snippet[edit | edit source]

function F = fibonacci_iterative(n)
first  = 0;
second = 1;
third  = 0;
for q = 1:n,
    third = first + second;
    first = second;
    second = third;
end
F = first;

Maxima[edit | edit source]

Recursive version[edit | edit source]

fib(n):=
    if n < 2 then
        n
    else
        fib(n - 1) + fib(n - 2)
$

Lucas form[edit | edit source]

fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5);

Iterative version[edit | edit source]

fib(n) := block(
    [i,j,k],
    i : 1,
    j : 0,
    for k from 1 thru n do
        [i,j] : [j,i + j],
    return(j)
)$

Exponentiation by squaring[edit | edit source]

fib(n) := block(
    [i,F,A],
    if n <= 0 then
        return(0),
    i : n - 1,
    F : matrix([1,0],[0,1]),
    A : matrix([0,1],[1,1]),
    while i > 0 do block(
        if oddp(i) then
            F : F.A,
        A : A^^2,
        i : quotient(i,2)
    ),
    return(F[2,2])
)$

O'Caml[edit | edit source]

 let fib n = 
   let rec fibonacci n = 
     match n with 
     | 0 -> (0, 0)
     | 1 -> (0, 1) 
     | m -> 
       let (a, b) = fibonacci (m-1) in 
         (b, a+b)
   in 
   let (_, k) = fibonacci n in 
     k;;

Pascal[edit | edit source]

  function F(n: integer): integer;
  begin
    case n of
    1,2: Result:=1
    else Result:=F(n-1)+F(n-2) end;
  end;

A bit more efficient[edit | edit source]

  function F(n: integer): integer;
  begin
    Result:=Round(Power((1+sqrt(5))/2, n)/sqrt(5));
  end;

Note that Power is usually defined in Math, which is not included by default.

For most compilers it's possible to improve performance by using the Math.IntPower instead of the Math.Power.

Iterative version also for negative arguments[edit | edit source]

function fib(n:integer):extended;
var i:integer;
    fib0,fib1:extended;
begin
fib0:=0;
fib1:=1;
for i:=1 to abs(n) do 
begin
fib0:=fib0+fib1;
fib1:=fib0-fib1;
end; 
if (n<0)and(not odd(n)) then fib0:=-fib0; 
fib:=fib0;
end:

Perl[edit | edit source]

 sub fib {
   my ($n, $a, $b) = (shift, 0, 1);
   ($a, $b) = ($b, $a + $b) while $n-- > 0;
   $a;
 }

Recursive versions[edit | edit source]

 sub fib {
   my $n = shift;
   return $n if $n < 2;
   return fib($n - 1) + fib($n - 2);
 }

 # returns F_n in a scalar context
 # returns all elements in the sequence up to F_n in a list context
 # only one recursive call
 sub fib {
    my ($n) = @_;
    return (0) if ($n == 0);
    return (0, 1) if ($n == 1);
    my @fib = fib($n - 1);
    return (@fib, $fib[-1] + $fib[-2]);
 }

Binary recursion, snippet[edit | edit source]

sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

Runs in Θ(F(n)) time, which is Ω(1.6n).

Binary recursion with special Perl "caching", snippet[edit | edit source]

use Memoize;
memoize 'fibo';
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

Iterative, snippet[edit | edit source]

sub fibo
{
    my ($n, $a, $b) = (shift, 0, 1);
    ($a, $b) = ($b, $a + $b) while $n-- > 0;
    $a;
}

PHP[edit | edit source]

Iterative version[edit | edit source]

function generate_fibonacci_sequence($length)
{
   for($l = [0, 1], $i = 2, $x = 0; $i < $length; $i++) {
        $l[] = $l[$x++] + $l[$x];
   }

   return $l;
 }

Recursive version[edit | edit source]

function fib($n)
{
   if ($n < 2) {
      return $n;
   }

   return fib($n - 1) + fib($n - 2);
}

Ternary version[edit | edit source]

function fib($n)
{
   return ($n < 2) ? $n : fib( $n-1 )+fib( $n-2 );
}

OOP version[edit | edit source]

class Fibonacci 
{
 	public $Begin	= 0;
 	public $Next;
 	public $Amount;
 	public $i;
 	
 	public function __construct( $Begin, $Amount ) {
 	
 		$this->Begin	= 0;
 		$this->Next		= 1;
 		$this->Amount	= $Amount;
 	
 	}
 	
 	public function _do() {
 	
 		for( $this->i = 0; $this->i < $this->Amount; $this->i++ ) {
    
 			$Value = ( $this->Begin + $this->Next );
    
 			echo $this->Begin . ' + ' . $this->Next . ' = ' . $Value . '<br />';
    
 			$this->Begin	= $this->Next;
 			$this->Next		= $Value;
 			
 		}
 	
 	}
 
 }
 
 $Fib = new fibonacci( 0, 6 );
 echo $Fib->_do();

Alternate version[edit | edit source]

 function fib($n) {
   return round(pow(1.6180339887498948482, $n) / 2.2360679774998);
 }

Python[edit | edit source]

Recursive version[edit | edit source]

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

Or :

def fib( n ):
    return n if n < 2 else fib( n - 1 ) + fib( n - 2 )

Recursive with memoization[edit | edit source]

m = {0: 1, 1: 1}
def fib(n):
    #assert n >= 0
    if n not in m:
        m[n] = fib(n-1) + fib(n-2)
    return m[n]

Lucas form[edit | edit source]

def fib(n):
    phi = (1 + sqrt(5))/2
    return int((phi**n - (-phi)**-n)/sqrt(5))

Iterative version[edit | edit source]

def fib(n):
    i,j = 1,0
    for k in range(1,n + 1):
        i,j = j, i + j
    return j

Iterative version using Generator[edit | edit source]

def fib(n):
  a,b = 1,0
  for i in range(n):
    yield b
    a, b = b, a+b

Exponentiation by squaring[edit | edit source]

def fib(n):
    if n <= 0:
        return 0
    i = n - 1
    a,b = 1,0
    c,d = 0,1
    while i > 0:
        if i % 2 == 1:
            a,b = d*b + c*a, d*(b + a) + c*b
        c,d = c**2 + d**2, d*(2*c + d)
        i = i >> 1
    return a + b

Lucas sequence identities[edit | edit source]

def fib(n):
    if n <= 0:
        return 0

    # n = 2**r*s where s is odd
    s, r = n, 0
    while s & 1 == 0:
        r, s = r+1, s/2

    # calculate the bit reversal t of (odd) s
    # e.g. 19 (10011) <=> 25 (11001)
    t = 0
    while s > 0:
        if s & 1 == 1:
            t, s = t+1, s-1
        else:
            t, s = t*2, s/2

    # use the same bit reversal process
    # to calculate the sth Fibonacci number
    # using Lucas sequence identities
    u, v, q = 0, 2, 2
    while t > 0:
        if t & 1 == 1:
            # u, v of x+1
            u, v = (u + v) / 2, (5*u + v) / 2
            q, t = -q, t-1
        else:
            # u, v of 2*x
            u, v = u * v, v * v - q
            q, t = 2, t/2

    # double s until we have
    # the 2**r*sth Fibonacci number
    while r > 0:
        u, v = u * v, v * v - q
        q, r = 2, r-1

    return u

Lucas sequence identities, recursion[edit | edit source]

As with the iterative version, this solution is also O(log n) with arbitrary precision.

def fib(n):
    def fib_inner(n):
        if n == 0:
            return 0, 2
        m = n >> 1
        # q = 2*(-1)**m
        q = -2 if (m & 1) == 1 else 2
        u, v = fib_inner(m)
        u, v = u * v, v * v - q
        if n & 1 == 1:
            # u, v of 2m+1
            u1 = (u + v) >> 1
            return u1, 2*u + u1
        else:
            # u, v of 2m
            return u, v

    if n <= 0:
        return 0
    # the outermost loop is unrolled
    # to avoid calculating an unnecessary v
    m = n >> 1
    u, v = fib_inner(m)
    if n & 1 == 1:
        # u of m+1
        u1 = (u + v) >> 1
        # u of 2m+1
        return u*u + u1*u1
    else:
        # u of 2m
        return u * v

REBOL[edit | edit source]

Recursive version[edit | edit source]

fib: func [n [integer!]] [
    either n < 2 [n] [(fib n - 1) + (fib n - 2)]
]

Ruby[edit | edit source]

 class Integer
     def fib
         @n = self.abs
         if @n < 2
             return @n
         else
             return (@n-1).fib + (@n-2).fib
         end
     end
 end

Alternate:

 class Integer
     def fib
         @n = self.abs
         (@n<2)?(return @n):(return (@n-1).fib+(@n-2).fib)
     end
 end

 # you run it like this
 puts 10.fib # output: 55
 puts 15.fib # output: 610

Recursive[edit | edit source]

def fib n
   return n if n < 2
   fib(n - 1) + fib(n - 2)
end

Generator[edit | edit source]

 class FibGenerator
   def initialize(n)
     @n = n		
   end	
 
   def each
     a, b = 1, 1
     @n.times do
       yield a
       a, b = b, a+b
     end
   end
 
   include Enumerable
 end
 
 def fibs(n)
   FibGenerator.new(n)
 end

 #use like this
 fibs(6).each do |x|
   puts x
 end

Arithmetic version[edit | edit source]

 def f(n)
   ((((1+Math.sqrt(5))/2)**n)/Math.sqrt(5)+0.5).floor
 end

Memoized Version[edit | edit source]

 fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]}
 fibmemo[0]=1
 fibmemo[1]=1
 
 def fib n
   fibmemo[n]
 end

Scheme[edit | edit source]

Tree-recursive version[edit | edit source]

 (define (fib n)
   (if (<= n 1)
       n
       (+ (fib (- n 1)) (fib (- n 2)))))

Iterative (tail-recursive) version[edit | edit source]

 (define (fib n)
   (define (iter a b count)
     (if (<= count 0)
         a
         (iter b (+ a b) (- count 1))))
   (iter 0 1 n))

Named-let, Iterative version[edit | edit source]

 (define (fib n)
   (let loop ((a 0) (b 1)
              (count n))
     (if (<= count 0) a
         (loop b (+ a b) (- count 1))))))

Lucas form[edit | edit source]

 (define fib
   (let* ((sqrt5 (inexact->exact (sqrt 5)))
          (fi (/ (+ sqrt5 1) 2)))
     (lambda (n)
       (round (/ (- (expt fi n) (expt (- fi 1) n)) sqrt5)))))

Logarithmic-time Version[edit | edit source]

This version squares the Fibonacci transformation, allowing calculations in log2(n) time:

(define (fib-log n)
  "Fibonacci, in logarithmic time."
  (define (fib-iter a b p q count)
    (cond ((= count 0) b)
	  ((even? count)
	   (fib-iter a b
		     (+ (* p p) (* q q))
		     (+ (* 2 p q) (* q q))
		     (/ count 2)))
	  (else (fib-iter (+ (* b q) (* a q) (* a p))
			  (+ (* b p) (* a q))
			  p q
			  (- count 1)))))

  (fib-iter 1 0 0 1 n))

[edit | edit source]

to fib :n
  output (cascade :n [?1+?2] 1 [?1] 0)
end

Recursive version[edit | edit source]

to fib :n
  if :n<2 [output 1]
  output (fib :n-1)+(fib :n-2)
end

VB.NET[edit | edit source]

Array oriented version[edit | edit source]

Dim i As Integer = 2
Dim sequencelength As Integer = 50
Dim fibonacci(sequencelength) As Integer
fibonacci(0) = 0
fibonacci(1) = 1
While i <> sequencelength
    fibonacci(i) = fibonacci(i - 1) + fibonacci(i - 2)
    i += 1
End While

Recursive Version[edit | edit source]

Private Function fibonacci(ByVal i as integer) As Integer
    If i < 1 Then
        Return -1
    ElseIf i < 2 Then
        Return i
    Else
        Return fibonacci(i-1) + fibonacci(i-2)
    End If
End Function

JavaScript[edit | edit source]

Recursive version[edit | edit source]

function fib(n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

Alternative recursive version[edit | edit source]

function fib(n, prev, cur) {
    if (prev == null) prev = 0;
    if (cur == null) cur = 1;
    if (n < 2) return cur;
    return fib(n--, cur, cur + prev);
}

Prev and cur is optional arguments.

Iterative version[edit | edit source]

function fibonacci(n) {
    var i = 1, j = 0, k, t;
    for (k = 1; k <= Math.abs(n); k++) {
        t = i + j;
        i = j;
        j = t;
    }
    if (n < 0 && n % 2 === 0) j = -j;
    return j;
}

This example supports negative arguments.

Lucas form[edit | edit source]

function fibonacci(n) {
    var sqrt5 = Math.sqrt(5);
    var fi = (1 + sqrt5) / 2;
    return Math.round((Math.pow(fi, n) - Math.pow(-fi, -n)) / sqrt5);
}

Binet's formula[edit | edit source]

function fibonacci(n) {
    var sqrt5 = Math.sqrt(5);
    var fi = (1 + sqrt5) / 2;
    return Math.round((Math.pow(fi, n + 1) - Math.pow(1 - fi, n + 1)) / sqrt5);
}

Algorithm from the Pascal "more efficient" version[edit | edit source]

function fibonacci(n) {
    var sqrt5 = Math.sqrt(5);
    return Math.round(Math.pow(((1 + sqrt5) / 2), n) / sqrt5);
}

Common Lisp[edit | edit source]

Lucas form[edit | edit source]

(defun fib (n)
  (cond
   ((= n 0) 0)
   ((or (= n 1) (= n 2)) 1)
   ((= 0 (mod n 2)) (-
                     (expt (fib (+ (truncate n 2) 1)) 2)
                     (expt (fib (- (truncate n 2) 1)) 2)))
   (t (+ (expt (fib (truncate n 2)) 2)
         (expt (fib (+ (truncate n 2) 1)) 2)))))

(fib (parse-integer (second *posix-argv*))) ;

Recursive version[edit | edit source]

(defun fib (x)
  (if (or (zerop x) (= x 1)) 1
    (+ (fib (- x 1)) (fib (- x 2)))))

(print (fib 10))

PostScript[edit | edit source]

Iterative[edit | edit source]

 20 % how many Fibonacci numbers to print
                                                                                
 1 dup
 3 -1 roll
 {
        dup
        3 -1 roll
        dup
        4 1 roll
        add
        3 -1 roll
        =
 }
 repeat

Stack recursion[edit | edit source]

This example uses recursion on the stack.

 % the procedure
 /fib
 {
    dup dup 1 eq exch 0 eq or not
    {
       dup 1 sub fib
       exch 2 sub fib
       add
    } if
 } def
 
 % prints the first twenty fib numbers 
 /ntimes 20 def
   
 /i 0 def
 ntimes {
    i fib =
    /i i 1 add def
 } repeat

PL/SQL[edit | edit source]

Iterative snippet[edit | edit source]

CREATE OR REPLACE PROCEDURE fibonacci(lim NUMBER) AS
  fibupper NUMBER(38);
  fiblower NUMBER(38);
  fibnum NUMBER(38);
  i NUMBER(38);
  BEGIN
    fiblower := 0;
    fibupper := 1;
    fibnum := 1;
    FOR i IN 1 .. lim
    LOOP
      fibnum := fiblower + fibupper;
      fiblower := fibupper;
      fibupper := fibnum;
      DBMS_OUTPUT.PUT_LINE(fibnum);
    END LOOP;
  END;