Fibonacci sequence
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci sequence is a sequence Fn of natural numbers defined recursively:
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.
References
Ada
<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; </ada> Smaple output:
0 1 1 2 3 5 8 13 21 34 55
BASIC
Iterative
<qbasic>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</qbasic>
Recursive
<qbasic>FUNCTION recFib (n) IF (n <= 2) THEN
recFib = 1
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF END FUNCTION</qbasic>
Befunge
00:.1:.>:"@"8**++\1+:67+`#@_v
^ .:\/*8"@"\%*8"@":\ <
C++
Using unsigned int, this version only works up to 48 before fib overflows. <cpp>#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;
} </cpp>
This version does not have an upper bound.
<cpp>#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;
}</cpp>
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.
<d>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) ) ;
}</d> Output for n = 83:
Fib( 83) = D : 99194853094755496 <- 61305790721611591 + 37889062373143906 I : 99194853094755497 <- 61305790721611591 + 37889062373143906 O : 99194853094755497 <- 61305790721611591 + 37889062373143906
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.)
Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
Fortran
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
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
Haskell
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
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"
IDL
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.
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)
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).
J
See J Wiki: Fibonacci Sequence.
Java
Iterative
<java>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;
}</java>
Recursive
<java>public static long recFibN(int n){
if(n <= 2) return 1;
return recFibN(n-1) + recFibN(n-2);
}</java>
Analytic
This method works up to the 92nd Fibonacci number. After that, it goes out of range. <java>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)); }</java>
JavaScript
Recursive
One possibility familiar to Scheme programmers is to define an internal function for iteration through anonymous tail recursion: <javascript> function fib(n) {
return function(n,a,b) {
return n>0 ? arguments.callee(n-1,b,a+b) : a;
}(n,0,1);
}</javascript>
Iterative
<javascript> 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));</javascript>
Joy
DEFINE fib ==
[small]
[]
[pred dup pred]
[+]
binrec .
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
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]
MAXScript
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
)
)
Recursive
fn fibRec n =
(
if n <= 2 then
(
1
)
else
(
fibRec (n - 1) + fibRec (n - 2)
)
)
OCaml
Iterative
<ocaml>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</ocaml>
Recursive
<ocaml>let rec fib_rec n =
if n <= 2 then 1 else fib_rec (n - 1) + fib_rec (n - 2)</ocaml>
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:
<ocaml> 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
</ocaml>
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
Perl
<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;
} </perl>
Pop11
define fib(x);
lvars a , b;
1 -> a;
1 -> b;
repeat x - 1 times
(a + b, b) -> (b, a);
endrepeat;
a;
enddefine;
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
Python
Iterative
<python>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</python>
Recursive
<python>def fibRec(n):
if n <= 2:
return 1
else:
return fibRec(n-1) + fibRec(n-2)</python>
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
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
V
Generate n'th fib by using binary recursion
[fib [small?] [] [pred dup pred] [+] binrec].