Calculating numbers in the Collatz sequence

Question

I have found two ways in which I can generate the Collatz sequence given a start number. I have looked briefly into their performance, but I'd like a more in depth/solid review into the difference in the two methods.

The main difference really is, one of them doesn't have if statements. But the down side to this method is there's a fair bit of math involved, which is where I'm concerned with performance.

The main questions I have are:

• Do computers get slower when they have to make (slightly) complex calculations?
• Do if statements actually have a significant affect on performance?
• If we were generating the numbers in the Collatz sequence for large numbers (for example numbers > 1,000,000,000), would the performance difference actually be noticeable?

Here are the two methods I have created:

private static ArrayList<Integer> generateCollatz1(int n) {
    ArrayList<Integer> results = new ArrayList<>();
    while(n != 1) { 
        if(n % 2 == 0) {
            n = n / 2;
            results.add(n);
        }else {
            n = ((n * 3) + 1);
            results.add(n);
        }
    }
    return results;
}

private static ArrayList<Integer> generateCollatz2(int n) {
    ArrayList<Integer> results = new ArrayList<>();
    while(n != 1) {
        n = (int) ( (7 * n + 2) - (Math.pow(-1, n)) * (5 * n + 2) ) / 4;
        results.add(n);
    }
    return results;
}

The math in the second method (generateCollatz2) is using the following formula:

$$ f(n) = \frac{7n + 2 - (-1)^n (5n + 2)}{4}$$

Answer 1

Test it

You are asking which one is faster, but did you actually test it yourself? I'm sure if you did you would find out.

Math.pow()

In your second solution, just using Math.pow() is slower than the entire first solution, probably by an order of magnitude. I'm not sure why you think using a single if statement would be slower than calling an extremely complicated function (which probably contains lots of if statements).

Avoiding Math.pow

You can compute \$(-1)^n\$ by using the 1 bit, like this: -(2*(n & 1)-1). So you can change your second solution to:

n = ( (7 * n + 2) + (2*(n & 1)-1) * (5 * n + 2) ) / 4;

This version would be very similar in runtime to the first solution. I couldn't tell you which would be faster. I'm also not sure if the division by 4 here will be optimized away. You may want to convert that into a shift by 2 instead:

n = ( (7 * n + 2) + (2*(n & 1)-1) * (5 * n + 2) ) >> 2;

Answer 2

Let's just think about how your formula works:

$$f(n) = \begin{cases} \frac{7n + 2 - (5n + 2)}{4} = \dfrac{n}{2} &\text{if}\ n\ \text{is even}\\ \frac{7n + 2 + (5n + 2)}{4} = 3n+1 &\text{if}\ n\ \text{is odd} \end{cases} $$

( (7 * n + 2) - (Math.pow(-1, n)) * (5 * n + 2) ) / 4 is eight elementary arithmetic operations, if you consider Math.pow(-1, n) to be an elementary operation — which it isn't. In OpenJDK, it ends up calling native code, and it's very numerically intensive. Not only that, but you also incur a performance penalty for a native call and for venturing into floating point arithmetic. -2 * (n & 1) + 1 should be a simpler (though less readable) substitute for Math.pow(-1, n).

Still, you would be looking at ten integer arithmetic operations for ((7 * n + 2) + (2 * (n & 1) + 1) * (5 * n + 2)) / 4. Why so many? Basically, the way the formula works is by computing both branches of the function and merging them based on the least-significant bit of n.

There are situations, such as cryptography and password verification, where branch-free code is necessary to avoid leaking timing information. Calculating the Collatz sequence is not one of those situations. Why not write the code the straightforward way, and let the CPU branch predictor do its job? Also note that generateCollatz2 isn't even branch-free — it's just that the conditionals are hidden inside the implementation of Math.pow().

---

Note that the Collatz sequence can reach some very large numbers for relatively small n. As noted in the tag wiki, n = 159487 will produce a sequence that overflows an int. Therefore, you should consider using ArrayList<Long> as the return type.

---

As for generateCollatz1(), results.add(n) can be factored out, and some redundant parentheses can be eliminated. I also suggest using a conditional operator rather than if-else.

private static ArrayList<Integer> generateCollatz1(int n) {
    ArrayList<Integer> results = new ArrayList<>();
    while (n != 1) { 
        n = (n % 2 == 0) ? n / 2
                         : 3 * n + 1;
        results.add(n);
    }
    return results;
}