[Haskell-cafe] Question about memory usage

[Roel van Dijk]

On Tue, Aug 17, 2010 at 3:53 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
> On Aug 17, 2010, at 12:37 AM, Roel van Dijk wrote:
>>
>> phi = (1 + sqrt 5) / 2
>> fib n = ((phi ** n) - (1 - phi) ** n) / sqrt 5
>>
>> The use of (**) should make the complexity at least O(n). Please
>> correct me if I'm wrong (or sloppy).
>
> Using the classic
>        x**0 = 1
>        x**1 = x
>        x**(2k+0) = (x**2)**k           k > 0
>        x**(2k+1) = (x**2)**k + x       k > 1
> powers of smallish numbers or matrices can be computed in logarithmic
> time.
That is an interesting trick. So there exists an algorithm that
calculates Fibonacci numbers in O(log n) time.

> 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.