Fibonacci Numbers

Definition: (Subscript[F, 0])=0, (Subscript[F, 1])=1, (Subscript[F, n])=(Subscript[F, n-1])+(Subscript[F, n-2])

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

Try it out:

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

fib/@Range[0,10]

Computation Time

Timing[fib[10]]

Timing[fib[30]]

Set up a function to measure the computation time of (Subscript[F, n]):

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

Try it out:

timeFib[30]

Make a list of runtimes:

timeVals=timeFib/@Range[30]

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

points=Transpose[{Range[30],Log[2,timeVals]}][[20;;]]

model=LinearModelFit[points,x,x]

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

intercept

slope

Show[
ListPlot[Log[2,timeVals]],
Plot[model["BestFit"],{x,0,30},PlotStyle->Orange]
]

Nonlinear model:

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

m[x]

Show[
ListPlot[timeVals,AxesLabel->{"n","time (seconds)"}],
Plot[m[x],{x,1,30},PlotStyle->Green]
]

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

m[50]

m[50]/(60*60)

4 hours???

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

m[100]

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

2 million years?

Demo

Adding elements to a list:

sampleList={0}

Append[sampleList,5]

sampleList

AppendTo[sampleList,5]

AppendTo[sampleList,7]

sampleList

Interesting

FunctionExpand[Fibonacci[x]]