Fibonacci Number Program
From Wikibooks, the open-content textbooks collection
Contents |
[edit] C
[edit] Recursive version
unsigned int fib(unsigned int n){
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}
[edit] Recursive version 2
unsigned int fib(unsigned int n){
return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
[edit] Lucas form
float fib(unsigned int n){
float fi = (1 + sqrt(5))/2;
return (pow(fi,(float)n) - pow(-fi,-(float)n))/sqrt(5);
}
[edit] Iterative version
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;
}
[edit] Exponentiation by squaring
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;
}
[edit] Alternate exponentiation by squaring
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;
}
[edit] C#
[edit] Iterative version
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);
}
[edit] Binet's formula
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);
}
[edit] Using long numbers
static Num FibbonaciNumber(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();
}
}
[edit] Erlang
fib(0) -> 0; fib(1) -> 1; fib(N) -> fib(N-1) + fib(N-2).
[edit] Arithmetic version
fib(N) ->
S = math:sqrt(5),
round(math:pow(((1 + S) / 2), N) / S).
algorithm taken from the Pascal "more efficient" version, below
[edit] F#
[edit] Simple recursive
let rec fib x = if x < 2 then x else fib(x - 1) + fib(x - 2)
This version overflows pretty quickly, to compute larger numbers Int64 or bigint can be used.
[edit] Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
[edit] Haskell
[edit] List version
fib n = fibs 0 1 !! n
where
fibs a b = a : fibs b (a + b)
[edit] Tail-recursive version
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)
[edit] Simple recursive version
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
For other versions, see Haskell/Overview.
[edit] Dyalog APL
[edit] Basic Tail-Recursive Version
fibonacci?{
??0 1
?=0:???
(1??,+/?)? ?-1
}
[edit] Array-Oriented Version
fibonacci?{+/{?!??}(??)-?IO}
[edit] Other Versions
See Fibonacci at the Dynamic Functions Database
[edit] Io
[edit] Generic method version
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
)
)
[edit] Polymorphc method version
Number fibonacci := method((self - 1) fibonacci + (self -2) fibonacci) 1 fibonacci = 1 0 fibonacci = 0
[edit] Java
[edit] recursive version
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);
}
[edit] 2nd recursive version
public int fib(int n)
{
if (n>1) return fib(n-1) + fib(n-2);
return n;
}
[edit] Iterative version
/**
* 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 (i=n ; i>2 ; i--) {
tmp = n2;
n2 = n1;
n1 = n1 + tmp;
}
return n2 + n1;
}
[edit] Memoized version
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]; }
[edit] Linotte
Livre : nombre Fibonacci
Les grands rôles :
A est un nombre valant 1
B est un nombre vide
C est un nombre
Paragraphe : on demande un nombre
Rôles :
Boucle est un nombre
Actions :
Boucle ?
De 2 à boucle , va vers somme
A !
Termine
Paragraphe : somme
Actions :
C = A + B
B = A
A = C
Reviens
[edit] Lexico (in spanish)
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)
}
[edit] Lua
function fib(n)
local a, b = 0, 1
while n > 0 do
a, b = b, a + b
n = n - 1
end
return a
end
[edit] recursive version
function fib(n) if n > 1 then n = fib(n - 1) + fib(n - 2) end return n end
[edit] Matlab
[1 0]*([1 1;1 0]^n)*[0 1]'
[edit] Maxima
[edit] Recursive version
fib(n):=
if n < 2 then
n
else
fib(n - 1) + fib(n - 2)
$
[edit] Lucas form
fib(n):=(%phi^n-(-%phi)^-n)/sqrt(5);
[edit] Iterative version
fib(n) := block(
[i,j,k],
i : 1,
j : 0,
for k from 1 thru n do
[i,j] : [j,i + j],
return(j)
)$
[edit] Exponentiation by squaring
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])
)$
[edit] O'Caml
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;;
[edit] Pascal
function F(n: integer): integer; begin case n of 1,2: Result:=1 else Result:=F(n-1)+F(n-2) end; end;
[edit] A bit more efficient:
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.
[edit] Iterative version also for negative arguments :
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;
[edit] Perl
sub fib {
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
[edit] recursive versions
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]);
}
[edit] Perl 6
1,1...&[+]
[edit] PHP
function generate_fibonacci_sequence( $length ) {
for( $l = array(0,1), $i = 2, $x = 0; $i < $length; $i++ )
$l[] = $l[$x++] + $l[$x];
return $l;
}
[edit] recursive version
function fib( $n ){
return ( $n?2 )
? $n
: fib( $n-1 )+fib( $n-2 );}
[edit] OOP version
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 . '
';
$this->Begin = $this->Next;
$this->Next = $Value;
}
}
}
$Fib = new fibonacci( 0, 6 );
echo $Fib->_do();
[edit] Python
[edit] Recursive version
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
[edit] Recursive with memoization
m = {0: 0, 1: 1}
def fib(n):
#assert n >= 0
if n not in m:
m[n] = fib(n-1) + fib(n-2)
return m[n]
[edit] Lucas form
def fib(n):
fi = (1 + sqrt(5))/2
return (fi**n - (-fi)**-n)/sqrt(5)
[edit] Iterative version
def fib(n):
i,j = 1,0
for k in range(1,n + 1):
i,j = j, i + j
return j
[edit] Exponentiation by squaring
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
[edit] REBOL
[edit] Recursive version
fib: func [n [integer!]] [
either n < 2 [n] [(fib n - 1) + (fib n - 2)]
]
[edit] Ruby
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
[edit] Generator
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
[edit] Arithmetic version
def f(n) ((((1+Math.sqrt(5))/2)**n)/Math.sqrt(5)+0.5).floor end
[edit] Memoized Version
fibmemo=Hash.new{|h,k| h[k-1]+h[k-2]}
h[0]=0
h[1]=1
def fib n
fibmemo[n]
end
[edit] Scheme
[edit] Tree-recursive version
(define (fib n)
(if (<= n 1)
n
(+ (fib (- n 1)) (fib (- n 2)))))
[edit] Iterative (tail-recursive) version
(define (fib n)
(define (iter a b count)
(if (<= count 0)
a
(iter b (+ a b) (- count 1))))
(iter 0 1 n))
[edit] UCBLogo
to fib :n output (cascade :n [?1+?2] 1 [?1] 0) end
[edit] recursive version
to fib :n if :n<2 [output 1] output (fib :n-1)+(fib :n-2) end
[edit] VB.NET
[edit] Array oriented version
Dim i As Integer = 2
Dim sequencelength As Integer = 20
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
[edit] Recursive Version
Public Function fibonacci(ByVal i as integer) As Integer
If i < 2 Then
Return i
Else
Return fibonacci(n-1) + fibonacci(n-2)
End If
[edit] Javascript
function fibonacci(n) {
var Phi=1.6180339887498948482;
var fibonacciNumber=0;
fibonacciNumber=Math.pow(Phi,n)/(Math.sqrt(5));
return Math.round(fibonacciNumber);
}
