Trebuie să parametrizez niște PRNG, să presupunem că am nevoie de numere pe 32 de biți. Dar când numerele nu par foarte aleatorii, dau rezultate proaste. Creatorii SplitMix au avut o problemă similară (rețineți că din câte am înțeles nu au rezolvat-o corect):
https://www.pcg-random.org/posts/bugs-in-splitmix.html
Așa că am nevoie de o funcție care să transforme să spunem numărul 1 în ceva de genul 10011110001101110111100110111001. Dar numărul 10100111101101010110001111100101 cu o complexitate algoritmică bună ar putea fi similară (desigur, Kolmorov ar putea avea aceeași complexitate algoritmică).
Deci hashing prin înmulțire: x = x*2654435769 mod 2^32 nu este opțiunea, deoarece putem găsi inversul multiplicativ modular, care ne-ar da 1 sau ceva rău oricum. Am încercat să folosesc bit mixer de la PCG:
uint32_t RXSMXS(uint32_t rxs)
{
uint8_t r;
r = rxs >> 28;
rxs = rxs ^ (rxs >> (4 + r));
rxs = rxs*277803737;
returnează rxs^(rxs >> 22);
}
Dar se pare că este și reversibil 1 la 1 (problema este bijecția, nu reversibilitatea în sine). Același murmur32:
uint32_t murmur32(uint32_t z)
{
z ^= (z >> 16);
z *= 0x85ebca6bul;
z ^= (z >> 13);
z *= 0xc2b2ae35ul;
returnează z ^ (z >> 16);
}
Este reversibil și bijetcion, nu-i așa (ca să putem găsi intrări care ne dau rezultate atât de proaste pe cât ne dorim)?
Deci, există o metodă bine cunoscută și eficientă pentru a face acest lucru? Adică - luați un număr cu o complexitate scăzută (sau mare) de Kolmogorov și scoateți un număr cu complexitate mare de Kolmogorov. Bineînțeles că o astfel de funcție/mapping nu ar fi bijecție, pentru că doar aruncăm câteva valori. Deci diferitele chei/coeficienți vor produce uneori aceleași rezultate.
Ideea mea este să definesc jumătate din număr ca o constantă, de exemplu să fie cei mai mulți biți semnificativi: 10011110001101110000000000000000 și apoi alegeți aleatoriu biții mai puțin semnificativi (atunci ar putea fi fiecare număr de 16 biți). Și apoi pune-l în mixerul de biți ca murmur32 sau altceva. Dar încă nu avem nicio garanție că murmur32 nu va transforma, de exemplu, 1001111000110111000000000000011 în 1, 2 sau 3. Așa că poate nu voi folosi un mixer (dar astfel de numere ar putea avea entropia algoritmică greșită în biți cel puțin semnificativi).
Aveți idei mai bune, dar eficiente?