On the Linear Time Algorithm For Finding Fibonacci Numbers

Hi all!

Just a note about the Python code:

def LinearFibonacci(n):
  fn = f1 = f2 = 1
  for x in xrange(2, n):
    fn = f1 + f2
    f2, f1 = f1, fn
  return fn

fn is not needed here, and if one opts to use it anyway, need not be initialised before the loop. Furthermore, the variable names "f1" and "f2" are confusing here, because I expect f2 to be bigger than f1. I would write this code as:

def LinearFibonacci(n):
  curr, next = 1, 1
  for x in xrange(2, n):
    next, curr = ((next+curr),next)
  return next

Tested and works.

Without reading your analysis it's clear that LnearFibonacci computes all the fib numbers up to "n", and then throws all but the last number away. Next time it recomputes the same numbers again, so of course you get complexity O(n^2).

If the function filled an array then computation would be linear and only one call would be required.

You can always use the O(logN) algorithm to compute nth fibonacci number (or O(NlogN) using your analysis). Your article's point is that big numbers (ie. not implemented in the hardware) don't have constant time operations. :|

excuse me sir,
I m ram sandesh.I m doing my B.tech degree.I m interested in knowing this algorithm with time complexity of O(log n).can u please mail me back graph & algorithm.i guess u have done with matrix multiplication method...

Actually, the «O(log n)» algorithm is not O(n log n) but O(n^a) where a single call is also O(n^a). If you use naïve long multiplication, a is 2; if you use Karatsuba multiplication, a is log(3)/log(2), which is better.

yes, LinearFibonacci() is O(n), but you run it m number of times which means the total computation is O(mn) time. And on each run of LinearFibonacci() m = n so that's O(n^2). Why should that be a surprise?

Also, Richie is correct: if you cached your previous results, it would be O(n). You've only come up with an O(n^2) algorithm for a problem that could be solved in O(n) time.

Richie: your point about throwing the results away is valid when multiple calls to LinearFibonacci are made. However, it seems that Peteris considers only the performance of single call to LinearFib; by modifying LinearFib according to your suggestion the running time will still be quadratic.

However your point is noted when the application requires multiple Fibonacci numbers - dropping previously computed results is a bit foolish then.

It seems beside the point to bring up caching the results. This is a very good analysis of the given algorithm

Corey, Richie: I believe you are incorrect. The following is a naive O(n^2) algorithm for calculating the nth fibonacci number:

def fib(n):
if n == 0 or n == 1:
return n
else: return fib(n-1) + fib(n-2)

However, the OP's algorithm simply performs n additions to find the nth fibonacci number -- there is no recursion. To work out [LinearFibonacci(x) for x in xrange(1,n)] would be O(n^2), but LinearFibonacci(n) itself is just O(n) (counting additions as constant time).

As Madars says, I consider only the performance of a single call to LinearFibonacci.

For example, if I did a call to LinearFib(1000) and LinearFib(2000), from the analysis algorithm I would expect that LinearFib(2000) would take twice as much time as LinearFib(1000). But in practice it takes four times as much time. The caching would not help here, as you would still have to iterate from 1000 to 2000 without caching!

Corey & Richie - you are wrong. It's only the test where the code iterates through 1 to 16 for the parameters. The points on the graph are the time take to complete the operation for a single value of N.

Alexandru hits the nail on the head - "big numbers don't have constant time operations"

Common sense: theory does not (necessarily) match practice when the theoretical assumptions don't hold.

http://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html

Not sure if this is still quadratic or not, but either way it's going to be an effective speed-up.

How about a closed form evaluation?

F(n) = (Phi^n - (1-Phi)^n) / sqrt(5)

Where Phi is the Golden Ratio.
Phi = (1 + sqrt(5)) / 2

To David: It's not a naive O(N^2) algorithm, it's actually O(Fib(n)) (assuming constant time addition).

To Peteris: Nice analysis :) It was well worth every byte :)

Thanks for the analysis, sure surprised me.

If possible, I'd like to hear how you generated that graph and those formulas. I generally use gnuplot and latex/lyx, but I'm sure there are numerous tips I could learn from you :)

Why have you compared the running time of Fib(n) to Fib(n)? There's no reason why this should give you any information about the complexity of the function. You must have meant to compare the running time of Fib(n) to n, which should be linear. It's no surprise that you found a quadratic relationship since the running time is linear in n and Fib(n) is quadratic in n, so Fib(n) is quadratic with respect to the running time.

All you've done is point out that you have to know what you're doing and not blindly follow your textbook and it's assumptions.

its*

John Tantalo, no, I compared n to running_time(Fib(n)).

Dror Levin, here is how I did it:

First I created a Python program to time execution for an individual n:

#!/usr/bin/python
#

import sys
from time import time

def LinearFibonacci(n):
  """ Finds n-th Fibonacci number. n >= 1 """
  fn = f1 = f2 = 1
  for x in xrange(2, n):
    fn = f1 + f2
    f2, f1 = f1, fn
  return fn

if __name__ == '__main__':
  args = sys.argv[1:]
  if len(args)<1:
    print "Usage: prog.py <fib>"
    sys.exit(1)
  fib = int(args[0])
  start = time()
  LinearFibonacci(fib)
  end = time()
  print "%d, %f" % (fib, end-start)

Next I created a loop in shell to run the program 10 times for each individual value on n:

for ((i=1;i<=200000;i+=1000)); do
  for ((j=1;j<=10;j++)); do
    ./linear.py $i >> linear.txt;
    sleep 0.1
  done;
