Collatz Conjecture and lookahead for chess

[dangi12012]

So this is an interesting problem - and a fast c++ solution has some goodies for chessprogramming:
Problem: Sum all collatz steps from 0 to 10000000
https://en.wikipedia.org/wiki/Collatz_conjecture

First solution: Naive loop

Code: Select all

uint64_t steps(uint64_t n) {
    uint64_t steps = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
            steps++;
        }
        else {
            n = (3 * n + 1) / 2;
            steps += 2;
        }
    }
    return steps;
}

But we can do better and get rid of all the branches and all the arithmetic and go back to binary math: (As an abstract machine that computes in base two in wiki)

Code: Select all

uint64_t steps(uint64_t n) {
    uint64_t N = n;

    //Make input odd
    uint64_t steps = std::countr_zero(n);
    if (steps != 0) n >>= steps;

    while (n != 1) {
        //Repeated expand until even
        while (n & 1) {
            n = (3 * n + 1) / 2;
            steps += 2;
        }

        //Repeated division by 2 until odd
        steps += std::countr_zero(n);
        n >>= std::countr_zero(n);
    }
    
    return steps;
}

But now we notice that we still have an inner loop with arithmetic. You can notice that the while (n&1) loop is touched as often as there are 1 bits at the end. So we know how often to recursively apply (3n+1)/2 to n.
This can be solved via recursive expansion:

n0 = (3n+1)/2
n1 = (3*(3n+1)/2+1)/2 = (9 n + 5) / 4
n2 = (3*(9 n + 5) / 4 + 1) / 2 = (27n + 19) / 8
n3 = (3 * (27n + 19) / 8 + 1) /2 = (81n + 65) / 16
n4 = (3 * (81n + 65) / 16 + 1) / 2 = (243 n + 211) / 32

When looking at the numbers here we get the general collatz pattern:
http://oeis.org/A001047

n = ((3^i)*n + (3^i - 2^i)) / 2^i
in c++ world 3^i cannot be calculated quickly. But since its a normal f(x) => y function we can do a simple lookup table for 3^i and 3^i - 2^i:

Code: Select all

n = (table_pow3[expand] * n + table_pow3minuspow2[expand]) >> expand;

Which yields branchless solution which skips any and all repeated steps on all odd and all even numbers:

Code: Select all

uint64_t steps(uint64_t n) {
    uint64_t steps;

    //Make input odd
    n >>= steps = std::countr_zero(n);

    while (n != 1) {
        //Repeated expand(e) 3x+1 until even
        uint64_t e = std::countr_one(n);
        steps += e * 2;

        //General form:
        //((3 ^ i) * n + (3 ^ i - 2 ^ i)) / 2 ^ i
        n = (table_pow3[e] * n + table_pow3minuspow2[e]) >> e;

        //Repeated division by 2(c) until odd
        uint64_t c = std::countr_zero(n);
        steps += c;
        n >>= c;
    }
    
    return steps;
}

If now someone finds a general formula to know how which power of 2 we end up with (its garuanteed to be divisible by 2) for this formula:
((3 ^ i) * n + (3 ^ i - 2 ^ i)) / 2 ^ i
The whole collatz problem could be compacted into a single formula.

This is not a solution to the problem if there are loops inside the collatz series or all numbers return to 1.
But it would be a piece of code that starts with a number and returns the number of steps without any loops.

All that because we found a general pattern:
How often can we apply x/2 to a number until its odd? : std::countr_zero(n) - very clear
How often can we apply (3x+1)/2 to a number until its even? : std::countr_one(n) - not so very clear

At the end I can say: The fastest code is code that is not called. So of course a series of numbers are perfect to lookup via dictionary but thats not a solution to the core problem.

For chess its exactly how you would write fast code.
1) implement a slow prototype.
2) replace all conditions with a branchless alternative (n = 1 << countr_zero(n)) would replace a while loop and is branchless.
3) get rid of all complex math and replace with branchless binary logic
4) find general patterns and use arrays to lookup the result directly without any binary logic at all
5) lookahead into a loop or recursive function.

Its so cool because chess is also a recursive problem. That shows that leapfrogging (generating moves + countermoves) in a single function could also be a very interesting approach to make things faster. And you could remove much code because its always "your own" move.

[dangi12012]

Full code:

Code: Select all

// Collatz.cpp : Copyright Daniel Infuehr. You must include my name in references if you use this code

