A few useful items for the π Project

The Range function gives a list of integers:

Range[10]

Range[4,10]

Recall that we can make a list using the Table function:

Table[ CatalanNumber[n], {n,1,10}]

Similarly the Map function lets us evaluate a function on a specified list:

Map[ CatalanNumber, {4,5,6} ]

Map[CatalanNumber, Range[10]]

Map also has a shorthand operator:

CatalanNumber/@ {4,5,6}

CatalanNumber/@Range[10]

Plotting a list is easy with ListPlot:

alist=CatalanNumber/@Range[10]

ListPlot[alist]

Fibonacci Numbers

First we compute the Fibonacci numbers recursively. We will use an indexed variable:

fib[0]=0
fib[1]=1
fib[n_]:=fib[n-1]+fib[n-2] (* recursive definition *)

?fib

Try it out:

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

fib/@Range[0,10]

fib[30]

How fast is this recursive computation? Let’s investigate using the Timing function:

Timing[fib[10]]

The runtime is close to zero for (Subscript[F, 10]). Let’s try a larger number:

Timing[fib[34]]

Make a function to extract the runtime from the pair returned by Timing:

myFibTime[n_]:=Timing[fib[n]][[1]]  (* the syntax [[1]] returns the first item in the pair *)

myFibTime[32]

Compute 30 runtimes and make a plot:

fibTimes=myFibTime/@Range[30]

ListPlot[fibTimes]

Let' s think of a more efficient way of computing the Fibonacci numbers!

Write a Module computeFib[n] that returns the nth Fibonacci number:

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

Try it out:

computeFib[4]

computeFib/@Range[10]

computeFib[100]

Your turn: compute the ratio of consecutive Fibonacci numbers. What do you observe?

N[computeFib[4]/computeFib[3]]

N[computeFib[20]/computeFib[19],30]