Project Euler #14 in Java
Cache implementation had bugs

Actually your cache implementation would have helped except that you didn't quite write it correctly.


The t_cache.put() is in the wrong spot.  It should be outside the while loop since you don't know t until the loop finishes.
This function t_cache.containsKey(n) is actually returning false always.  You need to cast n to an int like this: t_cache.containsKey((int) n).  Otherwise since n is a long, it doesn't actually look up the right key.  I believe it is attempting to look up a Long key instead.


With this fixed up code, it runs 3.7x faster than without the cache:

public static int get14() {
    int max = 1;
    int ans = 1;
    Map&lt;Integer, Integer&gt; t_cache = new HashMap&lt;Integer, Integer&gt;();

    t_cache.put(1, 0);
    for (int i = 2; i &lt; 1000000; i++) {
        long n = i;
        int t = 0;
        do {
            ++t;
            if (t_cache.containsKey((int)n)) {
                t += t_cache.get((int) n);
                break;
            }
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n = 3 * n + 1;
            }
        } while (n != 1);
        t_cache.put(i, t);
        // System.out.println(i + "-&gt;" + t);
        if (t &gt; max) {
            max = t;
            ans = i;
        }
    }
    return ans;
}


How to get even faster

Maaartinus already pointed out how to use bit operators to improve your speed.  Using the bit operators in addition to the HashMap cache improves the speed to 4.5x the original (from 3.7x, or a 22% speedup).  But this is still slower than just using the simple loop in maaartinus's answer (5.3x faster than original).

The problem is that the cache implementation can still be improved.


You don't need to call t_cache.containsKey() at all.  Since you are proceeding in order, the check if (n &lt; i) will do the same thing, since you know that at any i, all the results below i have been found and cached.
You only need to check the cache in the "even" case, where n is decreasing.  In the "odd" case, n will increase so there is no chance that the cache will be hit.
You can use an array instead of a HashMap.  You are filling in the cache sequentially, so there is no reason for hashing.


So here is the final version with all of the improvements:

public static int get14() {
    int max = 1;
    int ans = 1;
    int [] t_cache = new int[1000000];

    for (int i = 2; i &lt; 1000000; i++) {
        long n = i;
        int t = 0;
        do {
            ++t;
            if ((n &amp; 1) == 0) {
                n &gt;&gt;= 1;
                if (n &lt; i) {
                    t += t_cache[(int)n];
                    break;
                }
            } else {
                n = 3 * n + 1;
            }
        } while (true);
        t_cache[i] = t;
        if (t &gt; max) {
            max = t;
            ans = i;
        }
    }
    return ans;
}


And here is the speed of each implementation:

Implementation                 Time    Speedup from original
---------------------------    ----    ---------------------
Original (uncached)            3.33           1.0x
HashMap                        0.90           3.7x
HashMap + bit ops              0.74           4.5x
maaartinus (bit ops)           0.63           5.3x
JS1 (Array cache + bit ops)    0.10          33.3x