Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: [OT] was: Recursion v Memoization Date: Fri, 01 Jan 2021 08:40:07 -0800 Organization: A noiseless patient Spider Lines: 49 Message-ID: <8635zktxug.fsf@linuxsc.com> References: <861rf6uzw4.fsf@linuxsc.com> <87lfdc7ind.fsf_-_@bsb.me.uk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="b44b5f4d6daf76ab4210a530b39b09ae"; logging-data="17941"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19bsXvfK3QbCO9uvi56dHpTXnuCjFHr5TY=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:ylGLfWqXiw5aGop+qbUN0VSnJuI= sha1:26MQScQ6dwG9lB8AogpzjtFwMQ8= Xref: csiph.com comp.lang.c:158085 Ben Bacarisse writes: > David Brown writes: > >> On 31/12/2020 09:46, Tim Rentsch wrote: >> >>> Real Troll writes: >>> >>>> We sometimes resort to using simple methods such as Recursion >>>> functions or interactive functions but Memoization method can be >>>> very useful. For example to generate 45 Fibonacci numbers using >>>> recursion I used this function: >>>> >>>> int fibonacci(int input) >>>> { >>>> if (input == 0 || input == 1) >>>> { >>>> return input; >>>> } >>>> else >>>> { >>>> return fibonacci(input - 1) + fibonacci(input - 2); >>>> } >>>> } >>>> >>>> but using an array to store the numbers and to reuse the previous >>>> calculated values can save a lot of time. [...] >>> >>> Better simply to use a non-exponential algorithm: >> >> "Better" depends on what you are trying to do. For demonstrating the >> benefits of memoization on recursive functions, the OP's algorithm is >> better than yours. For actually calculating Fibonacci numbers >> efficiently, a simple "powers of phi" algorithm is better than yours. > > Is it? [...] No, it isn't. As usual David Brown is talking about things that he understands less well than he thinks he does, and without bothering to investigate his assertions. The algorithm that he removed, using ff2(), produces more accurate results and also runs more quickly than a powers of phi algorithm. I've run the benchmarks. (Disclosure: the algorithm shown in my recent posting marches through more high order bits than it needs to in calling the ff2() function. The version measured does a better job of choosing bit value to start the iteration, but the ff2() function is exactly the same. In any case the measurement includes both the call to ff2() and the high bit setup before ff2() is called.)