> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) < 2^n (If you need a hint: use induction), s

> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) < 2^n (If you need a hint: use induction), so it should be less than 10⁹ bits, or 128 megabytes. And that bound isn’t tight. A tighter one is 2log(phi) bits per step. That’s slightly less than 0.7, so that would make it less than 90 megabytes.