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

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

Re: generic memoization of pure functions?

Show all headers | View raw

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);
             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];
     }
};

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 };
     }
};



int main()
{
     sane_fib<uint64_t> fs;
     fib<uint64_t> f;
     symetric_matrix<uint64_t> A(1,0,1) ;

     for (int i=0;i<50;i++)
         cout<<f(i)<<" "<<fs(i)<< " "<<  power(A,i).c <<endl;

     return 0;
}

bartekltg

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