done;

Next, I used an Awk program to calculate the average of 10 runs:

awk -F, '
  NR==1{this=$1;prev=this}
  {this=$1}
  this!=prev{printf "%d, %f\n", prev, a/10; prev=this; a=0}
  {a+=$2}
  END {printf "%d, %f\n", prev, a/10}'
  linear-txt > linear-averaged.txt

Finally I used the following script for GnuPlot to create the graph and fit the data with a quadratic function:

filename = "linear-joined.txt"
f(x) = a*x**2 + b*x
fit f(x) filename via a, b
set title "Running time of Linear Fibonacci algorithm"      
set xlabel "n-th fibonacci number" tc lt 3
set ylabel "running time in seconds" tc lt 3 
set tics font "arial, 7"
set terminal gif size 480,360 font arial 9
set output './linear-fibonacci.gif'
plot filename with points pointtype 1 pointsize 0.6 title "LinearFibonacci(n)", f(x) title "O(x^2) approximation"

For the formulas I used this online latex generator.

Have fun!

Since you've introduced the matrix form for the fibonacci recurrence, I think it would interest your readers to decompose to PDP^-1 form and thereby derive the closed form formula one reader mentions.

I compared n to running_time(Fib(n))

Then why does the plot have "n-th fibonacci number" on the x axis? This should be "n".

And why do you say "the plot of LinearFibonacci(n) vs. running time of LinearFibonacci(n) should be a line"? This should be "the plot of n vs. running time of LinearFibonacci(n) should be a line".

John, that's a mistake right there. Will fix it now! Thanks for spotting.

I see by your sample code that you were indeed comparing n to the running time of fib(n). Please correct your graphs and analysis!

Learn all about memoization =]
http://en.wikipedia.org/wiki/Memoization

John Tantalo, I have now corrected the graph and analysis.

Brandon Pelfrey, sorry, but this time it has nothing to do with memoization! See one of my previous comments above!

But if we used a 128-bit processor (or created instructions to do a single-step 128-bit add) and updated our language to support these 128-bit integers, we'd return to O(n) time, since adding is once again an O(1) operation. I think that most modern processors support special case 128-bit-adds through SSE - so it's likely your Python Big-Number library that's the bottleneck?

Zach, you're missing the point, which is that in the real world, you need to take the finite capabilities of your computational unit into consideration when considering the order of your algorithm. Great analysis Peteris!

Zach, you're also just plain wrong. 128-bit integers only get you up to around f(200) or so (too lazy to calculate the exact number of bits, but it's close). Fibonacci numbers are *big*.

Anyway, any decent implementation will have a short linear part at the beginning, and then an n^2 part after that.

Unless, of course, you can play tricks to get your computation time down to constant again. No existing processor can do this, but a processor that had a configurable number of bits could stay linear for as long as it had computation units. Again, difference between theory and practice.

No technically is it exponential. This is a common problem used to trip up CS grad students during their qualifying exam. When finding the complexity of an algorithm, you must consider the number of steps with respect to the input. The input is log(n) and the number of steps in the for loop is n, hence the algorithm is exponential with respect to the input.

This is why the naive primality test:

isPrime(int n) {
 for (i=2;i<=n/2;i++) {
   if (n%i==0) return false;
 }
 return true;
}

fails to be O(n). Although long suspected to be in P, primality was not classified as such until the recent discovery of the AKS primality test.

See: http://en.wikipedia.org/wiki/Pseudo-polynomial_time for more info

Yes, in my comment I assumed addition time is constant. With long precision numbers it is not. So my comment was not entirely correct. :)

Another practical issue theoretical computer scientist often ignore (apart from machine code word sizes) is the memory hierarchy. I.e. the evaluation of an algorithm is ignorant of the locality of memory accesses. But in practice this makes a HUGE difference.

@ZachPruckowski: the 187th fibonacci number cannot be expressed in one 128-bit register, which renders the point rather moot.

The point is that physical limitation of the machine can and will increase computational time, and can make things inaccurate. Not realizing that fibonacci sequence can quickly exceed your register size can lead to unexpected increase in computational time, and not taking care while calculating your floating point calculation can cause erroneous results.

Just like the good old days, when int multiplications ran in time proportional to the number of bits set in the second operand ... and divisions ran *eventually*.

Interesting analysis & shows the (occasional) perils of abstraction. Thanks.

-----N

>In this article I’d like to show how the theory does not always match the practice

Just be careful to pick right theory. Theory saying that f1+f2 takes a constant time is useful in some situation, not in this one. You picked the right theory and it matches the practice.

Hi Cantonmat,

I looked at this a while ago because I was annoyed about stupid implementations of Fibonacci. I quickly noticed that the value of Fn quickly overflows fixed precision datatypes so as you point out you can't use fixed precision arithmetic and have to take account the non-trivial complexity of your operations.

I looks at the real complexity for Binet's formula and implement the better identity used by GMP
F2k = (Fk+1)^2 − (Fk−1)^2

Glimpses of Lisp: Fibonacci and the Netflix prize

As ZachPruckowski and other pointed out, the analysis is misleading. The skew is due to the big integer computation and has no bearing on the theory of asymptotic analysis. The syntactical sugar of python disguising the underlying big number implementation has mislead your analysis.
It is like expecting length(string) is O(1) operation, because you could express it as an say # operator.

The fact that several commentators are still confused show how deep rooted this misconception is.

Possibly one the most "simple yet insightful" posts I've read. Great work!