Project Euler #14 in Java

/*
 * 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.
 */
public static int get14() {
    int max = 1;
    int ans = 1;
    // Map t_cache = new HashMap();
    for (int i = 2; i " + t);
        if (t > max) {
            max = t;
            ans = i;
        }
    }
    return ans;
}

Using no cache I get:


Answer is 837799, Time taken 22.08799153 seconds

Using cache I get:


Answer is 837799, Time taken 90.002679307 seconds {really?}

I need improvements for this.

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 t_cache = new HashMap();

    t_cache.put(1, 0);
    for (int i = 2; i " + t);
        if (t > 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

-
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 >= 1;
                if (n  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
`

StackExchange Code Review Q#91843, answer score: 8