Computing Fibonacci Numbers

Memoization, the Easy Way

The easiest solution to this problem is called memoization: we create a lookup table that avoids redoing Fibonacci numbers we've already computed.

Python has a built-in solution for this, conveniently enough, so it takes just two lines of code to upgrade our program.

Now we can compute $F(1000)$ faster than we computed $F(30)$ earlier!¹

If you're more used to other programming languages, you might wonder why there aren't any issues storing a number as big as $F(1000)$ . Python integers are actually arbitrary-size by default, so there's no worries about running out of space.↩

Code

Output

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Memoization, the Easy Way

The easiest solution to this problem is called memoization: we create a lookup table that avoids redoing Fibonacci numbers we've already computed.

Python has a built-in solution for this, conveniently enough, so it takes just two lines of code to upgrade our program.

Now we can compute $F(1000)$ faster than we computed $F(30)$ earlier!¹

If you're more used to other programming languages, you might wonder why there aren't any issues storing a number as big as $F(1000)$ . Python integers are actually arbitrary-size by default, so there's no worries about running out of space.↩

Code

Output

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875