3n+1 Problem, aka Collatz Problem

This note and subsequent ones serve as a reading log of "programming challenges", a book concerning algorithms and their implementations. Since compiler frontend doesn't involve any advanced or sophisticated problem solving techniques, I haven't gotten a chance from my work to see how algorithms make short work of tough problems. It is time for me to brush up on algorithms.

The 3n + 1 problem is well defined at the link below.
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36
It is also known as Collatz problem because it's a conjecture in mathematics first proposed by Lothar Collatz.

Following is 4 solutions I have tried on this problem.

1. Brutal force
The most obvious solutions, yet the most inefficient one, is to write a function that calculate cycles for a given number. The function is then called in a loop on the loopvar iterating from i through j. A variable max_cycle is updated when its value is smaller than the cycles of current loopvar.

The pseudo code is as follows
for (loopvar = i; loopvar <= j, loopvar ++) {
    current_cycle = getCycle(i);
    if (current_cycle > max_cycle)
         max_cycle = current_cycle;
}

It is fairly slow especially when running on large numbers as input.
For example, the run time became unbearably long when input is i = 1 and j = 1000000.
  
2. Caching
It is stated in the problem description that n will be less than 1,000,000. If an array is used to cache results, the total memory usage is approximately 4MB. The beauty of caching is that every number only has its cycles calculated once. The next time the same number is needed for cycle calculation, a cached result can be obtained from the array saving CPU a lot of arithmetic instructions.

The pseudo code is like
for (loopvar = i; loopvar<=j, loopvar ++) {
    if (cache[loopvar] != 0) {
        current_cycle = cache[loopvar];    
    } else {
        current_cycle = getCycle(i);
        cache[loopvar] = current_cycle;
    }
    if (current_cycle > max_cycle)
         max_cycle = current_cycle;
}

3. Recursion and Caching of getCycle.
getCycle can be implemented in recursion, which further facilitate caching and reduction of calculations.
long getCycle(long n) {
    long cycle = 0;
    
    if ((n < CACHESIZE) && cacheCycle[n] != 0) {
        return cacheCycle[n];
    }
    if (n == 1) {
        cycle = 1;
    }
    else if (n & 1) {
        cycle = 1 + getCycle(n * 3 + 1);
    } else {
        cycle = 1 + getCycle(n / 2);
    }
    if (n < CACHESIZE) {
        cacheCycle[n] = cycle;
    }
    return cycle;
}

4. Precalculation
Instead of calculating and caching, we could write a program to precalculate cycles of numbers from 1 through 1,000,000 and to save results into an array. So getCycle would be as simple as accessing a array element by its subscript.

5. Performance numbers
The website (http://uva.onlinejudge.org) also serves as an online judge, whereby you can submit your code and validate your program.
Below is the states and performance numbers of solutions 1,2 and 3. Solution 4 was not submitted because the precauculated array exceeded the uploading size limit.

9194202     100     The 3n + 1 problem     Accepted     C++     0.664     2011-08-27 05:09:38
9194241     100     The 3n + 1 problem     Accepted     C++     0.052     2011-08-27 05:25:28
9194350     100     The 3n + 1 problem     Accepted     C++     0.028     2011-08-27 06:14:37

The best one I have so far is still far behind the optimum solution. Statistics of uva website shows there are 1206 submissions that have run time less than 0.028 seonds.
Problem Ranking Submission Date Run time
100 1207 9194350 2011-08-27 06:14:37 0.028