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

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

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

Спасибо, уже что-то есть. Идея понятна. А что если ещё использовать текущее значение какого-нибудь таймера? У меня в программе все 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 каждый) получилась такая диграмма распределения.
Нажмите для просмотра прикрепленного файла
При увеличении числа прогонов диаграмма почти выравнивается.
Да, пользователь будет иногда нажимать кнопку, а таймер работает с высокой частотой, поэтому его я попробую задействовать. Этот алгоритм я буду писать на ассемблере.

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

Ближе всего мне 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

Да, но для _псевдо_случайной последовательности это будет означать, что ряд закончился и далее начнется сначала (или откуда-то со середины).

Заблуждение.
Обычно генератор псевдослучайной последовательности у себя в потрохах имеет static переменную, про которую ваше утверждение верно (если значение этой переменной со временем повторится, то и значения на выходе генератора тоже начнут повторяться). Однако опять-таки обычно на выход генератора эта переменная выводится не "как есть" а через некоторый "перемалыватель". В итоге генератор ПСП может выдавать одинаковые подряд идущие значения, и это вовсе не обозначает что "последовательность зациклилась". Могу порекомендовать воспользоваться гуглом. Например весьма толково описано тут: http://algolist.manual.ru/maths/generator/

предлагаю чрезвычайно простой, но в определенных случаях вполне подходящий метод.
при помощи Excel строится таблица случайных чисел нужной длины (т.е. период повторения последовательности). Эта таблица загоняется в память на свободное место. Если свободного места много - можно сделать таблицу с огромным периодом повторения ПСП. ну, далее понятно: LPM r0, Z+ - и все дела. если программа занимает бОльшую часть памяти - то можно в качестве псевдослучайных чисел использовать собственно коды программы, заполнив эксельным "мусором" только незанятое место (чтобы не было больших участков 0xFF или чего-то одинакового).

И как бонус, более затрудненное дизассемблирование . Табличный метод в данном случае возможно подойдёт, надо лишь ограничить область адресов сверху, так как там много нулей.

2 Juras Pr.
А почему-бы просто не вычислять CRC от своего-же програмного кода побайтно (или побитно)? От CRC только 5 бит брать, младших или старших - без разницы. А в начале в CRC-аккумулятор случайное число, полученное от кнопки, нажимаемой пользователем, заносить. А наличие в коде FF-ов подряд ничего не испортит. Для CRC32 100 FF-ов ерунда.
P.S. То, что вы предлагаете, очень на вычисление CRC похоже. Только производящий многочлен у вас не самый лучший...

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

Вычислял когда-то. Вот тут можно взять:

http://andyplekhanov.narod.ru/science/galua.htm

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



Аха, еще есть такая наука математика. Только вот далеко не все в ней сильны...как папа у Васи. Большинству проще и быстрее, до определенных границ, прогнать алгоритм брутфорсом нежели пытаться въехать в несколько специализированных книжек на конкретную тему.

andran25,
спасибо, а также всем, кто подсказывал и помогал.

Так для этого как раз и существуют такие форумы как этот.
Каждый силен в своей области. А вместе мы составляем коллективный разум очень широкого диапазона знаний. Большую теорему Ферма вам тут, наверное, не раскажут, как доказывать,
а что-нибудь чуть по-проще - легко.
Спрашивайте - всегда помогут.