Fibonacci number program

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). In general, however, a recursive Algorithm to compute Fibonacci numbers is extremely inefficient when compared to other algorithms, such as iterative or matrix equation algorithms.

=Common Lisp programming language=

== Calculating fibonacci through Lucas formula ==

(defun fib (n) (cond ((= n 0) 0) 1) (- (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 programming language examples =

==Lazy infinite list==

module Main where import System.Environment fibo = 1 : 1 : zipWith (+) fibo (tail fibo) main = do args 0; $a; }

==Command line iterative==

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

=PostScript example=

==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 programming language examples=

==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 n th Fibonacci number in Big O notation(logarithm N) time, from the matrix (mathematics) equation :egin{bmatrix} 1 & 1 \ 1 & 0 end{bmatrix}^n = egin{bmatrix} Fleft(n+1 ight) & F left(n ight) \ Fleft(n ight) & F left(n-1 ight) end{bmatrix}

and by using exponentiating by squaring.

=Scheme programming language examples=

==Binary recursion, snippet==

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

Runs in Big O notation(F( n )) time, which is Ω(1.6 n ).

==Tail recursion, 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 Big O notation( 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 Big O notation(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 programming language/C plus plus/Java programming language example=

==Recursive snippet==

int fib(int n) { if (n < 2) return n; else return fib(n-1) + fib(n-2); }

Runs in Big O notation(F( n )) time, which is Ω(1.6 n ).

==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:

:F_{2n} = F_ncdot(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.

=PHP scripting language example=

==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; # ---- } //

=Ruby programming language examples=

def fib(num) i, j = 0, 1 while i