Re: Fibonnaci

"Jordan Abel" <jmabel@xxxxxxxxxx> wrote in message
news:slrndpi5k5.2q4r.jmabel@xxxxxxxxxxxxxxxx
> On 2005-12-09, Richard Heathfield <invalid@xxxxxxxxxxxxxxx> wrote:
>> Write it. See how slow it is? Find out why. Hint: use printf.
>>
>> Now think about how you could make it a lot faster. Hint: think about
>> arrays.
>
> All that's needed to change the worst-case performance to linear is a
> two-element cache.

I think Richard tryed to explain the process... how to move from a top down,
recursion-based solution to a memoized recursion, and then to a bottom-up
solution (building that same array that was used for memoization from 0 to
n). This is infact the best you can do if you need to keep all of the first
n Fibonacci numbers - it is unclear if the OP needs this, or he just wants
to write them out. Also, your comment is covered in the last "idea" Richard
gives.


.

Relevant Pages

  • Re: Fibonnaci
    ... MARQUITOS51 said: ... > Im trying to find any code in C developed to calculate the fibonnacci ... Hint: use printf. ... arrays. ...
    (comp.lang.c)
  • Re: Using representation clauses in networking software
    ... Sounds like a lost optimization opportunity with absolutely no overall ... gain. ... Hint: it most likely does not make much difference for individual ... but things get more interesting with arrays - the longer the ...
    (comp.lang.ada)
  • Re: vector-push-extend
    ... (or have a look at adjustable arrays). ... That works of course because size is the same; but your hint to ... It's funny though that SBCL seems ...
    (comp.lang.lisp)
  • Re: Which company is MFR90073? (Manufacturer of TTL chips in 1981)...
    ... 90073 is a CAGE code for CMC, probably a mfr or dist. ... Thanks for this hint. ... transistors driving the hinhibit lines. ... either transistor arrays, ...
    (sci.electronics.components)