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:

-- SteveHowell

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

define add_3_4: go_home face_east move move pick_all_beepers move pick_all_beepers

define add: go_to_end_of_beeper_diagonal copy_to_3 copy_to_4 add_3_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: add

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/

--PaulMiller

CategoryMath