Compute Fibonacci Numbers from the Definition

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

Compute some Fibonacci numbers:

{fib[5], fib[7], fib[8]}

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

Map[fib,Range[0,10]]

fib/@Range[0,10]

How fast is this computation?

Timing[fib[15]]

Timing[fib[20]]

Timing[fib[30]]

Make a function to extract the time from the pair returned by Runtime:

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

Note that Timing returns a list of two elements, and [[1]] extracts the first item from the list.

myFibTime[30]

fibTimes=myFibTime/@Range[30]

Plot the Fibonacci runtime:

ListPlot[fibTimes]

Is this exponential growth in runtime? Why?

Iterative Version of Fibonacci

goal : computeFib[n] returns the nth Fibonacci number (Subscript[F, n])

computeFib[n_]:=Module[{a=0,b=1,next},
Do[
next=a+b; (* compute the next Fibonacci number *)
a=b;                (* shift b to a *)
b=next,          (* shift next to b *)
n-1   (* repeat n-1 times *)
];
b (* return value *)
]

Try it out:

computeFib/@Range[10]

computeFib[100]

Timing[computeFib[1000]]

Ratios of Consecutive Fibonacci Numbers

What is ((Subscript[F, n])/(Subscript[F, n-1]))? What does this ratio tend to as n increases?

computeFib[10]/computeFib[9] //N

computeFib[20]/computeFib[19] //N

computeFib[19]/computeFib[20] //N

N[GoldenRatio,20]

N[1/GoldenRatio,20]

Let's compute a bunch of ratios all at once. Start by making a big list of Fibonacci numbers:

m=100;
fibs=computeFib/@Range[m];

Compute a lot of ratios:

numerators=fibs[[2;;m]];
denominators=fibs[[1;;m-1]];
ratios=numerators/denominators;
N[ratios,20]