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.