Fibonacci sequence
From Rosetta Code
Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they know.
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.
Contents |
[edit] References
[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 92nd 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].
Categories: Clarified and Needing Review | Programming Tasks | Arithmetic operations | Recursion | Ada | BASIC | Befunge | Brainf*** | C++ | GMP | D | E | Forth | Fortran | Haskell | IDL | J | Java | JavaScript | Joy | Logo | Mathematica | MAXScript | OCaml | Oz | Perl | Pop11 | PostScript | Python | Scheme | SNUSP | Tcl | UnixPipes | UNIX Shell | V