#include <iostream>
#include <stdint.h>
#include <bit>
#include <chrono>
#include <atomic>
#include <cmath>

static uint64_t table_pow3[64];
static uint64_t table_pow3minuspow2[64];

//Threadsave impl
uint64_t steps(uint64_t n) {
    uint64_t steps;

    //Make input odd
    n >>= steps = std::countr_zero(n);

    while (n != 1) {
        //Repeated expand(e) 3x+1 until even
        uint64_t e = std::countr_one(n);
        steps += e * 2;

        //General form:
        //((3 ^ i) * n + (3 ^ i - 2 ^ i)) / 2 ^ i
        n = (table_pow3[e] * n + table_pow3minuspow2[e]) >> e;

        //Repeated division by 2(c) until odd
        uint64_t c = std::countr_zero(n);
        steps += c;
        n >>= c;
    }
    
    return steps;
}

int main()
{
    for (int i = 0; i < 64; i++) {
        uint64_t pow3 = std::pow(3, i);
        uint64_t pow2 = std::pow(2, i);
        table_pow3[i] = pow3;
        table_pow3minuspow2[i] = pow3 - pow2;
    }

    auto t1 = std::chrono::high_resolution_clock::now();
    std::atomic<uint64_t> sum = 0;

    #pragma omp parallel
    #pragma omp for
    for (int i = 2; i < 100000000; i++)
    {
        sum += steps(i);
    }
    auto t2 = std::chrono::high_resolution_clock::now(); 
    auto ms_int = duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    std::cout << sum << "\n";
    std::cout << ms_int / 1000.0 << "s";
}

[dangi12012]

Now here is the interesting part:
Both functions are 100% identical in a mathematical sense - I found some more interdependencies that could be resolved.

Branchless boolean algebra approach - Runs up to 64 iterations in a single branchless boolean algebra loop

Code: Select all

uint64_t steps(uint64_t n) {
    uint64_t steps = 0;
	
    while (n != 2) {
        uint64_t c = std::countr_zero(n);           //Repeated division by 2(c) until odd
        uint64_t e = std::countr_one(n >> c);     //Repeated expand(e) 3x+1 until even
       
        steps += 2 * e + c; //Steps this algo does in one loop
        n = (table_pow3[e] * (n >> c) + table_pow3minuspow2[e]) >> e; 
    }
	
    return steps - 2;
}

Naive approach - Runs 1 iteration per loop - has branches and is the conventional programming style

Code: Select all

uint64_t steps_naive(uint64_t n) {
    uint64_t steps = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
            steps++;
        }
        else {
            n = (3 * n + 1) / 2;
            steps += 2;
        }
    }
    return steps;
}

This is a nice problem - since the optimisations are visible in base2 only and not in base10.
Very much like chess where the naive array and mailslot approach is much slower than the bitboard approach - and the more sophisticated faster solutions make the code faster AND A LOT SIMPLER.
Kind of like revealing the underlying truth which is hidden and gets unveiled by optimizing.

[Sopel]

This is a chess forum and this is heavy offtopic.

[dangi12012]

This is a chess forum and this is heavy offtopic.

Expansion of recursive functions is the essence of chess. Too bad you dont see any connection between the two topics.
Also for everyone reading this Sopel is a forum troll if you look at his history. Extremely rude and never advancing a topic forward.
Dont engage with the troll.

[connor_mcmonigle]

This is a chess forum and this is heavy offtopic.

Expansion of recursive functions is the essence of chess. Too bad you dont see any connection between the two topics.
Also for everyone reading this Sopel is a forum troll if you look at his history. Extremely rude and never advancing a topic forward.
Dont engage with the troll.

Sopel is one of the most active Stockfish developers... Many of his posts here are insightful and productive to the conversation at hand. On the other hand, many of your posts seem solely dedicated to self aggrandizement (To be fair, I think your perft generator is quite neat if lacking in practical application).

In any case, the Collatz conjecture has little relation to chess and Sopel is completely justified in pointing out that your post is off topic. The update rule is not even recursive (well, I guess you could argue it's tail recursive if you really wanted to). FWIW, I do find your optimizations interesting, though better suited for some other forum.

[jhellis3]

Not sure if this is what you are looking for or not, but here you go:

https://www.dropbox.com/s/hugwaywmisfwk ... s.pdf?dl=0