2016-09-22

Addition auf Umwegen – eine Knobelaufgabe

Hintergrund

Beim Herumexperimentieren mit (Pseudo-)Zufallszahlengeneratoren (wie z.B. dem KISS-Zufallszahlengenerator) kam ich auf die Idee, eine Art „Basisfunktion“ zu nehmen, die man dann parametrisieren und kombinieren kann, um Pseudozufallszahlen mit besserer/gleichmäßigerer Verteilung zu erhalten. Diese Basisfunktion ist unten als C++-Quellcode dargestellt.

Leider zeigte sich, dass die Parameter dieser Basisfunktion sorgfältig gewählt werden müssen, damit man brauchbare Pseudozufallszahlen erhält. Andernfalls korrelieren die Ein- und Ausgangswerte der Funktion einfach zu stark.

Die gegebene Basisfunktion

Die Funktion berechnet für einen gegebenen Eingabewert einen Ausgabewert. Dafür führt sie nacheinander eine XOR-Operation, eine Bitrotation und eine Multiplikation aus. Diese 3 Operationen sind jeweils parametrisiert (mit x, r und m).

Die Basisfunktion kann man als reine Funktion mit 4 Parametern, als Funktor oder als Klassentemplate implementieren:

in C, funktional in C++, als Funktor in C++, als Klassentemplate 
uint64_t xrm(uint64_t x,
             uint64_t r,
             uint64_t m,
             uint64_t value
            )
{
    value ^= x;
    value = (value>>r) + (value<<(64-r));
    value *= m;
    return value;
}

class XRM
{
public:
    XRM(uint64_t _x, uint64_t _r, uint64_t _m)
    : x(_x), r(_r), m(_m)
    {}
    
    uint64_t operator()(uint64_t value) const
    {
        value ^= x;
        value = (value>>r) + (value<<(64-r));
        value *= m;
        return value;
    }
    
    const uint64_t x, r, m;
};

template<uint64_t X, uint64_t R, uint64_t M>
class XRM
{
    public:
    uint64_t operator()(uint64_t value) const
    {
        value ^= X;
        value = (value>>R) + (value<<(64-R));
        value *= M;
        return value;
    }
};

Gesucht: Parameter für eine Addition

Es werden nun geeignete Parameter gesucht, so dass die Verkettung zweier XRM-Funktionen zu einer einfachen Addition mit 1 degeneriert:

in C, funktional in C++, als Funktor in C++, als Klassentemplate 
const uint64_t X1 = // gesucht!
const uint64_t R1 = // gesucht!
const uint64_t M1 = // gesucht!
const uint64_t X2 = // gesucht!
const uint64_t R2 = // gesucht!
const uint64_t M2 = // gesucht!

// true for all values:
xrm( X1, R1, M1, xrm(X2, R2, M2, value)) == value+1

const XRM xrm1(X1, R1, M1);
const XRM xrm2(X2, R2, M2);

// true for all values:
xrm1( xrm2( value )) == value + 1

const XRM<X1, R1, M1> xrm1;
const XRM<X2, R2, M2> xrm2;

// true for all values:
xrm1( xrm2( value )) == value + 1

Es gelten dabei die üblichen arithmetischen Regeln von C und C++, insbesondere das vorzeichenlose Datentypen nicht überlaufen, sondern eine Modulo-Arithmetik implementieren.