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

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

Например, сдвигаешь влево 32 бита, а вдвигаешь в 0-й исключающее или между 30-м и 27-м битом. Только в начале надо вдвинуть хотя бы одну единицу.

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

Сообщение отредактировал 777777 - Nov 22 2008, 18:47

Спасибо, уже что-то есть. Идея понятна. А что если ещё использовать текущее значение какого-нибудь таймера? У меня в программе все 3 таймера заняты.

Я делал так:
В таймере, который выполняет свою функцию помещаю
RAN = rand(); //Случайное во времени число
A1 = RAN%32; //Получаем случайное число от 0 до 32 (если не ошибаюсь насчет 32)
В нужный момент в программе использую число RAN, которое поучается врезултате модуляции результата функции rand() временным интервалом. А использоваться это значение будет в разные моменты времени с различным интервалом добавляя этим случайность.

Надо учесть, что таймеры работают от того же генератора, что и процессор. Поэтому результаты при кадждом запуске будут одинаковые. Если же сама программа будет их брать в "случайное" время (например при нажатии пользователем кнопки), то наверное можно. Но опять же, зависит от соотношения частоты таймера и частоты получения от него "случайного" числа: ведь значение таймера всегда увеличивается, поэтому если брать значение, скажем, 10 раз за оборот (переполнение), то значения будут не очень случайными, а монотонно возрастающими. А если один раз за 5-10 оборотов, то могут возникнуть "биения" между частотой таймера и частотой обращений и ты каждый раз будешь попадать примерно в одно и то же место, в результате получаемое значение будет медленно плыть. Так что таймером ИМХО лучше не пользоваться.

Можно сделать програмный сдвиговый регистр с обратными связями(ОС),
в зависимости от разрядности регистра - соответствующие ОС,

http://www.qrz.ru/schemes/contribute/secur...enerator1.shtml

Чем больше разрядность регистра, тем равномерней шум ГПСП.

Я попробовал сдвигать влево один байт, перед сдвигом беру 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

Ближе всего мне 7-и битный вариант получается, буду на нём обкатывать, потом 5 бит попробую.
Да и по ссылке http://www.qrz.ru/...generator1.shtml для 7-и бит пример есть.
Важно, чтобы числа не повторялись 2 раза вподряд.

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

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


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

Можно сделать простой генератор ПСП по формуле x=(a*x+b)mod c
Вот пример для a=5, b=77, c=256


Так как нужно число до 32, то оставляем только 5 бит

Двух подряд одинаковых чисел точно не будет, но длина последовательности будет только 32. Начиная с 33 позиции серия будет повторятся.
Если взять старшие пять бит:

То последовательность будет более случайная (длина серии 256), но будут встречаться подряд идущие одинаковые числа.

Случайные - на значит разные! В случайной последовательности идущие подряд одинаковые числа не только могут, но и должны встречаться с вероятностью, вычисляемой теоретически.

Я сейчас так и сделал, только взял младшие 5 бит, а к результату применяю "исключающее или" текущего значения таймера, не заводя его значение в сам генератор. Результаты не повторяются, а до этого иногда было.

Посмотри, может что-то из этого поможет
http://vrtp.ru/index.php?showtopic=9500