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

Groups > comp.lang.c++ > #41485

Re: generic memoization of pure functions?

Show all headers | View raw

On 03/06/2016 09:25 AM, Alf P. Steinbach wrote:
> On 06.03.2016 14:00, Paavo Helde wrote:
>> On 6.03.2016 13:09, luser.droog@gmail.com wrote:
>>> I asked about this in comp.lang.c and the most useful response so
>>> far was "use C++". So what would be the most idiomatic C++ way to
>>> interface a naïve Fibonacci function with a memoization mapping?
>>>
>>> int fib(int n){
>>>     return n>1? fib(n-1) + fib(n-2): 0;
>>> }
>>>
>>> Assume `int` is a stand-in for some appropriate bignum type.
>>>
>>
>>
>> If the argument is a compile-time constant:
>>
>> constexpr int fib(int n) {
>>      return n>1 ? fib(n-1) + fib(n-2) : 0;
>> }
>>
>> The computation would be done at compile time, so there would be no need
>> to memoize anything.
>
> This brings up the question of implementation limits, formal and
> in-practice?
>
>
>> If the argument is not known at compile time and the speed is important,
>> then the first step would be to use an iterative algorithm instead of
>> recursive, as recursion tends to be pretty slow in C++.
>
> I agree with the conclusion but the argument “pretty slow in C++” is
> irrelevant, whether that premise is true or not, which is a different
> discussion. The improvement has nothing to do with the speed of
> recursion in C++, and all to do with the big-O behavior. The exact form
> is not very apparent; it was analyzed by [1]Donald Knuth in volume 1 of
> “The Art of Computer Programming”. But if you consider
>
>      return (n == 0? 0 : foo(n-1) + foo(n-1))
>
> as a rough approximation, then you see that O(f(n)) ~= 2*O(f(n-1)),
> which gives O(f) ~= 2^n, which is rather ungood. Compared to O(n) for
> iterative, or (but lacking the precision implied by bignum ints) O(1)
> for using the golden ratio formula to compute the numbers directly.

The recursive Fibonacci algorithm's big O behavior is essentially due to 
its shameless breaking of the first rule of algorithm design: never do 
the same work twice.

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

Thread

generic memoization of pure functions? luser.droog@gmail.com - 2016-03-06 03:09 -0800
  Re: generic memoization of pure functions? Paavo Helde <myfirstname@osa.pri.ee> - 2016-03-06 15:00 +0200
    Re: generic memoization of pure functions? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-03-06 15:25 +0100
      Re: generic memoization of pure functions? bitrex <bitrex@de.lete.earthlink.net> - 2016-03-11 11:49 -0500
  Re: generic memoization of pure functions? bartekltg <bartekltg@gmail.com> - 2016-03-06 21:43 +0100
    Re: generic memoization of pure functions? Paavo Helde <myfirstname@osa.pri.ee> - 2016-03-07 10:21 +0200
      Re: generic memoization of pure functions? bartekltg <bartekltg@gmail.com> - 2016-03-08 12:00 +0100
  Re: generic memoization of pure functions? Juha Nieminen <nospam@thanks.invalid> - 2016-03-06 23:06 +0000
    Re: generic memoization of pure functions? BartC <bc@freeuk.com> - 2016-03-07 20:34 +0000
      Re: generic memoization of pure functions? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-03-07 22:27 +0100

csiph-web