[Haskell-cafe] Question about memory usage

[Richard O'Keefe]

On Aug 17, 2010, at 6:39 PM, Roel van Dijk wrote:
>> Using x**n = exp(n*log(x)) and floating point arithmetic,
>> the whole thing can be done in O(1) time, and the price of
>> some inaccuracy.
> It will calculate a subset of the Fibonacci numbers in O(1) time.
> Thinking about it I think you can easily calculate subsets of any
> function in O(1) time, as long as the function is guaranteed to
> terminate. Simply precompute the answers and store them in an array.

It is what, 30 years, since someone pointed out that the simplest
way to implement the full range of factorial() that can be handled
by a machine integer is using a tiny tiny array.

F(n) is approximately phi^n/sqrt(5)
So log2 F(n) is approximately 0.7*n - 1.2
The largest 64-bit IEEE-format number is about 2^1023,
the largest 128-bit one about 2^216383.
So the largest F(n) we can approximate with floats is
	n =  1,476 or thereabouts for 64-bit
	n = 23,608 or thereabouts for 128-bit
That's more Fibonnaci numbers than I personally have any need for
right now, but you're right, it's not all of them, and even the
larger number is a quantity we *could* precompute and store,
and the precomputation would of course be O(1) per stored item.