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];
Table[Echo@Timing[n->f0[n]], {n,1,40}]

The Naive Way, Corrected

f1[0]=f1[1]=1; f1[n_] := f1[n-1]+f1[n-2];
Timing[f1[40]];

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

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

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

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

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

“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)))

“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?