Мне нужно параметризовать некоторый PRNG, допустим, мне нужны 32-битные числа. Но когда числа не выглядят очень случайными, это дает плохие результаты. У создателей SplitMix была аналогичная проблема (обратите внимание, насколько я понимаю, они решили ее неправильно):
https://www.pcg-random.org/posts/bugs-in-splitmix.html
Поэтому мне нужна функция, которая преобразует, скажем, число 1 в что-то вроде 10011110001101110111100110111001. Но число 10100111101101010110001111100101 с хорошей алгоритмической сложностью (я имею в виду колмогоровскую сложность) может оставаться таким же хорошим (конечно, не обязательно должно быть таким же).
Таким образом, хеширование путем умножения: x = x*2654435769 mod 2^32 не вариант, потому что мы можем найти инверсию модулярного мультипликатива, что даст нам 1 или что-то плохое в любом случае. Я пытался использовать битовый микшер от PCG:
uint32_t RXSMXS (uint32_t rxs)
{
uint8_t р;
г = гхз >> 28;
rxs = rxs ^ (rxs >> (4 + r));
гкс = гкс * 277803737;
вернуть rxs^(rxs >> 22);
}
Но похоже, что он также обратим 1 к 1 (проблема в биекции, а не в самой обратимости). Тот же ропот32:
uint32_t бормотание32(uint32_t z)
{
г ^= (г >> 16);
г *= 0x85ebca6bul;
г ^= (г >> 13);
г *= 0xc2b2ae35ul;
вернуть z ^ (z >> 16);
}
Это обратимо и биективно, не так ли (чтобы мы могли найти входные данные, которые дают нам такой плохой результат, как мы хотим)?
Итак, есть ли известный и эффективный способ сделать это? Я имею в виду - взять число с некоторой низкой (или высокой) колмогоровской сложностью и вывести число с высокой колмогоровской сложностью. Конечно, такая функция/отображение не будет биекцией, потому что мы просто отбрасываем некоторые значения. Таким образом, разные ключи/коэффициенты иногда дают одинаковые результаты.
Моя идея состоит в том, чтобы определить половину числа как константу, например, пусть старшие значащие биты будут: 100111100011011100000000000000000, а затем просто случайным образом выберите младшие значащие биты (тогда это может быть каждое 16-битное число). А затем поместите это в битовый микшер, например, murmur32 или что-то еще. Но у нас все еще нет гарантии, что murmur32 не превратит, например, 100111100011011100000000000000011 в 1, 2 или 3. Так что, возможно, я не буду использовать миксер (но такие числа могут иметь неправильную алгоритмическую энтропию в младших битах).
У вас есть лучшие, но эффективные идеи?