Pensieve header: Sep 22: Too many ways to compute Fibonacci.

ImageRestyle[,]

Too many ways to compute Fibonacci

The Naive Way

f0[0]=f0[1]=1; f0[n_] := f0[n-1]+f0[n-2];

f0[10]

?Timing

Timing[Log[Log[10000000!]]//N]

Table[i^2, {i,0,9}]

Table[i^2, {i,3,9,2}]

?Table

Table[i j, {i,10},{j,10}]

Table[i j, {i,10},{j,10}] // MatrixForm

?Echo

Echo[1+1]

Echo[1+1]*7

Table[Echo@Timing[n->f0[n]], {n,1,40}]

The Naive Way, Corrected

sq[x_] := x^2

sq[7]

sq[7]=50

?sq

Table[sq[i], {i,10}]

sq[x_] := (sq[x]=x^2)

?sq

Table[sq[x], {x,10}]

?sq

f1[0]=f1[1]=1; f1[n_] := (f1[n] = f1[n-1]+f1[n-2]);

f1[10]

?f1

Timing[f1[40]]

Timing[f1[100]]

f1[5]

f1[5]=10

f1[5]

Table[f1[k], {k,0,10}]

f1[5]=.

f1[5]

“prev”, “cur”, and “While”.

prev=8; cur=13

{prev=cur, cur=prev+cur}

{prev=8, cur=13}

{cur=prev+cur, prev=cur}

{prev=8, cur=13}

{prev, cur} = {cur, prev+cur}

{a=77, b=55}

a=b-a; b=b-a; a=a+b; {a,b}

?While

100!

k=1; p=1;
While[k≤100, p=p*k; k=k+1];
p

Range[100]

Times@@Range[100]

k=1; p=1;
While[k≤100, p*=k; k+=1];
p

k=1; p=1;
While[k≤100, p*=k;++k];
p

k=prev=cur=1;
While[k<100, {prev, cur} = {cur, prev+cur}; ++k];
cur

f2[n_] = (
k=prev=cur=1;
While[k<n, {prev, cur} = {cur, prev+cur}; ++k];
cur
)

? ;

?=

Clear[f2]

f2[n_] = (
{k,prev,cur}={1,1,1};
While[k<n, {prev, cur} = {cur, prev+cur}; ++k];
cur
)

f2[10]

Clear[f2]

f2[n_] := (
{k,prev,cur}={1,1,1};
While[k<n, {prev, cur} = {cur, prev+cur}; ++k];
cur
)

f2[100]

prev

?Module

f3[n_] := Module[{k,prev,cur},
{k,prev,cur}={1,1,1};
While[k<n, {prev, cur} = {cur, prev+cur}; ++k];
cur
]

f3[40]

cur

Aside on @, @@, @@@

Times@Range[5]

Times@@Range[5]

Times[2,3,5]

Times[2,3]

Times[2]

Times[]

Plus[]

h@@@f[g[1],g[2]]

“prev”, “cur”, and “For”.

?For

For[k=cur=prev=1, k<100, ++k, {prev, cur} = {cur, prev+cur}]; cur

3==7

7==7

“prev”, “cur”, and “Do”.

?Do

{prev, cur}={1,1};
Do[{prev, cur} = {cur, prev+cur},99];
cur

A “While” loop for {(Subscript[f, 1]), (Subscript[f, 2]), ...} (using negative indices)

Length[{1,2,4}]

?Append

fs=Append[f[1,2,3], "tristan"]

fs[[4]]

fs[[2]]

fs[[-1]]

fs[[0]]

First[fs]

Last[fs]

Head[fs]

fs={1,1};
f6[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, Append[fs, fs[[-1]]+fs[[-2]]]];
Last[fs]
]

f6[100]

fs={1,1}

While[Length[fs]≤5, fs=Append[fs, fs[[-1]]+fs[[-2]]]]

fs

fs={1,1};
f6[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, fs=Append[fs, fs[[-1]]+fs[[-2]]]];
Last[fs]
]

f6[100]

fs={1,1};
f7[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, fs=Append[fs, fs[[-1]]+fs[[-2]]]];
fs
]

f7[20]

fs={1,1};
f8[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, AppendTo[fs, fs[[-1]]+fs[[-2]]]];
fs
]

f8[10]

A “While” loop for {(Subscript[f, 1]), (Subscript[f, 2]), ...} (using “Total” and “Most”)

fs={1,1};
f9[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, AppendTo[fs,1+Total@Drop[fs,-1]]];
fs
]

f9[10]

fs={1,1};
f10[n_] := Module[{fs={1,1}},
While[Length[fs]≤n, AppendTo[fs,1+Total@Most@fs]];
fs
]

f10[10]

Total[Range[100]]

Plus@@Range[100]

“ReplaceRepeated” on (({{n}, {(Subscript[f, n-1])}, {(Subscript[f, n])}})).

“NestWhile” on (({{n}, {(Subscript[f, n-1])}, {(Subscript[f, n])}})).

“Nest” on (({{(Subscript[f, n-1])}, {(Subscript[f, n])}})).

A Sum of Binomial Coefficients

Solve for an “explicit” formula, then use it.

“Series” and (1/(1-x-(x^2)))

Series[(1/(1-x-(x^2))),{x,0,10}]

“SeriesCoefficient” and (1/(1-x-(x^2)))

Using “MatrixPower”

Using (Subscript[f, 2n])=(Subscript[f, n]^2)+(Subscript[f, n-1]^2) and (Subscript[f, 2n+1])=(Subscript[f, n])((Subscript[f, n+1])+(Subscript[f, n-1]))

A “categorified” version (using lists)

A “categorified” version (using strings)

Other Items

Continue looking at Charlene’s project? A look at Etienne’s project?