Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #158085

Re: [OT] was: Recursion v Memoization

Show all headers | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> David Brown <david.brown@hesbynett.no> writes:
>
>> On 31/12/2020 09:46, Tim Rentsch wrote:
>>
>>> Real Troll <real.Troll@trolls.com> 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.)

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Recursion v Memoization Real Troll <real.Troll@trolls.com> - 2020-12-29 16:30 -0500
  Re: Recursion v Memoization Bart <bc@freeuk.com> - 2020-12-29 22:17 +0000
    Re: Recursion v Memoization Ike Naar <ike@sdf.org> - 2020-12-30 05:47 +0000
      Re: Recursion v Memoization Bart <bc@freeuk.com> - 2020-12-30 11:55 +0000
  Re: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-29 21:51 -0800
  Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-31 00:46 -0800
    Re: Recursion v Memoization David Brown <david.brown@hesbynett.no> - 2020-12-31 16:12 +0100
      [OT] was: Recursion v Memoization Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-01-01 15:59 +0000
        Re: [OT] was: Recursion v Memoization David Brown <david.brown@hesbynett.no> - 2021-01-01 17:35 +0100
        Re: [OT] was: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-01 08:40 -0800
        Re: [OT] was: Recursion v Memoization Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-01-02 10:36 -0800
          Re: [OT] was: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-01-02 16:59 -0800
          Re: [OT] was: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-01-02 17:00 -0800
    Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-02 18:56 -0700
      Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-04 19:56 -0800
        Re: Recursion v Memoization beej@beej.us (Beej) - 2021-01-05 04:27 +0000
          Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-07 04:54 -0800
            Re: Recursion v Memoization beej@beej.us (Beej) - 2021-01-11 05:43 +0000
              Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-11 06:34 -0800
        Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-05 14:35 -0700
          Re: Recursion v Memoization Real Troll <real.troll@trolls.com> - 2021-01-05 16:45 -0500
            Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-05 15:33 -0700
          Re: Recursion v Memoization Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-01-06 09:40 +0000
            Re: Recursion v Memoization Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-01-06 17:09 +0000
          Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-07 06:37 -0800
  Re: Recursion v Memoization Andrey Tarasevich <andreytarasevich@hotmail.com> - 2020-12-31 02:33 -0800

csiph-web