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

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

Re: generic memoization of pure functions?

Show all headers | View raw

On 07.03.2016 09:21, Paavo Helde wrote:
> On 6.03.2016 22:43, bartekltg wrote:
>> On 06.03.2016 12: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.
>>
>> Something like this:
>>
>> template <typename bignum>
>> class fib
>> {
>> private:
>>      map <uint64_t,bignum> M; //or unordered_map
>>
>> public:
>>      fib()    {
>>          M[0]=0;
>>          M[1]=1;
>>      }
>>      bignum operator () (uint64_t x)   {
>>          auto it = M.find(x);
>>          if (it!=M.end())
>>              return (it)->second;
>>          else    {
>>              // always x >= 2  because M[0] and M[1] created in the
>> constructor.
>>              M[x] = this->operator ()(x-1) + this->operator ()(x-2);
>
>  From the key type uint64_t I infer that this is meant to support
> arguments larger than 2^32. Alas, it creates map lookup entries for all
> integers<=x, meaning that if you calculate fib(2^32) you perform 2^32
> dynamic memory allocations for the map and consume several hundreds of
> GB-s of memory. Not so nice.


The whole idea of computing fibonaci number using 'linear' equation
is not nice;-) This is only an exercise.


> To be useful, the map should probably store only values for selected
> points, like each fib(2^n), fib(2^n+1). Again, depends on the usage
> pattern.

http://mathworld.wolfram.com/FibonacciNumber.html
equations 26 and 60.

But if you use 29 instaad of 26, the whole memorization
is almost useless.



>>              return M[x];
>>          }
>>      }
>> };
>>
>>
>> int main(){
>>      fib<uint64_t> f;
>>      for (int i=0;i<50;i++)
>>      cout<<f(i)<<endl;
>>      return 0;
>> }
>>
>> For a general function, but for Fibonacci sequence is a poor idea.
>>
>> template <typename bignum>
>> class sane_fib
>> {
>> private:
>>      vector <bignum> M;
>> public:
>>      sane_fib()
>>      {
>>          M.push_back(0);
>>          M.push_back(1);
>>      }
>>      bignum operator () (uint64_t x)
>>      {
>>          while (x >= M.size())
>>              M.push_back( M[M.size()-1] + M[M.size()-2] );
>>          return M[x];
>>      }
>> };
>
> This is much better than the first example in terms of memory
> allocations, but still suffering from the memory explosion.

In rare cases you need (almost) all values for n<N.
I'm still not sure if this would be faster than O(log(n))
direct computation compared to random access to the array
(cache).
At least in this version wider index do not expand memory usage.

>
>> BTW My favorite way to compute fib numbers (in O(log(n)
>> multiplications)):
>>
>> Powers of a matrix [1,1;1,0] contains fib numbers.
>>   [1,1;1,0]^k = [Fb_{k+1},Fb_k ; Fb_k, Fb_{k-1} ].
>> Coputing a power of anything thac can be multiplied is easy:
>>
>> template <typename T >
>> T power(T a, uint64_t ex){
>>      T r;
>>      if (ex==0)  {
>>          T r(1);
>>          return r;
>>      }
>>      else  {
>>          if (ex%2==1) return a*power(a,ex-1);
>>          else  {
>>              T t=power(a,ex/2);
>>              return t*t;
>>          }
>>      }
>> }
>>
>> Now we need a symetric matrix. A matrix library is an overkill
>> template <typename bignum>
>> class symetric_matrix
>> {
>> public:
>>      bignum d1,d2,c;
>>      symetric_matrix (bignum d1_,bignum d2_, bignum c_ ):
>> d1(d1_),d2(d2_),c(c_) {};
>>      symetric_matrix (int x): d1(x),d2(x),c(0) {};
>>      symetric_matrix (): d1(1),d2(1),c(0) {};
>>
>>      friend  symetric_matrix operator * (const symetric_matrix& A, const
>> symetric_matrix& B)    {
>>          return symetric_matrix<bignum> {  A.d1*B.d1 + A.c*B.c,A.d2*B.d2
>> + A.c*B.c, A.d1*B.c + A.c*B.d2 };
>>      }
>> };
>
> This seems interesting and most promising.
> This looks fast enough to not
> need any memoization.

I do not see how to add memoization to if even if someone want to.
The 'trajectory' is too sparse for memoization to do anything important.

But it is still far for the best way.
The symatric matrix use 6 multiplication, but this is not a any
general matrix. One can use the relation d1 = d2+c
and get 4 multiplication per level.

If I really want, I can extract the equations (or loot to the wolfram
page) and write it with 3 bignum-bignum multiplications per level:


template <class bignum>
pair<bignum,bignum> fibf_pair ( uint64_t x )
{
     //retrun  fib{ x+1} and fib{x}

     if (x==0)
         return make_pair<bignum,bignum> (1,0);

     bignum F2n1, F2n, Fn, Fn1;

     tie(Fn1,Fn) = fibf_pair<bignum>(x/2);   //n=x/2

     F2n1 = Fn1*Fn1 + Fn*Fn;
     F2n  = Fn* (2* Fn1  - Fn );

     if (x%2==0) // x == 2n;  x+1 == 2n+1
         return make_pair(F2n1,F2n);
     else  // x == 2n+1; x+1 == 2n+2
         return make_pair(F2n1+F2n,F2n1);
}

template <class bignum>
bignum fibf ( uint64_t x )
{
     return fibf_pair<bignum>(x).second;
}

But the matrix version is, paradoxically, easer to write.
Additionally the matrix framework give us a way to
compute F( a + b k ) for many k easily.

I used it for another exercise:
http://zimpha.github.io/2015/09/22/pa-2015-translate/#Fibonacci_(fib)_[A]

Best
Bartek

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