Fibonacci Numbers

Definition of the Fibonacci numbers:
(Subscript[F, 0])=0, (Subscript[F, 1])=1
(Subscript[F, n])=(Subscript[F, n-1])+(Subscript[F, n-2]) for n>1

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

Computing the Fibonacci numbers recursively

Directly from the definition:

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

Calculate some Fibonacci numbers:

fib[2]
fib[5]
fib[6]

fib/@Range[0,10]

Computation Time

How fast is the recursive computation?

ClearSystemCache[];
Timing[fib[10]]

ClearSystemCache[];
Timing[fib[30]]

Make a function to return the runtime:

fibTime[n_]:=Module[{},
ClearSystemCache[];
Timing[fib[n]][[1]]
]

fibTime[30]

Map our function on to values up to 30:

timeList=fibTime/@Range[32]

ListPlot[timeList,AxesLabel->{"n","time"}]

ListPlot[Log[2,timeList],AxesLabel->{"n","time"}]

points=Transpose[{Range[32],Log[2,timeList]}][[21;;]]

model=LinearModelFit[points,x,x]

{intercept,slope}=model["BestFitParameters"]

Show[
ListPlot[Log[2,timeList],AxesLabel->{"n","time"}],
Plot[model["BestFit"],{x,0,32},PlotStyle->Orange]
]

Here is the exponential model:

m[x_]:=2^(slope*x+intercept)

m[x]

Show[
ListPlot[timeList,AxesLabel->{"n","time"}],
Plot[m[x],{x,0,32},PlotStyle->Orange]
]

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

m[50]

m[50]/(60*60)

Six hours to compute (Subscript[F, 50]).

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

m[100]

m[100]/(60*60*24*365)

ten million years???

How could we compute the Fibonacci numbers more efficiently?