Fibonacci numbers

MATH 242 Modern Computational Mathematics

The Fibonacci numbers are one of the mostly widely studied sequences in mathematics. Their definition is recursive.

(Subscript[F, 0])=0, (Subscript[F, 1])=1
(Subscript[F, n])=(Subscript[F, n-1])+(Subscript[F, n-2])      for n>1

The first few Fibonacci numbers: 0,1,1,2,3,5,8,13,21,34,55,...

Computing the Fibonacci numbers recursively

Let’s start by computing these directly from the definition.

fib[0]=0
fib[1]=1
fib[n_]:=fib[n-1]+fib[n-2]

Calculate a few Fibonacci numbers:

fib[5]

fib[10]

Compute (Subscript[F, 0]), (Subscript[F, 1]), (Subscript[F, 2]), ..., (Subscript[F, 10]):

Table[fib[n],{n,0,10}]

We could also use the /@ shorthand:

fib/@Range[0,10]

Computation Time

How fast is this recursive computation? Use the Timing function. Start with n=10.

Timing[fib[10]]

The computation time is very close to zero. What about larger values? Try n=30.

Timing[fib[30]]

Let’s make a function to extract the runtime from the pair returned by the Timing function.

fibTime[n_]:=Timing[fib[n]][[1]]

fibTime[30]

Evaluate this function on the values n=1,2,...32.

nMax=32;
myFibTimes=fibTime/@Range[nMax]

Make a plot of the Fibonacci runtimes:

ListPlot[myFibTimes,AxesLabel->{"n","time (seconds)"}]

What is the shape of this plot?

How long would it take to compute the 50th Fibonacci number in this way? The 100th Fibonacci number?

If we think the plot above looks roughly exponential, let’s try a log transform. We can simply use e as the base.

Log[myFibTimes]

ListPlot[Log[myFibTimes]]

The first several runtimes are nearly zero, but after that the runtime plot looks nearly linear. What linear equation approximates this plot?

x1=22
y1=Log[myFibTimes[[x1]]]

x2=32
y2=Log[myFibTimes[[x2]]]

slope=(y2-y1)/(x2-x1)

intercept=y1-slope*x1

Show[
ListPlot[Log[myFibTimes],AxesLabel->{"n","log(runtime)"}],
Plot[slope*x + intercept,{x,0,34},PlotStyle->Orange]
]

Now let's undo the transformation to plot an exponential function along with our original runtime data. Our exponential function should be: 
(e^(slope · x + intercept))

expModel[x_]:=Exp[slope*x+intercept]

Show[
ListPlot[myFibTimes,AxesLabel->{"n","runtime (seconds)"}],
Plot[expModel[x],{x,0,nMax},PlotStyle->Orange,PlotRange->All]
]

Now we can determine how long it would take to compute (Subscript[F, 50]):

expModel[50]

%/(60*60)

How long would it take to compute (Subscript[F, 100])?

expModel[100]

%/(60*60*24*365)

Questions for discussion:
   Why is the previous computation so slow?
   How could we compute the Fibonacci numbers more efficiently?

Discuss these questions with your classmates. Try to think of a more efficient algorithm for computing the Fibonacci numbers.

computeFib[n_]:=Module[
(* local variables *)
{a=0, b=1, next=1},
(* main loop *)
Do[
next=a+b;
a=b;
b=next,
n-1
];
(* return value *)
next
]

computeFib/@Range[10]

computeFib[1]

computeFib[50]

computeFib[100]

Ratios

N[computeFib[50]/computeFib[49],40]