Algorithm Implementation/Mathematics/Fibonacci Number Program

From Wikibooks, open books for an open world
< Algorithm Implementation‎ | Mathematics(Redirected from Fibonacci number program)
Jump to: navigation, search

Contents

C[edit]

Recursive version[edit]

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

Ternary Recursive version[edit]

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

Tail recursive version[edit]

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

Lucas form[edit]

#include <math.h>
 
long fib(unsigned int n) {
    double fi = (1 + sqrt(5))/2;
    return (pow(fi, n) - pow(-fi, -n)) / sqrt(5);
}

Iterative version[edit]

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

Exponentiation by squaring[edit]

 unsigned int fib(unsigned int n){
   unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
   if (n <= 0)
     return 0;
   while (i > 0){
     if (i % 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;
     i = i / 2;
   }
   return a + b;
 }

Alternate exponentiation by squaring[edit]

 unsigned int fib(unsigned int n){
   unsigned int i = n - 1, a = 1, b = 0, c = 0, d = 1, t;
   if (n <= 0)
     return 0;
   while (i > 0){
     while (i % 2 == 0){
       t = d*(2*c + d);
       c = c*c + d*d;
       d = t;
       i = i / 2;
     }
     t = d*(b + a) + c*b;
     a = d*b + c*a;
     b = t;
     i--;
   }
   return a + b;
 }

C#[edit]

Iterative version[edit]

 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]

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

Using long numbers[edit]

    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]

Basic Recursive Version[edit]

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

Iterative Version[edit]

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]

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]

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

Arithmetic version[edit]

 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]

Simple recursive[edit]

 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]

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]

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]

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]

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]

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

Go[edit]

Recursive Solution[edit]

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

Iterative Solution[edit]

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]

List version[edit]

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

Tail-recursive version[edit]

 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]

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

Awesome recursive version[edit]

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]

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 Haskell/Overview.

Dyalog APL[edit]

Basic Tail-Recursive Version[edit]

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

Array-Oriented Version[edit]

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

Other Versions[edit]

See Fibonacci at the Dynamic Functions Database

Io[edit]

Generic method version[edit]

 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]

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

Java[edit]

Recursive version[edit]

    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]

    /* Recursive versions. Horribly inefficient. Use iterative/memoized versions instead */
    public long fib(long n) {
        if (n<2) {
            return n;
        }
        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]

    /**
     * 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]

  /**
    * 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]

	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]

	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]

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]

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]

 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]

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

Matlab[edit]

Recursive snippet[edit]

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

Iterative snippet[edit]

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]

Recursive version[edit]

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

Lucas form[edit]

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

Iterative version[edit]

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]

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]

 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]

  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]

  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]

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]

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

Recursive versions[edit]

 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]

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]

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

Iterative, snippet[edit]

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

PHP[edit]

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

Recursive version[edit]

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

OOP version[edit]

 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]

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

Python[edit]

Recursive version[edit]

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

Recursive with memorization[edit]

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]

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

Iterative version[edit]

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

Exponentiation by squaring[edit]

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 / 2
    return a + b

Lucas sequence identities[edit]

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]

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]

Recursive version[edit]

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

Ruby[edit]

 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]

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

Generator[edit]

 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]

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

Memoized Version[edit]

 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]

Tree-recursive version[edit]

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

Iterative (tail-recursive) version[edit]

 (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]

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

Lucas form[edit]

 (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]

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]

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

Recursive version[edit]

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

VB.NET[edit]

Array oriented version[edit]

 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]

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

JavaScript[edit]

Recursive version[edit]

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


Alternative recursive version[edit]

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]

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]

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);
}


Binets formula[edit]

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]

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

Common Lisp[edit]

Lucas form[edit]

(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]

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

PostScript[edit]

Iterative[edit]

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]

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]

Iterative snippet[edit]

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;