Fibonacci number program
From Free net encyclopedia
Template:Inappropriate tone Template:Not verified Template:Importance
In many beginning computer science courses, an introduction to the concept of recursion often includes a program to calculate and print Fibonacci numbers (or computing the factorial of a number). The following list includes examples of code in various programming languages that will calculate the Fibonacci sequence.
Contents |
Common Lisp
The following Common Lisp code segment demonstrates how to calculate the Fibonacci sequence using Lucas' formula.
(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*))) ;
Haskell
The following Haskell code segment demonstrates how to calculate the Fibonacci sequence using an infinite list.
fibo = 0 : 1 : zipWith (+) fibo (tail fibo)
Perl
The following Perl code segments demonstrate how to calculate the Fibonacci sequence using a 'for' loop, binary recursion, and iteration.
One example
#! /usr/bin/perl
use bigint;
my ($a, $b) = (0, 1);
for (;;) {
print "$a\n";
($a, $b) = ($b, $a+$b);
}
Binary recursion, snippet
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
use Memoize;
memoize 'fibo';
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}
Iterative, snippet
sub fibo
{
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
Command line iterative
perl -Mbigint -le '$a=1; print $a += $b while print $b += $a'
PostScript
The following PostScript code segments demonstrate how to calculate the Fibonacci sequence using iteration and recursion.
Iterative
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
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
Python
The following Python code segments demonstrate how to calculate the Fibonacci sequence using recursion, a generator, and a matrix equation.
Recursion
def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)
Generator
def fib():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
Matrix equation
def mul(A, B):
a, b, c = A
d, e, f = B
return a*d + b*e, a*e + b*f, b*e + c*f
def pow(A, n):
if n == 1: return A
if n & 1 == 0: return pow(mul(A, A), n/2)
else: return mul(A, pow(mul(A, A), (n-1)/2))
def fib(n):
if n < 2: return n
return pow((1,1,0), n-1)[0]
This calculates the nth Fibonacci number in O(log N) time, from the matrix equation
- <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n =
\begin{bmatrix} F\left(n+1\right) & F \left(n\right) \\
F\left(n\right) & F \left(n-1\right) \end{bmatrix}
</math> and by using exponentiating by squaring.
Scheme
The following Scheme code segments demonstrate how to calculate the Fibonacci sequence using binary recursion and tail-end recursion.
Binary recursion, snippet
(define fibo
(lambda (x)
(if (< x 2)
x
(+ (fibo (- x 1)) (fibo (- x 2))))))
Runs in Θ(F(n)) time, which is Ω(1.6n).
Tail-end recursive, snippet
(define (fibo x)
(define (fibo-iter x a b)
(if (= x 0)
a
(fibo-iter (- x 1) b (+ a b))))
(fibo-iter x 0 1))
Runs in Θ(n) time.
Tail-end recursive, snippet
(define (fib n)
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* 2 p q))
(+ (* p p) (* q q))
(/ count 2)))
(else (fib-iter (+ (* (+ a b) p) (* a q))
(+ (* a p) (* b q))
p
q
(- count 1)))))
(fib-iter 1 0 1 0 n))
Suggested by Structure and Interpretation of Computer Programs. Runs in Θ(log(n)) time.
Display all, snippet
(define (fibo-run a b) (display a) (newline) (fibo-run b (+ a b)))
(define fibo-run-all (fibo-run 0 1)))
C/C++/Java
The following C/C++/Java code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration.
Recursive snippet
int fib(int n) {
if (n < 2)
return n;
else
return fib(n-1) + fib(n-2);
}
Runs in Θ(F(n)) time, which is Ω(1.6n).
Iterative snippet
int fib(int n) {
int first = 0, second = 1;
while (n--)
{
int tmp = first+second;
first = second;
second = tmp;
}
return first;
}
Shorter iteration
This version depends on the identities:
- <math>F_{2n} = F_n\cdot(2F_{n-1}+F_n)</math>
- <math>F_{2n+1} = F_n^2 + F_{n+1}^2</math>
Using these tightens up the iteration. Instead of iterating n times to calculate F(n), this function iterates only log(n) times:
unsigned fib (unsigned n)
{
unsigned a = 1, b = 0;
unsigned i = 0x8000;
while (i) {
unsigned aa;
aa = n&i ? (2*b+a)*a : a*a+b*b;
b = n&i ? a*a+b*b : b*(2*a-b);
a = aa;
i >>= 1;
}
return b;
}
It is essentially equivalent to the versions that employ matrix arithmetic, but with redundant calculations eliminated. Note that this method only makes sense for high-precision calculations where the benefit of an O(log n) algorithm outweighs the extra complexity. Since F(48) exceeds 232 - 1, no ordinary C program with 32-bit integers can calculate F(n) for n ≥ 48, and the sophisticated algorithm in this version is just over-engineering.
Ada
The following Ada code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration.
Recursive snippet
function fib(n : integer) return integer is
begin
if n < 2 then
return n;
else
return fib(n-1) + fib(n-2);
end if;
end fib;
Iterative snippet
function fib(n : integer) return integer is
first : integer := 0;
second : integer := 1;
tmp : integer;
begin
for i in 1..n loop
tmp := first + second;
first := second;
second := tmp;
end loop;
return first;
end fib;
MatLab
The following MatLab code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration.
Recursive snippet
function F = fibonacci_recursive(n)
if n < 2
F = n;
else
F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
end
Iterative snippet
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;
PHP scripting language
The following PHP scripting language code segment demonstrates how to calculate the Fibonacci sequence.
Contained snippet
function generate_fibonacci_sequence( $length, $method = 0 ) {
# ----
if( $method == 0 ):
// -- standard addition - limited by the capacity (int)
for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
$l[] = $l[$x++] + $l[$x];
elseif( $method == 1 ):
// -- arbitrary precision addition - more process intensive
for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ )
$l[] = bcadd($l[$x++], $l[$x]);
endif;
return $l;
# ----
} // <- generate_fibonacci_sequence ->
Ruby
The following Ruby code segments demonstrate how to calculate the Fibonacci sequence.
def fib(num)
i, j = 0, 1
while i <= num
yield i
i, j = j, i + j
end
end
fib(10) {|i| puts i}
The algorithm can also be defined on the open Integer class:
class Integer
def fib
if self < 2 then
fib = self
else
fib, f1 = 1, 1
(self-1).times do
fib, f1 = f1, f1 + fib
end
end
fib
end
end
puts (1...10.to_a.map {|i| i.fib}).join(", ")
QBasic/VisualBasic
The following QBasic/Visual Basic code segments demonstrate how to calculate the Fibonacci sequence.
n = 1 m = 1 FOR x = 1 TO 10 n = m o = m + n m = o n = o PRINT n NEXT x
or
x = 1 y = 1 FOR x = 1 to 100 z = x + y x = y y = z PRINT z + 1 NEXT x
PL/SQL
The following PL/SQL code segment demonstrates how to calculate the Fibonacci sequence using iteration.
Iterative snippet
PROCEDURE fibonacci(lim NUMBER) IS
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;
J
The following J code segments demonstrate how to calculate the Fibonacci sequence using double recursion, single recursion, iteration, power of phi, continued fraction, Taylor series, sum of binomial coefficients, matrix power, and operations in Q[√5] and Z[√5].
All of the following J examples generate <math>F_n^{}</math>.
Double recursion
f0a and f0b use the basic identity <math>F_{n}^{} = F_{n-2}^{} + F_{n-1}^{}</math>. f0c uses a cache of previously computed values. f0d depends on the identity <math>F_{n+k}^{} = F_k F_{n+1} + F_{k-1} F_n</math>, whence <math>F_{2n}^{} = F_{n+1}^2 - F_{n-1}^2</math> and <math>F_{2n+1}^{} = F_{n+1}^2 + F_{n}^2</math> obtain by substituting <math>n</math> and <math>n+1</math> for <math>k</math>.
f0a=: 3 : 'if. 1<y. do. (y.-2) +&f0a (y.-1) else. y. end.'
f0b=: (-&2 +&$: -&1) ^: (1&<)
F=: 0 1x
f0c=: 3 : 0
if. y. >: #F do. F=: F,(1+y.-#F)$_1 end.
if. 0 <: y.{F do. y.{F return. end.
F=: F y.}~ t=. (y.-2) +&f0c (y.-1)
t
)
f0d=: 3 : 0 if. 2 >: y. do. 1<.y. else. if. y. = 2*n=.<.y.%2 do. (n+1) -&*:&f0d n-1 else. (n+1) +&*:&f0d n end. end. )
Single recursion
f1a=: 3 : 0
{. y. f1a 0 1x
:
if. *x. do. (x.-1) f1a +/\|.y. else. y. end.
)
f1b=: {.@($:&0 1x) : ((<:@[ $: +/\@|.@])^:(*@[))
Iteration
f2=: 3 : '{. +/\@|.^:y. 0 1x'
Power of phi
Power of the golden ratio phi. Because of the limited precision of 64-bit IEEE floating-point numbers this method is good only for n up to 76.
f3=: 3 : '<. 0.5 + (%:5) %~ (2 %~ 1+%:5)^y.'
Continued fraction
The numerator of the continued fraction [0; 1, ..., 1] (with n 1's) as a rational number.
f4=: {. @ (2&x:) @ ((+%)/) @ (0: , $&1x)
Taylor series
Taylor series coefficients of <math> x \over 1-x-x^2 </math> and <math>{1 \over \phi} e^{x/2} {\sinh \phi x}</math>
f5a=: (0 1&p. % 1 _1 _1&p.) t. f5b=: (%-.-*:)t.
f5c=: (^@-: * 5&o.&.((-:%:5)&*)) t:
Sum of binomial coefficients
The second variant below sums the back-diagonals of Pascal‘s triangle as a square upper triangular matrix.
f6a=: i. +/ .! i.@-
f6b=: [ { 0: , +//.@(!/~)@i.
Matrix power
Computing the n-th power of the lower triangular unit matrix by repeated squaring.
f7=: 3 : 0
x=. +/ .*
{.{: x/ x~^:(I.|.#:y.) 2 2$0 1 1 1x
)
Operations in Q[√5] and Z[√5]
Based on Binet’s formula
- <math>F_n = {1\over\sqrt 5} \left(\left( {{1+\sqrt 5}\over 2}\right)^n -
\left( {{1-\sqrt 5}\over 2}\right)^n \right)
= {{(1+\sqrt 5)^n-(1-\sqrt 5)^n} \over {2^n \sqrt 5}} </math>
operations are done in [[Field extension|Q√5] and Z[√5] with powers computed by repeated squaring.
times=: (1 5&(+/ .*)@:* , (+/ .* |.)) " 1
pow =: 4 : 'times/ 1 0 , times~^:(I.|.#:y.) x.' " 1 0
f8a =: {. @ (0 1r5×) @ (-/) @ ((1r2 1r2,:1r2 _1r2)&pow)
f8b =: {:@(1 1x&pow) % 2x&^@<:
See also
- Fibonacci number
- Golden ratio
- Hello world program (Unrelated to the Fibonacci numbers, but contains many programming examples.)