Псевдослучайный генератор чисел, Нужен несложный алгоритм Опции

[Juras Pr.]

Подскажите несложный алгоритм, генерирующий значения от 0 до 31 по псевдослучайному закону. Сверхравномерность распределения значений мне не нужна, а нужно, чтобы было хоть подобие случайности. Работаю в основном на ассемблере.

Сообщение отредактировал Juras Pr. - Nov 22 2008, 18:06

[Juras Pr.]

Я попробовал сдвигать влево один байт, перед сдвигом беру 3-й и 6-й биты (с другими битами получается хуже), применяю к ним XOR и результат заношу после сдвига в 0-й бит байта. А в результат беру 5 младших битов. Перед запуском в этот регистр (байт) было занесено значение $55.
После прогона алгоритма 3 раза (по 32 каждый) получилась такая диграмма распределения.

При увеличении числа прогонов диаграмма почти выравнивается.
Да, пользователь будет иногда нажимать кнопку, а таймер работает с высокой частотой, поэтому его я попробую задействовать. Этот алгоритм я буду писать на ассемблере.

Сообщение отредактировал Juras Pr. - Nov 22 2008, 21:03

[Огурцов]

Когда-то экспериментировал, только проверьте: длинну регистра нужно брать m = 2^n - 1, один бит крайний, второй может быть перед ним, либо самый первый, длиннна последовательности 2^m - 1, регистр инициализировать любым числом, отличным от нуля. Имхо, точно работает для 7, 15, 31 бит.

Сообщение отредактировал Огурцов - Nov 23 2008, 00:22

[SKov]

только проверьте: длинну регистра нужно брать m = 2^n - 1

Это, конечно, преувеличение.
Длину регистра можно брать любую. Для каждой длины m можно найти примитивный элемент поля GF(2^m), который даст на выходе регистра последовательность максимальной длины. В том числе можно подобрать и такой прим. элемент, который потребует только один сумматор в обратной связи. Кстати, этот вариант хоть и прост в реализации, но дает не очень хороший датчик. Чем больше сумматоров, тем датчик "псевдослучайнее".

[Огурцов]

Длину регистра можно брать любую.

Конечно, при условии, что есть возможность физически проверить всю последовательность.

В том числе можно подобрать и такой прим. элемент, который потребует только один сумматор в обратной связи.

Да, я на это и намекал.

[SKov]

Конечно, при условии, что есть возможность физически проверить всю последовательность.

Никто физически ничего не проверяет. Есть такая наука, называется теория конечных полей. Она занимается теоремами и доказательствами и не использует "физических" проверок
Есть таблицы примитивных элементов, которые уже "проверили". Если не ошибаюсь,
в книжке Лиддла и Нидеррайтера есть таблицы, которые можно использовать для создания регистров сдвига длиной до 160, которые будут гарантированно генерировать последовательность бит с периодом 2^160. Если будет свободное время, попробуйте проверить этот период "физически."
Кажется, это число сильно больше, чем число атомов в видимой части Вселенной