Calculating numbers in the Collatz sequence

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 generateCollatz1(int n) {
    ArrayList 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 generateCollatz2(int n) {
    ArrayList 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}$$

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;

StackExchange Code Review Q#105776, answer score: 7