Генератор псевдослучайных чисел (ГПСЧ), Получение ПСЧ по seed-у и индексу внутри последовательности Опции

[fsergey]

Проще говоря нужна функция rand_value(int seed, int index).
Все ГПСЧ, что я видел, при генерации нового значения используют в качестве зерна предыдущее, либо модифицируют собственные задающие значения.
Поэтому получение n+1 числа в последовательности невозможно без расчёта предыдущих n чисел.
Мне же нужно получить произвольное число в последовательности без расчёта предыдущих.
Есть ли такие генераторы? Если нет, то что можно придумать?

[Rst7]

Есть ли такие генераторы? Если нет, то что можно придумать?

Не видал, но есть простой метод решения. Берете какой-нибудь алгоритм шифрования (например DES), и шифруете ключем seed открытый текст index. На выходе получаете случайные числа. Либо берете хэш-функцию (например, MD5) от композиции seed и index.

[fsergey]

Не видал, но есть простой метод решения. Берете какой-нибудь алгоритм шифрования (например DES), и шифруете ключем seed открытый текст index. На выходе получаете случайные числа. Либо берете хэш-функцию (например, MD5) от композиции seed и index.

Отличный вариант! Если не найду нужный ГПСЧ, то так и сделаю. Спасибо! ))

[Guest_TSerg_*]

Что мешает заполнить таблицу нужного размера от ГСЧ, а затем по индексу извлекать?

[fsergey]

Что мешает заполнить таблицу нужного размера от ГСЧ, а затем по индексу извлекать?

Даже если всю память контроллера займу таблицей, периодичность повторения ПСП будет для меня очень маленькой (

[Guest_TSerg_*]

Ну, хорошо. А открытый текст где держать? На большом брате и передавать по Wi-Fi?
Вы задачу поточнее изложите, а то фантазий много возникает.

[Fat Robot]

Выдумывайте функцию rng = f(seed, index) и проверяйте с помощью diehard test battery последовательность получившихся значений rng для index, который инкрементируется.

В основу f( a, b ) удобно положить, как уже написал Rst7, какой-нибудь готовый шифратор или кодер от простой комбинации битов seed и index.

[fsergey]

Ну, хорошо. А открытый текст где держать? На большом брате и передавать по Wi-Fi?
Вы задачу поточнее изложите, а то фантазий много возникает.

Время (индекс значения в последовательности) и ключ/полином, по условиям задачи, синхронизируются один раз в "безопасной среде".
Одинаковые значения должны синхронно формироваться на обоих устройствах для поддержания связи между собой.
Задача получения n-го значения последовательности выплывает из-за необходимости периодического восстановления синхронизма.
Это если вкратце.

[Tarbal]

Аналоговый генератор шума + АЦП. Хотя дополнительное железо мне не нравится, но для полноты картины...

[Guest_TSerg_*]

Аналоговый генератор шума + АЦП. Хотя дополнительное железо мне не нравится, но для полноты картины...

В этом случае никакой синхронизации не будет в принципе, а она ТС нужна.

P.S.
Если возникает рассинхронизация, то использовать передачу slave-девайсу нового значения seed и начинать синхронную генерацию ПСП (reset с новым seed).

[fsergey]

Вопрос, может уже не в эту тему...
Последовал совету вычислять md5 от комбинации времени и индекса.
Время вычисления md5 на целевом камне - 15.17 мкс.
Зато алгоритм хэша "MurmurHash2" - 0.59 мкс.
Предел 1 мкс.
Кто-нибудь слышал про MurmurHash2? И есть ли альтернативная и быстрая хэш функция?

[Fat Robot]

Альтернативная обязательно есть: любая функция с выходом фиксированной разрядности, зависящим от входа.

А мурмур-то почему не подходит?

xxhash посмотрите, но не думаю, что там кардинальные отличия по части быстродействия

И есть ли альтернативная и быстрая хэш функция?

[fsergey]

Альтернативная обязательно есть: любая функция с выходом фиксированной разрядности, зависящим от входа.

А мурмур-то почему не подходит?

xxhash посмотрите, но не думаю, что там кардинальные отличия по части быстродействия

мурмур как раз подходит! Тест на равномерность распределения, применительно к задаче, дал отличный результат.
За совет спасибо, xxhash тоже думаю потестировать.

[Fat Robot]

Тест на равномерность распределения не стоит и ломаного сентаво.

пример: rng = 0,1,2,3, 0,1,2,3, 0,1,2,3, ... имеет равномерное распределение в диапазоне [0; 3]

Я писал вам, чем проверяются RNG.

С другой стороны, если у вас все хорошо, то пусть так и будет. равномерно хорошо.

[fsergey]

Тест на равномерность распределения не стоит и ломаного сентаво.

пример: rng = 0,1,2,3, 0,1,2,3, 0,1,2,3, ... имеет равномерное распределение в диапазоне [0; 3]

Я писал вам, чем проверяются RNG.

С другой стороны, если у вас все хорошо, то пусть так и будет. равномерно хорошо.

Тест последовательностей по дайхарду (Runs Test):
49.76 - 49.82-% восходящих последовательностей для разных сидов. Покатит.
Тест Birthday Spacings ещё кажется интересным.
Идею понял. Благодарю!

[Tarbal]

В этом случае никакой синхронизации не будет в принципе, а она ТС нужна.

P.S.
Если возникает рассинхронизация, то использовать передачу slave-девайсу нового значения seed и начинать синхронную генерацию ПСП (reset с новым seed).

Да, увлекся.
Ну тогда М-последовательность самое то, что надо. И предопределенная и абсолютно неавтокоррелируемая.

[fsergey]

Да, увлекся.
Ну тогда М-последовательность самое то, что надо. И предопределенная и абсолютно неавтокоррелируемая.

Обращал внимание на М-последовательность, но она не позволяет вычислить n+1 элемент без вычисления n предыдущих. Поэтому отказался.

[Guest_TSerg_*]

Позволяет, если в качестве исходного состояния взять n-е, тогда на след шаге получим n+1.

[Task Solver]

Рассмотрим группу по умножению по модулю 2^32 она изоморфна декартову произведению двух групп по сложению по модулям 2^30 и 2. В исходной группе ровно 2^31 элемент, все нечётные. Видно, что самый длинный цикл в ней равен 2^30, такой элемент не сложно найти перебором, их там очень много, пусть такое число - A.

Далее случайное число формируется по формуле: (A^k)*B.

B - это какой то любой элемент группы (нечёное число), имеют смысл только 1 и 3, остальные получаются сдвигом степени.

Его легко посчитать используя разложение степени на сумму степеней двойки, просто анализируя двоичное представление.

k=53=(110101)

A^53=A*A^52=A*(A*A)^26=A*((A*A)^2)^13=...

Сепени равные 0, 1, 2, 4, 8, 16, 32, ... 2^29 можно заранее посчитать и записать в таблицу. Потом согласно битам k перемножить.

В качестве случайного числа взять 30 старших битов (или их подстроку), потому что младший бит всегда 1, а не самый младший тоже вроде постоянен.

Сообщение отредактировал Task Solver - Jan 30 2014, 19:04