Псевдослучайный хэш двух целых чисел

Мне нужна матрица NxN с 16-битным или 32-битным псевдослучайным равномерно распределенным числом по всему диапазону значений. N, к сожалению, очень большой (по крайней мере, 1e6), поэтому он не может быть предварительно сгенерирован (это займет около ТБ памяти). Единственный жизнеспособный вариант, о котором я могу думать, - использовать хэш моих индексов i и j в качестве матричных элементов.Псевдослучайный хэш двух целых чисел

Существует множество целых хеш-функций, но я не уверен, какие из них подходят по двум причинам.

-Достаточно 32-разрядные целые операции без знака. Так как N не менее 2^20, я не могу наивно объединить два индекса в один 32-битный ключ, не создавая ненужных коллизий.

-Примерность важна здесь, я не здание хэш-таблицы. Большинство целых хэшей, которые я нашел, предназначены для хэш-таблиц и не имеют очень сильных требований.

Возможное решение будет заключаться в криптографическом хеше, таком как SHA-2, но производительность важна, и это слишком дорого.

Предложения о том, как объединить два 32-битных uint в один wile, избегая шаблонов столкновений, уже очень помогут, поскольку я мог бы выбрать из всего диапазона 32-битных 32-х хэвых хэшей.

Некоторое понимание, по которому 32-х и 32-х хэшированные хэши имеют хорошую случайность, также будет высоко оценено.

Прегенерация 1 или 2 массивов из N случайных чисел не проблема, если это помогает.

В случае, если это имеет значение, целью являются графические процессоры, которые я пишу в последних версиях GLSL.

источник

2015-10-22 MaVo159

Не имея четкого понимания ваших потребностей, трудно сделать рекомендацию. У меня были хорошие результаты, используя [хэш-функцию Роберта Дженкинса] (http://www.burtleburtle.net/bob/hash/doobs.html) для аналогичных приложений за последние 20 лет. Он обладает очень хорошими свойствами для выпаса. Я бы сказал, что стоит попробовать. – njuffa

Полностью лавина, единообразие и отсутствие узоров - мои основные требования. – MaVo159

В этом случае определенно дайте хэш-функции Jenkins попробовать.Автор разместил код в общедоступном домене, поэтому вы можете использовать его практически для любой базы кода. Еще один хэш с хорошей лавиной в моем воспоминании - это хеш Murmur3. – njuffa

Как насчет использования LCG? Это хорошо известный факт, что в виде хп = (а * х + с) по модулю 2 где a mod 8 3 или 5 и c нечетно, то в результате конгруэнтной последовательности будет иметь период 2 .

Численные рецепты: а = 1664525, с = 1013904223, но есть тонны них

Форма уникальных x из i, j, и вычислить xn.

источник

2015-10-23 02:15:45

Здесь не подходит последовательность, которая зависит от предыдущих элементов. – MaVo159

@ MaVo159?! Вы писали: «Псевдослучайность здесь важна». Любой псевдослучайный RNG будет иметь зависимость от предыдущего элемента. Ваша хэш-функция будет иметь такую зависимость –

Нет, любое псевдослучайное rng зависит от состояния, но ваше решение зависит от предыдущего результата, что делает его непригодным в этом контексте. В этом случае это вход - это то, как работают хеши. Состояние не совпадает с предыдущим результатом в большинстве rng. – MaVo159

Я нашел подходящий алгоритм. Очевидно, подходят блокирующие шифры в режиме счетчика. Первоначально я отклонил эту идею из-за влияния производительности большинства блочных шифров. Тем не менее, я нашел документ, в котором представлен связанный алгоритм (в основном блок-шифр с меньшим количеством раундов), называемый Philox (Parallel Random Numbers: As Easy, как 1, 2, 3 от Salmon и др.).

Ссылка: http://www.thesalmons.org/john/random123/papers/random123sc11.pdf

Единственная проблема, которая возникает в том, как объединить два индекса в один ряд 32-битных. Но я думаю, что XOR должен быть достаточно хорош, если в сочетании с вращением, чтобы избежать коммутативности.

источник

2015-10-23 09:38:55 MaVo159

Псевдослучайный хэш двух целых чисел

ответ

Смежные вопросы