Automatic memoization!!

[trss]

Has anyone experienced automatic memoization by any C++ compiler
before?

The program coded as a solution for the problem based on the famous 3n
+1 problem, both of which are given below, is automatically memoized.
Is it due to caching of return values or something else? The point is,
does this program exhibit some property which leads to automatic
memoization by the compiler? Which can be satisfied by other programs
too to make them automatically optimized by the compiler?

Also, though this might be considered compiler specific, i have tried
this on microsoft vc++ compiler as well as bloodshed devc++ compiler.
Even without optimization in both of these compilers, this happens.

Problem ( http://projecteuler.net/index.php?section=problems&id=14
) :-
----------------
Problem 14
05 April 2002

The following iterative sequence is defined for the set of positive
integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following
sequence:
13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1)
contains 10 terms. Although it has not been proved yet (Collatz
Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one
million.

Answer:
837799
----------------

The solutions given below takes the number below which the longest
chain is to be found as input.

Recursive solution ( http://pastecode.org/2035 ) :-
----------------
#include <stdio.h>

unsigned maxn = 0, maxx = 1;

unsigned solve(unsigned x) {
if(x == 1) return 1;
else return x & 1 ? solve(3 * x + 1 >> 1) + 2 : solve(x >> 1) + 1;
}

int main() {
unsigned i, t, n;
scanf("%u", &n);
for(i = 2; i < n; i++)
if(maxn < (t = solve(i))) maxn = t, maxx = i;
printf("%u\n", maxx);
return 0;
}
----------------

There might be a mistake here though. Like i tried incrementing a
global variable (initialized to 0) inside the function to check how
many times control goes inside the function and printed the value in
main after calling the function and it gave the actual number of times
it went in and did not take any extra time and was as fast as it was
without it!

The following code is the non-optimized program since it uses a loop
which essentially does the same thing as the recursion but cannot have
automatic memoization done by the compiler.

Non-recursive solution ( http://pastecode.org/2036 ) :-
----------------
#include <stdio.h>

int main() {
int i, j, l, maxl = 0, maxi = 0, n;
scanf("%d", &n);
for(i = 1; i < n; i++) {
for(l = 1, j = i; j - 1; l++)
j = j & 1 ? 3 * j + 1 : j >> 1;
if(maxl < l) maxl = l, maxi = i;
}
printf("%d\n", maxi);
return 0;
}

 

[trss]

* trss:


C++ compilers don't do memoization for you.

They can in some cases inline recursive calls, to some shallow depth.

By the way, it seems your two programs are not logically equivalent, hence it
seems that at least one is wrong.

Cheers, & hth.,

- Alf

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

could you please give it another quick look and check if they really
arent equivalent in logic? both do the same thing in the same way.
sorry if my code is a bit obfuscated. they are small though.

btw, neither is wrong since both give exactly the same ans. for all
inputs which are the right anss.

thnx

 

[trss]

Please don't quote signatures.

alright

I've looketh and yes they now seem to be equivalent, just an optimization in the
recursive version.

yeah thnx. but the question is, how does that optimization occur for
this particular recursion alone and not for any other even simple
recursions like factorial calculations and stuff? the depth is also
quite large in this case since chains happen to be quite long for many
values within 1,000,000 which is the actual question in that problem
even for which this recursion gets optimized.

my point is, we could use this technique to code in this "style"
instead of implementing our own hash map and stuff to manually code
memoization. though implementing ourselves isn't much of a big task
when we know the input values to be within a small domain where we can
simply use an array of that size as the cache, it may become slower
(and a bit to code too) if we are to use hash maps and stuff as is the
case with this problem in case memoization wasn't achieved
automatically.

 

[Ben Bacarisse]

alright

But you should retain attribution lines (the "so-and-so wrote:" bits).

yeah thnx. but the question is, how does that optimization occur for
this particular recursion alone

Alf Steinbach is probably referring to *your* optimisation. You made
the recursive version do two iterations in one go in the "odd" case.
The two versions are not equivalent, however.

The compiler is not doing any memoization. Are you, perhaps, being
confused by the very long run time of your second (non-recursive)
version? This is caused by the second version not terminating (at
least on my system). Try running it with input 113383 and then with
input 113384.

 

[Dario Saccavino]

The compiler is not doing any memoization.  Are you, perhaps, being
confused by the very long run time of your second (non-recursive)
version?  This is caused by the second version not terminating (at
least on my system).  Try running it with input 113383 and then with
input 113384.

Possibly OT: indeed, it seems that the second algorithm overflows when
i == 113383. Using 32-bit int, the 'j' variable in the inner loop
becomes negative, and the program never terminates.

Dario

 

[trss]

But you should retain attribution lines (the "so-and-so wrote:" bits).
okay!



Alf Steinbach is probably referring to *your* optimisation.  You made
the recursive version do two iterations in one go in the "odd" case.
The two versions are not equivalent, however.

yes but not coz of the minor optimization. i forgot to add it to the
non-recursive solution. it doesnt give that much of a difference in
execution times. thnx for pointing out though.

The compiler is not doing any memoization.  Are you, perhaps, being
confused by the very long run time of your second (non-recursive)
version?  This is caused by the second version not terminating (at
least on my system).  Try running it with input 113383 and then with
input 113384.

oh man. really sorry. thnx for finding that! i just replaced int with
unsigned in the non-recursive solution guessing that should be the
problem causing this and it worked!! faster than the recursion
ofcourse!

so yes there is no automatic memoization by the compiler and hence
something like http://apl.jhu.edu/~paulmac/c++-memoization.html must
only be used (though i haven't tried it out yet).

p.s. - for problem 15 in http://projecteuler.net the problem can be
solved by implementing simple memoization only and it led me to feel
the power of memoization!

thnx ppl
thnx

 

[trss]

Possibly OT: indeed, it seems that the second algorithm overflows when
i == 113383. Using 32-bit int, the 'j' variable in the inner loop
becomes negative, and the program never terminates.

   Dario

right. in fact i checked it with long long unsigned and length of
chains seem different for some inputs though the final answer turns
out to be same as with unsigned.

i actually implemented memoization myself and found running time to
increase in the memoized version which was the actual source of
confusion. implementing memoization for the right code with long long
sure increases performance.

anyway, all confusions apart, the problem is only with overflow and no
automatic memoization is done by usual compilers.

thnx