Fibonacci sequence

From Rosetta Code

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2, if n>1

Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). Support for negative n errors is optional.

[edit] References

Wikipedia

Wolfram MathWorld

[edit] Ada

 
with Ada.Text_IO;  use Ada.Text_IO;
 
procedure Test_Fibonacci is
   function Fibonacci (N : Natural) return Natural is
      This : Natural := 0;
      That : Natural := 1;
      Sum  : Natural;
   begin
      for I in 1..N loop
         Sum  := This + That;
         That := This;
         This := Sum;
      end loop;
      return This;
   end Fibonacci;
begin
   for N in 0..10 loop
      Put_Line (Positive'Image (Fibonacci (N)));
   end loop;
end Test_Fibonacci;
 

Sample output:

 0
 1
 1
 2
 3
 5
 8
 13
 21
 34
 55

[edit] BASIC

Works with: QuickBasic version 4.5

Translation of: Java

[edit] Iterative

FUNCTION itFib (n)
IF (n <= 2) THEN
        itFib = 1
ELSE
        ans = 0
        n1 = 1
        n2 = 1
        n = n - 2
        DO WHILE (n > 0)
                ans = n1 + n2
                n1 = n2
                n2 = ans
                n = n - 1
        LOOP
        itFib = ans
END IF
END FUNCTION

[edit] Recursive

FUNCTION recFib (n)
IF (n <= 2) THEN
        recFib = 1
ELSE
        recFib = recFib(n - 1) + recFib(n - 2)
END IF
END FUNCTION

[edit] Befunge

00:.1:.>:"@"8**++\1+:67+`#@_v
       ^ .:\/*8"@"\%*8"@":\ <

[edit] Brainf***

The first cell contains n (10), the second cell will contain fib(n) (55), and the third cell will contain fib(n-1) (34).

++++++++++
>>+<<[->[->+>+<<]>[-<+>]>[-<+>]<<<]

[edit] C++

Using unsigned int, this version only works up to 48 before fib overflows.

#include <iostream>
 
int main()
{
        unsigned int a = 1, b = 1;
        unsigned int target = 48;
        for(unsigned int n = 3; n <= target; ++n)
        {
                unsigned int fib = a + b;
                std::cout << "F("<< n << ") = " << fib << std::endl;
                a = b;
                b = fib;
        }
 
        return 0;
}
 

Library: GMP

This version does not have an upper bound.

#include <iostream>
#include <gmpxx.h>
 
int main()
{
        mpz_class a = mpz_class(1), b = mpz_class(1);
        mpz_class target = mpz_class(100);
        for(mpz_class n = mpz_class(3); n <= target; ++n)
        {
                mpz_class fib = b + a;
                if ( fib < b )
                {
                        std::cout << "Overflow at " << n << std::endl;
                        break;
                }
                std::cout << "F("<< n << ") = " << fib << std::endl;
                a = b;
                b = fib;
        }
        }
        return 0;
}

Far-fetched version using adjacent_difference:

#include <numeric>
#include <functional>
#include <iostream>
 
unsigned int fibonacci(unsigned int n) {
  if (n == 0) return 0;
  int *array = new int[n];
  array[0] = 1;
  std::adjacent_difference(array, array+n-1, array+1, std::plus<int>());
  // "array" now contains the Fibonacci sequence from 1 up
  int result = array[n-1];
  delete [] array;
  return result;
}

[edit] D

Here are four versions of Fibonacci Number generating functions.
FibD has an argument limit of magnitude 82 due to floating point precision, the others have a limit of 92 due to overflow (long).
The traditional recursive version is inefficient. It is optimized by supplying a static storage to store intermediate results.
All four functions have support for negative arguments.

module fibonacci ;
import std.stdio ;
import std.math ;
import std.conv ;
 
long FibD(int m) { // Direct Calculation, correct for abs(m) <= 82
  const real sqrt5r = 0.44721359549995793928L ; // 1 / sqrt(5)
  const real golden = 1.6180339887498948482L ;  // (1 + sqrt(5)) / 2 ;
  real sign = (m < 0) && (1 & m ^ 1) ? -1.0L : 1.0L ;
  return rndtol(pow(golden, abs(m)) * sign * sqrt5r)  ;
}
long FibI(int m) { // Iterative
  int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
  int n = m < 0 ? -m : m ;
  if (n < 2)
    return n ;
  long prevFib = 0 ;
  long thisFib = 1 ;
  for(int i = 1 ; i < n ;i++) {
    long tmp = thisFib ;
    thisFib += prevFib ;
    prevFib = tmp ;
  } 
  return thisFib*sign ;   
}
long FibR(int m) { // Recursive
  if (m == 0 || m == 1) return m ;
  return (m >= 0) ? FibR(m-1) + FibR(m-2) : (1 & m ^ 1) ? - FibR(-m) : FibR(-m)  ;
}
long FibO(int m) { // Optimized Recursive
  static long[] fib = [0,1] ;
 
  int sign = (m < 0) && (1 & m ^ 1) ? -1 : 1 ;
  int n = m < 0 ? -m : m ;  
 
  if(n >= fib.length )
    fib ~= FibO(n-2) + FibO(n-1) ;
  return fib[n]*sign ;    
}
void main(string[] args) {
  int k = args.length > 1 ? toInt(args[1]) : 10 ;
  writefln("Fib(%3d) = ", k) ;
  writefln("D : %20d <- %20d + %20d", FibD(k), FibD(k - 1), FibD(k - 2) ) ;
  writefln("I : %20d <- %20d + %20d", FibI(k), FibI(k - 1), FibI(k - 2) ) ;
  if( abs(k) < 36 || args.length > 2) // set a limit for recursive version
  writefln("R : %20d <- %20d + %20d", FibR(k), FibO(k - 1), FibO(k - 2) ) ;
  writefln("O : %20d <- %20d + %20d", FibO(k), FibO(k - 1), FibO(k - 2) ) ;
}

Output for n = 83:

Fib( 83) =
D :    99194853094755496 <-    61305790721611591 +    37889062373143906
I :    99194853094755497 <-    61305790721611591 +    37889062373143906
O :    99194853094755497 <-    61305790721611591 +    37889062373143906

[edit] E

def fib(n) {
    var s := [0, 1]
    for _ in 0..!n { 
        def [a, b] := s
        s := [b, a+b]
    }
    return s[0]
}

(This version defines fib(0) = 0 because OEIS A000045 does.)

[edit] Forth

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

[edit] Fortran

[edit] Recursive

In ISO Fortran 90 or later, use a RECURSIVE function:

module fibonacci
contains
    recursive function fibR(n) result(fib)
        integer, intent(in) :: n
        integer             :: fib
        
        select case (n)
            case (:0);      fib = 0
            case (1);       fib = 1
            case default;   fib = fibR(n-1) + fibR(n-2)
        end select
    end function fibR

[edit] Iterative

In ISO Fortran 90 or later:

    function fibI(n)
        integer, intent(in) :: n
        integer, parameter :: fib0 = 0, fib1 = 1
        integer            :: fibI, back1, back2, i
     
        select case (n)
            case (:0);      fibI = fib0
            case (1);       fibI = fib1
         
            case default
                fibI = fib1
                back1 = fib0
                do i = 2, n
                    back2 = back1
                    back1 = fibI
                    fibI   = back1 + back2
                end do
        end select
    end function fibI
end module fibonacci

Test program

program fibTest
    use fibonacci
    
    do i = 0, 10
        print *, fibr(i), fibi(i)
    end do 
end program fibTest

Output

0 0
1 1
1 1
2 2
3 3
5 5
8 8
13 13
21 21
34 34
55 55

[edit] Haskell

[edit] With lazy lists

This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers:

fib = 1 : 1 : zipWith (+) fib (tail fib)

The nth Fibonacci number is then just

fib !! n

[edit] With matrix exponentiation

With the (rather slow) code from Matrix exponentiation operator

import Data.List

xs <+> ys = zipWith (+) xs ys
xs <*> ys = sum $ zipWith (*) xs ys

newtype Mat a = Mat {unMat :: [[a]]} deriving Eq

instance Show a => Show (Mat a) where
  show xm = "Mat " ++ show (unMat xm)

instance Num a => Num (Mat a) where
  negate xm = Mat $ map (map negate) $ unMat xm
  xm + ym   = Mat $ zipWith (<+>) (unMat xm) (unMat ym)
  xm * ym   = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm]
  fromInteger n = Mat [[fromInteger n]]

we can simply write

fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n

So, for example, the ten-thousendth Fiboncacci number starts with the digits

*Main> take 10 $ show $ fib (10^5)
"2597406934"

[edit] IDL

[edit] Recursive

function fib,n
   if n lt 3 then return,1L else return, fib(n-1)+fib(n-2)
end 

Execution time O(2^n) until memory is exhausted and your machine starts swapping. Around fib(35) on a 2GB Core2Duo.

[edit] Iterative

function fib,n
  psum = (csum = 1uL)
  if n lt 3 then return,csum
  for i = 3,n do begin
    nsum = psum + csum
    psum = csum
    csum = nsum
  endfor
  return,nsum
end

Execution time O(n). Limited by size of uLong to fib(49)

[edit] Analytic

function fib,n
  q=1/( p=(1+sqrt(5))/2 ) 
  return,round((p^n+q^n)/sqrt(5))
end

Execution time O(1), only limited by the range of LongInts to fib(48).

[edit] J

See J Wiki: Fibonacci Sequence.

[edit] Java

[edit] Iterative

public static long itFibN(int n){
        if(n <= 2)return 1;
        long ans = 0;
        long n1 = 1;
        long n2 = 1;
        for(n -= 2;n > 0;n--){
                ans = n1 + n2;
                n1 = n2;
                n2 = ans;
        }
        return ans;
}

[edit] Recursive

public static long recFibN(int n){
        if(n <= 2) return 1;
        return recFibN(n-1) + recFibN(n-2);
}

[edit] Analytic

This method works up to the 92^nd Fibonacci number. After that, it goes out of range.

public static long anFibN(long n){
	double p= (1 + Math.sqrt(5)) / 2;
	double q= 1 / p;
	return (long)((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5));
}

[edit] JavaScript

[edit] Recursive

One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion:

 function fib(n) {
   return function(n,a,b) {
     return n>0 ? arguments.callee(n-1,b,a+b) : a;
   }(n,0,1);
 }

[edit] Iterative

 function fib(n) {
   var a=0, b=1, t;
   while (n-- > 0) {
     t = a;
     a = b;
     b += t;
   }
   return a;
 }
 for (var i=0; i<10; ++i) alert(fib(i));

[edit] Joy

DEFINE fib ==
             [small]
             []
             [pred dup pred]
             [+]
             binrec .

[edit] Logo

to fib_acc :n :a :b
  if :n < 1 [output :a]
  output fib_acc :n-1 :b :a+:b
end
to fib :n
  output fib_acc :n 0 1
end

[edit] Mathematica

Mathematica already has a built-in function Fibonacci, but a simple recursive implementation would be

fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n - 1] + fib[n - 2]

An optimization is to cache the values already calculated:

fib[0] = 0
fib[1] = 1
fib[n_Integer] := fib[n] = fib[n - 1] + fib[n - 2]

[edit] MAXScript

[edit] Iterative

fn fibIter n =
(
    if n <= 2 then
    (
        1
    )
    else
    (
        fib = 1
        fibPrev = 1
        for num in 3 to n do
        (
            temp = fib
            fib += fibPrev
            fibPrev = temp
        )
        fib
    ) 
)

[edit] Recursive

fn fibRec n =
(
    if n <= 2 then
    (
        1
    )
    else
    (
        fibRec (n - 1) + fibRec (n - 2)
    )
)

[edit] OCaml

[edit] Iterative

let fib_iter n =
  if n <= 2 then
    1
  else let fib_prev = ref 1
  and fib = ref 1 in
    for num = 2 to n - 1 do
      let temp = !fib in
        fib := !fib + !fib_prev;
        fib_prev := temp
    done;
    !fib

[edit] Recursive

let rec fib_rec n =
  if n <= 2 then
    1
  else
    fib_rec (n - 1) + fib_rec (n - 2)

The previous way is the naive form, because for most n the fib_rec is called twice, and it is not tail recursive because it adds the result of two function calls. The next version resolves these problems:

 
let fib n =
  let v = 0
  and vn = 1 in
  let rec aux i v vn =
    if i >= n then v else
    aux (i+1) (v+vn) v
  in
  aux 0 v vn
;;
 

[edit] Oz

 fun{FibI N}   %% Iterative using Cell
   Temp = {NewCell 0}
   A = {NewCell 0}
   B = {NewCell 1}
 in    
   for I in 1..N do
     Temp := @A + @B
     A := @B
     B := @Temp
   end
   @A          %% return result
 end       

 fun{Fibi N}   %% Iterative(or Recursive?) by arguments swapping
   fun{FibIter N A B}
     if N == 0 then B
     else {FibIter N-1 A+B A} end
   end
 in    
   if N < 2 then N
   else {FibIter N 1 0} end
 end       

 fun{FibR N}   %% Simple Recursive
   if N < 2 then N
   else {FibR N-1} + {FibR N-2} end
 end       

[edit] Perl

#!/usr/bin/perl -w
 
my $a = 1;
my $b = $a;
 
my $target = 500;
 
for( my $n = 3; $n <= $target; ++$n )
{
        my $fib = $a + $b;
        if($fib < $b)
        {
                print "Overflow at $n\n";
                last;
        }
        print "F($n): $fib\n";
        $a = $b;
        $b = $fib;
}
 

[edit] Pop11

define fib(x);
lvars a , b;
    1 -> a;
    1 -> b;
    repeat x - 1 times
         (a + b, b) -> (b, a);
    endrepeat;
    a;
enddefine;

[edit] PostScript

Enter the desired number for "n" and run through your favorite postscript previewer or send to your postscript printer:

%#!PS

% We want the 'n'th fibonacci number
/n 13 def

% Prepare output canvas:
/Helvetica findfont 20 scalefont setfont
100 100 moveto

%define the function recursively:
/fib { dup 
       3 lt
         { pop 1 }
         { dup 1 sub fib exch 2 sub fib add }
       ifelse
    } def
    
    (Fib\() show n (....) cvs show (\)=) show n fib (.....) cvs show

showpage

[edit] Python

[edit] Iterative

def fibIter(n):
    if n <= 2:
        return 1
    fibPrev = 1
    fib = 1
    for num in xrange(2, n):
        temp = fib
        fib += fibPrev
        fibPrev = temp
    return fib

[edit] Recursive

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

[edit] Generative

def fibGen():
    f0, f1 = 0, 1
        while True:
            yield f0
            f0, f1 = f1, f0+f1

[edit] Example use

>>> fg = fibGen()
>>> for x in range(9): 
    print fg.next()
 
0
1
1
2
3
5
8
13
21
>>>

[edit] Scheme

[edit] Iterative

(define (fib-iter n)
  (do ((num 2 (+ num 1))
       (fib-prev 1 fib)
       (fib 1 (+ fib fib-prev)))
      ((>= num n) fib)))

[edit] Recursive

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

[edit] SNUSP

[edit] Iterative

 @!\+++++++++#  /<<+>+>-\       
fib\==>>+<<?!/>!\      ?/\      
  #<</?\!>/@>\?-<<</@>/@>/>+<-\ 
     \-/  \       !\ !\ !\   ?/#

[edit] Recursive

             /========\    />>+<<-\  />+<-\
fib==!/?!\-?!\->+>+<<?/>>-@\=====?/<@\===?/<#
      |  #+==/     fib(n-2)|+fib(n-1)|
      \=====recursion======/!========/

[edit] Tcl

proc fib {n} { if { $n < 3 } then { return 1 } else { return [expr [fib [expr $n-1]]+[fib [expr $n-2]]] } }

E.g.:

fib 7
 ;==> 13

[edit] UnixPipes

Uses fib and last as file buffers for computation. could have made fib as a fifo and changed tail -f to cat fib but it is not line buffered.

echo 1 |tee last fib ; tail -f fib | while read x
do
   cat last | tee -a fib | xargs -n 1 expr $x + |tee last
done

[edit] UNIX Shell

Works with: bash version 3

 
#!/bin/bash
 
a=0
b=1
max=$1
 
for (( n=1; "$n" <= "$max"; $((n++)) ))
do
  a=$(($a + $b))
  echo "F($n): $a"
  b=$(($a - $b))
done
 

[edit] V

Generate n'th fib by using binary recursion

[fib
   [small?] []
     [pred dup pred]
     [+]
   binrec].