Transwiki:Fibonacci number program

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Template:Inappropriate tone Template:Not verified Template:Importance

Merge-split-transwiki default.svg

A Wikibookian suggests that this book or chapter be merged into Fibonacci Number Program.
Please discuss whether or not this merge should happen on the discussion page.

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

[edit] 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*))) ;

The following is a recursive Fibonacci sequence calculator

(defun fib (x)
  (if (or (zerop x) (= x 1)) 1
    (+ (fib (- x 1)) (fib (- x 2)))))
 
(print (fib 10))

[edit] Haskell

The following Haskell code segment demonstrates how to calculate the Fibonacci sequence using an infinite list.

module Main where
import System.Environment

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

main = do
    args <- getArgs
    print (fibo !! (read(args!!0)-1))

[edit] Perl

The following Perl code segments demonstrate how to calculate the Fibonacci sequence using a 'for' loop, binary recursion, and iteration.

[edit] One example

#! /usr/bin/perl
use Math::BigInt;
 
my ($a, $b) = (0, 1);
for (;;) {
    print "$a\n";
    ($a, $b) = ($b, $a+$b);
}

[edit] 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).

[edit] Binary recursion with special Perl "caching", snippet

use Memoize;
memoize 'fibo';
sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

[edit] Iterative, snippet

sub fibo
{
    my ($n, $a, $b) = (shift, 0, 1);
    ($a, $b) = ($b, $a + $b) while $n-- > 0;
    $a;
}

[edit] Command line iterative

perl -Mbigint -le '$a=1; print $a += $b while print $b += $a'

[edit] PostScript

The following PostScript code segments demonstrate how to calculate the Fibonacci sequence using iteration and recursion.

[edit] 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

[edit] 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

[edit] Python

The following Python code segments demonstrate how to calculate the Fibonacci sequence using recursion, a generator, and a matrix equation.

[edit] Recursion

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

[edit] Generator

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

[edit] 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

\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}

and by using exponentiating by squaring.

[edit] Scheme

The following Scheme code segments demonstrate how to calculate the Fibonacci sequence using binary recursion and tail-end recursion.

[edit] Binary recursion, snippet

(define (fibo x)
 (if (< x 2)
   x
   (+ (fibo (- x 1))
      (fibo (- x 2)))))

Runs in Θ(F(n)) time, which is Ω(1.6n).

[edit] 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.

[edit] 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.

[edit] Display all, snippet

(define (fibo-run a b) 
  (display a)
  (newline)
  (fibo-run b (+ a b)))
 
(define fibo-run-all (fibo-run 0 1)))

[edit] Power of Phi

The following takes advantage of the fact that F_n \approx \frac{\phi^{n}}{\sqrt{5}}

(define fib
  (lambda (n)
    (let ((phi 1.6180339887498948482)          ; Predefined values of Phi (The golden Ratio)
          (root5 2.2360679774997896964))       ; And root 5, impedes accuracy, increases speed.
      (if (<= 0 n)
          (round (/ (expt phi n) root5))
          (error "Input must be greater than zero. " n)
       )
    )
  )
)

[edit] C/C++/Java

The following C/C++/Java code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration.

[edit] 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).

[edit] Iterative snippet

int fib(int n) {
  int first = 0, second = 1;
  while (n--)
  {
    int tmp = first+second;
    first = second;
    second = tmp;
  }
  return first;
}

[edit] Shorter iteration

This version depends on the identities:

F_{2n} = F_n\cdot(2F_{n-1}+F_n)
F_{2n+1} = F_n^2 + F_{n+1}^2


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.

[edit] Ada

The following Ada code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration.

The Fibonacci algorithms is fully explained in Ada Programming/Algorithms/Chapter 6 together with several alternative implemetnations.

[edit] Recursive

To see the full implementation inclusive test driver follow the "view" link.

File: fibonacci_1.adb (view, plain text, download page, browse all)
type Integer_Type is range 0 .. 999_999_999_999_999_999;
 
function Fib (n : Integer_Type) return Integer_Type is
begin
   if n = 0 then
      return 0;
   elsif n = 1 then
      return 1;
   else
      return Fib (n - 1) + Fib (n - 2);
   end if;
end Fib;

[edit] 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;

[edit] MatLab

The following MatLab code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration.

[edit] Recursive snippet

function F = fibonacci_recursive(n)
if n < 2 
    F = n;
else
    F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2);
end

[edit] 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;

[edit] PHP scripting language

The following PHP scripting language code segment demonstrates how to calculate the Fibonacci sequence.

[edit] 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 ->

[edit] Ruby

The following [Ruby programming language|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).map {|i| i.fib}.join(", ")

[edit] 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

or (one that actually works) for the first 100 numbers in the series

a = 1
b = 1
DO WHILE x < 100
PRINT a
f = a + b
a = b
b = f
x = x + 1
LOOP

[edit] PL/SQL

The following PL/SQL code segment demonstrates how to calculate the Fibonacci sequence using iteration.

[edit] Iterative snippet

CREATE OR REPLACE PROCEDURE fibonacci(lim NUMBER) AS
  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;

[edit] 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 F_n^{}.

[edit] Double recursion

f0a and f0b use the basic identity F_{n}^{} = F_{n-2}^{} + F_{n-1}^{}.   f0c uses a cache of previously computed values.   f0d depends on the identity F_{n+k}^{} = F_k F_{n+1} + F_{k-1} F_n, whence F_{2n}^{} = F_{n+1}^2 - F_{n-1}^2 and F_{2n+1}^{} = F_{n+1}^2 + F_{n}^2 obtain by substituting n and n + 1 for k.

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.
)

[edit] Single recursion

f1a=: 3 : 0
 {. y. f1a 0 1x
:
 if. *x. do. (x.-1) f1a +/\|.y. else. y. end.
)

f1b=: {.@($:&0 1x) : ((<:@[ $: +/\@|.@])^:(*@[))

[edit] Iteration

f2=: 3 : '{. +/\@|.^:y. 0 1x'

[edit] 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.'

[edit] Continued fraction

The numerator of the continued fraction [0; 1, ..., 1] (with n 1's) as a rational number.

f4=: {. @ (2&x:) @ ((+%)/) @ (0: , $&1x)

[edit] Taylor series

Taylor series coefficients of   x \over 1-x-x^2   and   {1 \over \phi} e^{x/2} {\sinh \phi x}

f5a=: (0 1&p. % 1 _1 _1&p.) t.
f5b=: (%-.-*:)t.

f5c=: (^@-: * 5&o.&.((-:%:5)&*)) t:

[edit] 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.

[edit] 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
)

[edit] Operations in Q[√5] and Z[√5]

Based on Binet’s formula

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}}

operations are done in 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&times) @ (-/) @ ((1r2 1r2,:1r2 _1r2)&pow)

f8b  =: {:@(1 1x&pow) % 2x&^@<:

[edit] See also

[edit] External links

Retrieved from "http://en.wikibooks.org/wiki/Transwiki:Fibonacci_number_program"
In other languages