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