# Fibonacci Sequence

A sequence described by LeonardoFibonacci, defined as f(1)=f(2)=1, f(n)=f(n-1)+f(n-2) for n>2. The first few terms are:

 1 1 2 3 5 8 13 21 34 55 89 144 233 377


For more on the sequence's properties, see http://mathworld.wolfram.com/FibonacciNumber.html.

The Fibonacci sequence is attributed originally to Indian mathematics. A number of credible sources support this assertion, including Wikipedia. See http://en.wikipedia.org/wiki/Fibonacci_sequence.

The Fibonacci numbers form a classic example for recursion:

In Scheme:

  (define (fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1))
(fib (- n 2))))))


In C:

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


But while elegant, this code is extremely inefficient (exponential)! The following iterative version runs in linear time:

In Scheme:

  (define (fib2 n)
(let loop
((m 0)
(k 1)
(count n))
(if (= count 0)
m
(loop k (+ m k) (- count 1)))))


In C:
  int fib2(int n) {
int m = 1;
int k = 0;
int i;

for (i = 1; i <= n; i++) {
int tmp = m + k;
m = k;
k = tmp;
}
return m;
}


ForthLanguage:
 : fib   0 1 rot 0 ?do  over + swap  loop drop ;


This can be improved further to an algorithm that runs in logarithmic time, that is, provided we're assuming that arithmetic operations take constant time. (Which is true only if your numbers are bounded or you want only limited precision.)

Generating the nth Fibonacci number requires you to generate on the order of n bits. There can't possibly be a way to do that in less than linear time.

True. Scheme code for the logarithmic-in-n sense could look something like this:

  (define (fib3 n)
(define (fib-iter a b u v count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (square u) (square v))
(+ (square v) (* 2 u v))
(/ count 2)))
(else (fib-iter (+ (* b v) (* a v) (* a u))
(+ (* b u) (* a v))
u
v
(- count 1)))))
(fib-iter 1 0 0 1 n))


By defining a square-able operator on the coefficient space, this achieves logarithmic-in-n behaviour in exactly the same way that an exponentiation operator could.

In Haskell the version is more elegant (YMMV):

We define a lazy list corresponding to the FibonacciSequence.

 fibs  = 0 : 1 : zipWith (+) fibs (tail fibs)


fibs is a list composed of 0, 1 and the sum of items from two lists, fibs itself, and all but the first element of fibs, exactly as the original definition

 fib n = fibs !! n


Here we say that the fibonacci number at n is the nth element of fibs. It's elegant and runs in linear time (modulo laziness issues, but they're implementation specific). -- DanielYokomiso

In wild contrast to the terse versions of Fibonacci that are possible in functional languages, I present an implementation in GuidoVanRobot, which does not have the luxury of variables. I assure you, this code actually works, as long as you leave plenty of beepers in the origin of the world:

    define face_north:
while not_facing_north:
turnleft

define face_east:
while not_facing_east:
turnleft

define face_west:
while not_facing_west:
turnleft

define face_south:
while not_facing_south:
turnleft

define move_north:
face_north
move

define move_east:
face_east
move

define move_west:
face_west
move

define move_south:
face_south
move

define go_home:
face_south
while front_is_clear:
move
face_west
while front_is_clear:
move

define move_northeast:
face_east
move
face_north
move

define move_southwest:
face_south
move
face_west
move

define go_past_end_of_beeper_diagonal:
go_home
while next_to_a_beeper:
move_northeast

define go_to_end_of_beeper_diagonal:
go_past_end_of_beeper_diagonal
move_southwest

define makebeeper:
go_home
pickbeeper
go_to_end_of_beeper_diagonal

define move_beepers_northeast:
while next_to_a_beeper:
pickbeeper
move_northeast
putbeeper
move_southwest
move_northeast

define copy_beepers_northeast:
go_to_end_of_beeper_diagonal
move_beepers_northeast

define double_beeper_at_home:
pickbeeper
go_home
pickbeeper

define drop_beeper_west_of_current:
go_past_end_of_beeper_diagonal
move_north
putbeeper
move_east

define move_beepers_to_3:
face_east
move
move
putbeeper

define move_beepers_to_4:
face_east
move
move
move
putbeeper

define copy_to_3:
copy_beepers_northeast
while next_to_a_beeper:
double_beeper_at_home
move_beepers_to_3
drop_beeper_west_of_current

define copy_to_4:
copy_beepers_northeast
while next_to_a_beeper:
double_beeper_at_home
move_beepers_to_4
drop_beeper_west_of_current

