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

[Juras Pr.]

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

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

[ae_]

...
Важно, чтобы числа не повторялись 2 раза вподряд.

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

Код

.equ  rnd=R15
.equ  tmp=R16

mov  tmp, rnd
lsl  rnd
lsl  rnd
add  rnd, tmp
ldi  tmp, 77
add  rnd, tmp
mov  tmp, rnd

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

Код

andi tmp, 0b00011111

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

Код

lsr  tmp
lsr  tmp
lsr  tmp

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

[777777]

Двух подряд одинаковых чисел точно не будет

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

[Огурцов]

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

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

[Petka]

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

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

[Огурцов]

Заблуждение.

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

Никто физически ничего не проверяет. Есть такая наука, называется теория конечных полей.

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

[SKov]

Аха, еще есть такая наука математика. Только вот далеко не все в ней сильны...как папа у Васи.

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