c++collatz

Is there a way to optimise the Collatz conjecture into a branchless algorithm?

I'm trying to create an algorithm that will compute the collatz conjecture, this is the code so far:

while (n > 1) {
   n % 2 == 0 ? n /= 2 : n = n * 3 + 1;
}

I was wondering if there was a way to optimize this any further since efficiency and speed is crucial for this, and I've heard about branchless programming but I'm not sure how to implement it, or if it's worth it to begin with.

Solution

  • Sure. You need the loop, of course, but the work inside can be done like this:

    n /= (n&-n);  // remove all trailing 0s
while(n > 1) {
    n = 3*n+1;
    n /= (n&-n);  // remove all trailing 0s
}

    It also helps that this technique does all the divisions by 2 at once, instead of requiring a separate iteration for each of them.