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

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.

CodePudding user response：

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.

CodePudding user response：

One way to make it branchless (except for the loop condition) is to multiply n / 2 with the n % 2 == 0 result (1 for true) and multiply (n * 3 1) with the negated result of (n % 2 == 0) and add them together.

void collatz(unsigned long long n) {
    std::cout << n << '\n';
    while (n > 1) {
        auto m = n % 2 == 0;
        n = m * (n / 2)   !m * (n * 3   1);
        std::cout << n << '\n';
    }
}

Demo