The boxes below may be used to compute values from the Fibonacci Sequence. Because the computation uses a naïve, recursive version of Fib, it would traditionally incur exponential runtime and appear to run forever sometime around term 40. This page, however, rebinds the naïve function to an automatically memoized version that provides linear runtime for uncomputed terms, and amortized constant runtime for previously-computed terms (and any terms that are lower than the highest computed term). It should compute large terms nearly instantly, up to about term 1476 (after which most Javascript engines will begin to simply return a result of "infinity"). The small cost for this massive performance increase is space consumption linearly proportional to the highest computed term.
| Fib Term: | |
| Fib Result: |
The unmemoized Fibonacci source code used for this page can be found in the file "./js/fib.js". The automatic memoization code used for this page can be found in the file "./js/automatic_memoization.js". The actual call which rebinds the Fibonacci function into an automatically memoized one can be seen directly in the HTML for this page.
Back to main page.