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?se...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;

}

----------------

Thank You

trss