generic memoization of pure functions?

[luser...@gmail.com]

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.

[Paavo Helde]

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.

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++. Only then, IF
the performance is not sufficient AND the profiler shows a bottleneck in
fib() one could try memoizing.

At this step it becomes complicated. The best solution depends very much
on the real usage pattern and other aspects like multithreading support,
so I guess there is no single 'idiomatic' way in C++. The only idiomatic
piece would probably be std::unordered_map for storing the remembered
results.

hth
Paavo

[Alf P. Steinbach]

On 06.03.2016 14:00, Paavo Helde wrote:
> On 6.03.2016 13:09, luser...@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.

> Only then, IF
> the performance is not sufficient AND the profiler shows a bottleneck in
> fib() one could try memoizing.
>
> At this step it becomes complicated. The best solution depends very much
> on the real usage pattern and other aspects like multithreading support,
> so I guess there is no single 'idiomatic' way in C++. The only idiomatic
> piece would probably be std::unordered_map for storing the remembered
> results.

Yes, I agree for the general case of “any function”.


Cheers!,

- Alf

Notes:
[1] Or rather, by whomever it was that did the most of the math for him.
This little thing has been troubling me. I don't know who it was.

[bartekltg]

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

[Juha Nieminen]

luser...@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?

Wouldn't it be easier to just implement it with a loop?

Recursive fibonacci is fancy but inefficient. Just do it iteratively.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Paavo Helde]

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.

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.

> 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.

This seems interesting and most promising. This looks fast enough to not
need any memoization.

[BartC]

On 06/03/2016 23:06, Juha Nieminen wrote:
> luser...@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?
>
> Wouldn't it be easier to just implement it with a loop?
>
> Recursive fibonacci is fancy but inefficient. Just do it iteratively.

I think everyone is missing the point.

Fibonacci is just an *example*. Quite a good example because memoising
would have a dramatic effect on performance.

But it is about memoising a more general function. (I don't know how to
it; I was just curious in seeing the easy C++ solution that was hinted
at in c.l.c.)

(I remember when I was using recursive fibonacci as a benchmark. People
came up with better solutions that reduced the number of calls from tens
of millions to a few dozen. Great, except the purpose of the exercise
was to measure how good an implementation was at executing tens of
millions of function calls! The 'better' methods were rubbish at that as
they all executed in 0 milliseconds...)

--
Bartc

[Alf P. Steinbach]

On 07.03.2016 21:34, BartC wrote:
> On 06/03/2016 23:06, Juha Nieminen wrote:
>> luser...@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?
>>
>> Wouldn't it be easier to just implement it with a loop?
>>
>> Recursive fibonacci is fancy but inefficient. Just do it iteratively.
>
> I think everyone is missing the point.
>
> Fibonacci is just an *example*. Quite a good example because memoising
> would have a dramatic effect on performance.

Yes, memoizing would dramatically reduce performance.

This is good to know about.

Too many people just blindly apply techniques that they learn from what
they regard as authoritative sources, and end up making things
needlessly complex and inefficient.

> But it is about memoising a more general function. (I don't know how to
> it; I was just curious in seeing the easy C++ solution that was hinted
> at in c.l.c.)

Can go like this:


<code>
#include <functional>
#include <unordered_map>
#include <utility>
using namespace std;

class Memoized
{
private:
function<auto(int)->int> f_;
unordered_map<int, int> values_;

Memoized( Memoized const& ) = delete;
auto operator=( Memoized const& ) = delete;

public:
auto operator()( int const x )
-> int
{
const auto it = values_.find( x );
if( it != values_.end() )
{
return it->second;
}
const int result = f_( x );
values_.insert( {x, result} );
return result;
}

explicit Memoized( function<auto(int)->int> f ): f_( move( f ) ) {}
};

auto fib( int const x )
{
static Memoized m( [&]( int x ) -> int
{
fprintf( stderr, "fib(%d) called.\n", x );
return (x == 0? 0 : x == 1? 1 : m( x-1 ) + m( x-2 ));
} );

return m( x );
}

#include <stdio.h>
auto main() -> int
{
for( int x = 0; x < 10; ++x )
{
printf( "%d -> %d\n", x, fib( x ) );
}
}
</code>

> (I remember when I was using recursive fibonacci as a benchmark. People
> came up with better solutions that reduced the number of calls from tens
> of millions to a few dozen. Great, except the purpose of the exercise
> was to measure how good an implementation was at executing tens of
> millions of function calls! The 'better' methods were rubbish at that as
> they all executed in 0 milliseconds...)

For typical small range of arguments fib can be calculated directly.

There no need for “a few dozen” [recursive] calls: it's just one call,
that's it.

Above that argument range, say 64-bit, memoization could help if it
didn't use up zillions times more memory than the computer has.


Cheers & hth.,

- Alf

[bartekltg]

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.

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

[bitrex]

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.