On Mon, Aug 6, 2012 at 8:37 PM, Russel Winder <[email protected]> wrote: > On Mon, 2012-08-06 at 17:21 +0200, Philippe Sigaud wrote: > […] >> Well, you're using the worst possible algorithm to calculate Fibonacci >> (exponential time), so it's no wonder it's taking foverer :) > > Memoization is a bit of a help it destroying that problem.
Memoization at compile-time is a bit tricky, though. Which reminds me... What if someone wants Fibonacci values depending on a runtime value, but would like them to be calculated really fast? Use the "Sabalausky Trick" (aka Nick's Run-Time to Compile-Time Time Machine): Pregenerate desired values at compile-time (for example here in an array), to get O(1) fibonacci access at runtime.
