On the Linear Time Algorithm For Finding Fibonacci Numbers

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!