Re: FIbonacci

On 2005-12-11, Peteris Krumins <peteris.krumins@xxxxxxxxx> wrote:
> Eric Sosman wrote:
>> Peteris Krumins wrote:
>>
>>
>> Somebody always proposes this solution, but it's a
>> poor one. Try it with fib(47), say, and tell us how
>> long it takes. Hint: You won't need a high-precision
>> timer.
>>
>
> Yes, the solution has exponential complexity.

But only needs the last two results [or even the last one even and the
last one odd n] cached to reduce it to the same as the iterative
version.
.

Relevant Pages

  • Re: FIbonacci
    ... Eric Sosman wrote: ... > Peteris Krumins wrote: ... > poor one. ... Prev by Date: ...
    (comp.lang.c)
  • Re: FIbonacci
    ... > Eric Sosman wrote: ... >> Peteris Krumins wrote: ... >> poor one. ... Prev by Date: ...
    (comp.lang.c)
  • Re: FIbonacci
    ... > Peteris Krumins wrote: ... prev2 is Fand prev is F. ... using continuation-passing style and tail recursion, ...
    (comp.lang.c)
  • Run-scoring and -allowing by month...
    ... Everywhere else, I've been rounding, but it seemed odd to do ... AVG OBP SLG OPS ... The rest have been poor ...
    (alt.sports.baseball.bos-redsox)
  • Re: C4 "How The West Was Won" format
    ... > across the line is poor and is so so obvious on the screen - very odd for ... Unless they have lost the original, a modern digital print should be ... The rolling stones concert down the road caused a brown out ...
    (uk.media.tv.misc)