define pick_all_beepers:
while next_to_a_beeper:
pickbeeper

define put_all_beepers:
while any_beepers_in_beeper_bag:
putbeeper

go_home
face_east
move
move
pick_all_beepers
move
pick_all_beepers

go_to_end_of_beeper_diagonal
copy_to_3
copy_to_4
go_home
go_past_end_of_beeper_diagonal
do 2:
move_northeast
put_all_beepers
do 2:
move_west
pick_all_beepers
move_south
put_all_beepers

makebeeper
makebeeper
move_northeast
putbeeper
move_northeast
putbeeper
while next_to_a_beeper:



Surprisingly enough, there is also a simple non-recursive formula for the nth Fibonacci number (the ^ operator is exponentiation):

 fib(n) = (Phi^n - (-phi)^n) / sqrt(5).


where the GoldenRatios Phi and phi are defined as

  Phi = (1 + sqrt(5)) / 2.
-phi = (1 - sqrt(5)) / 2.


It is a simple proof by induction to show that this correctly gives the nth Fibonacci number. If calculating x^n runs in linear time for fixed x, this algorithm takes only linear time. Actually, it takes fewer than 2*lg n multiplications. See IntegerPowerAlgorithm. -- EricJablow

Since the number called "-phi" above is less than 1 in absolute value, it's easy to prove that fib(n) is the nearest integer to Phi^n/sqrt(5).

MemoIzation can make the recursive algorithm work in linear time. To do it in logarithmic time, reduce this to a matrix exponentiation problem:

 /0 1\ /F_{n-1} F_n    \    /F_n     F_{n+1}
|   | |               |  = |               |

\1 1/ \F_n     F_{n+1}/    \F_{n+1} F_{n+2}/


Here, F_{-1} = 1. Given that definition,

      n
/0 1\      /F_{n-1}  F_n
|   |    = |                |

\1 1/      \F_n      F_{n+1}/


and standard exponentiation techniques make this run in O(log n) arithmetic operations. Since F_n has O(n) binary digits, and you need to store only constantly many intermediate values, and since the bit-complexity of multiplication of n-bit numbers is n log n (the divide and conquer algorithms), you end up with O(log n) arithmetic operations, O(n) space, and O(n (log n)^2) bit-complexity.

Incidentally, don't be so sure that you need to compute n bits of a number to get the nth bit; there's an infinite series for pi where the denominators are powers of 16 and the numerators are sufficiently bounded that you can find the nth bit of the binary expansion of pi in O(log n) time.

The GeneratingFunction of the FibonacciNumbers? is:

\sum_{n=0}^{\infty} F_n x^n = \frac{x}{1 - x - x^2}.

On the other hand, the GoldenRatio method is fairly useless for precise computational work, because errors propagate. Suppose the computed version of F_{100} is off by 1. Then the computed version of F_{200} will be off by about F_{100}. Sorry about the quasi-TeX notation. -- EricJablow

All these algorithms are of course fun to write create and think of but ....

On the other hand, as very few uses of Fibonacci numbers require infinite precision arithmetic, it is often possible to remember all possible answers to all the possible questions and just use a look up table - constant time.

By sublime coincidence, the GoldenRatio is very close to the ratio of km to miles

for n = 3 to 11, and not far out after that....

      Fib(n)Miles = Fib(n+1)Kilometers


Not quite as applicable as double-and-add-thirty for C->F though.
• I may have missed something here. I always thought it was F = 9/5C + 32? Or is it that we're trying to say that F = 2C + 30 is a useful rough approximation?
• Well, let's try that ...
  |        (x2+30) (9/5+32)
|    C      F        F     Err
|    0     30       32      -2
|    1     32       33.8    -1.8
|    2     34       35.6    -1.6
|    3     36       37.4    -1.4
|    5     40       41      -1
|   10     50       50       0
|   15     60       59       1
|   20     70       68       2
|   30     90       86       4
|   38    106      100.4     5.6
|   40    110      104       6

Hmmm. A little sloppy, but not unusable. Faster in the head.

Implementing a generator for the FibonacciSequence introduced as a TestDrivenDevelopment exercise by CharliePoole: http://groups.yahoo.com/group/testdrivendevelopment/message/295

Here's an implementation of the FibonacciSequence I coded up in Python based on a new-ish algorithm I read in a journal article: http://pythonista.wordpress.com/2008/07/03/pure-python-fibonacci-numbers/

EditText of this page (last edited December 24, 2009) or FindPage with title or text search