Project Euler #14 in Java

Question

/*
 * 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<Integer, Integer> t_cache = new HashMap<Integer, Integer>();
 for (int i = 2; i < 1000000; i++) {
 long n = i;
 int t = 0;
 do {
 // if (t_cache.containsKey(n)) {
 // t += t_cache.get(n);
 // break;
 // }
 ++t;
 if (n % 2 == 0) {
 n /= 2;
 } else {
 n = 3 * n + 1;
 }
 // t_cache.put(i, t);
 } while (n != 1);
 // System.out.println(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.

Answer 1

Cache implementation had bugs

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

1. 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.

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

1. You don't need to call t_cache.containsKey() at all. Since you are proceeding in order, the check if (n < i) will do the same thing, since you know that at any i, all the results below i have been found and cached.

2. 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.

3. 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 < 1000000; i++) {
 long n = i;
 int t = 0;
 do {
 ++t;
 if ((n & 1) == 0) {
 n >>= 1;
 if (n < i) {
 t += t_cache[(int)n];
 break;
 }
 } else {
 n = 3 * n + 1;
 }
 } while (true);
 t_cache[i] = t;
 if (t > 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

• maaartinus: Well spotted the cache problem! You need something like (n <= Integer.MAX_VALUE && t_cache.containsKey((int)n)) in order not to look up nonsense. Otherwise you can get wrong results and possibly also wrong timing results.
• RE60K: thanks. Finally under half a second! I will need to read it maybe quite a few times.

Answer 2

Using no cache I get: Answer is 837799, Time taken 22.08799153 seconds

That's strange. My pretty similar solution takes 0.42 seconds.

Using Cache I get: Answer is 837799, Time taken 90.002679307 seconds {really?}

Yes, really. The number of steps needed is usually rather small and the cache has quite some overhead and what's worse: You pay this overhead for every miss too.

This is my loop:

 while (n > 1) {
 ++result;
 n = (n & 1) == 1 ? 3 * n + 1 : n >> 1;
 }

I guess, what makes the difference is the use of fast bitwise operations instead of modulus and division. Though java optimizes it, the results aren't perfect.

There are quite a few other optimizations possible.

Bit operations

• & is bitwise "and".
• n & 1 extracts the least significant bit (=binary digit). Just like the least significant decimal digit tells us about divisibility by 10, this tells us about divisibility by 2.
• >> is signed right shift. Just like shifting a decimal representation by one digit to the right means division by 10, shifting by one bit means division by 2. With negative numbers it gets a bit complicated, but we don't care here.

A very simple optimization

After every 3 * n + 1 step, there will be a division step. Doing both in one saves us one test:

 while (n > 1) {
 if ((n & 1) == 1) {
 ++result;
 n = 3 * n + 1;
 } 
 ++result;
 n >>= 1;
 }

The best (= best for big numbers) optimization allows to do many steps at once (speedup factor 10), see Wikipedia. It's rather complicated and given that JS1's algorithm needs just 0.1 s, it's not worth it.

• RE60K: yes thanks. bitwise shift decreas time by 8 seconds and ternary operation by 10 seconds. now at around 3.2 still trying to bring it under 0.5 seconds

Answer 3

In addition to what both of the other great answers said, I'd add that you should make it a habit to use better names for your functions and variables, for example:

• get14 : how about findLongestCollatzStart

  • on a related note, I suggest making the function take 1000000 as a parameter instead of hard coding inside the implementation

• t -> chainLenght

• max -> maxChainLength
• ans -> longestStart
• t_cache -> cache

The implementation will be a lot more readable.