Генерация псевдослучайных последовательностей

Submitted by st on Sat, 14/06/2014 - 17:42

В массово-калькуляторную эпоху еще до появления МК-61/52 с командой КСч (неудачно реализованной, см. "Тайна ГСЧ раскрыта?" НиЖ №6-1989, "Беседа о случайных цифрах" НиЖ №12-1989) в программах требовалось генерировать случайные числа. Поскольку размер кода была ограничен, то приходилось использовать наиболее простые и короткие алгоритмы. Думаю, они могут пригодится и сейчас любому программисту, поставленному в условия ограниченного объема памяти и отсутствия подходящих библиотечных (встроенных) функций.

Генерация неповторяющейся последовательности целых чисел [1;P)

Использовалась в программировании игры "Морской бой".

Ni+1 = Ni * Q - INT(Ni * Q / P) * P

Ni - текущее случайное число;
INT() - функция выделения целой части дробного числа;
P - простое число;
Q = P - 3m выбирается близким к P/2.

N0 задаётся из указанного диапазона.

Например, для P = 101 и Q = 74 (m = 3) получаем генератор в диапазоне [1;100].

Генерация действительных чисел в диапазоне (0;1)

Использование степенной функции

ai+1 = 10ai - INT(10ai)

ai - текущее случайное число;
INT() - функция выделения целой части дробного числа.

a0 задаётся из указанного диапазона.

Использование константы Пи

Вариант 1. ai+1 = FRAC(11 * ai + Пи)

Вариант 2. ai+1 = FRAC((ai + Пи)5)

ai - текущее случайное число;
FRAC() - функция выделения дробной части числа.

a0 задаётся из указанного диапазона. Можно использовать число в формате 0,ddhhmm, где dd - текущий день, hh - текущий час, mm - текущая минута.

Приведенный список далеко не полный, буду рад любым дополнениям.

Математические

Comments

Submitted by Vlad_AB on Mon, 23/06/2014 - 16:14

Первый - третий генераторы ПСЧ проверил на HP Prime.

Для первого генератора (с простым параметром) при использовании одной формулы (первое значение - икс, второе [следующее] значение - игрек) получается дискретная диагональ для всего экрана. При использовании двух формул (одна для икс, другая для игрек) с разными начальными значениями получается дискретное заполнение экрана (см. скриншот).

Вариант программы "Звёздное небо" с двумя формулами:

EXPORT STARS_2(N)
BEGIN
LOCAL N1,N2;
N1:=1;
N2:=3;
RECT_P();
RECT_P(0,0,317,239,#FF0000h,#FFFFFFh);
FOR I FROM 1 TO N DO
N1:=N1*236-IP(N1*236/317)*317;
N2:=N2*158-IP(N2*158/239)*239;
PIXON_P(N1,N2);
END;
END;

Результат работы программы для 1 000 000 звёзд:

Второй генератор ПСЧ с одной формулой порождает семейство линий (экран перечёркивается несколькими линиями). При использовании двух формул экран заполняется полностью (при однократной проверке c 1000000 звёзд только один пиксель не закрасился), но имеется некоторый "градиентный" эффект, т.е. в процессе рисования плотность точек выше в левом верхнем углу экрана, а ниже в правом нижнем углу (самыми последними закрашиваются пиксели, расположенные ближе к правому нижнем углу).

Вариант программы "Звёздное небо" с двумя формулами:

EXPORT STARS_3(N)
BEGIN
LOCAL N1,N2,R1,R2;
N1:=0.92557452045;
N2:=0.150082152465;
RECT_P();
RECT_P(0,0,319,239,#FF0000h,#FFFFFFh);
FOR I FROM 1 TO N DO
N1:=10^N1-IP(10^N1);
R1:=IP(N1*318)+1;
N2:=10^N2-IP(10^N2);
R2:=IP(N2*238)+1;
PIXON_P(R1,R2);
END;
END;

Третий генератор ПСЧ с числом ПИ (1 вариант) с одной формулой порождает горизонтальную прямую. Вариант с двумя формулами (самый шустрый) целиком заполняет экран.

Вариант программы "Звёздное небо" с двумя формулами:

EXPORT STARS_4(N)
BEGIN
LOCAL N1,N2,R1,R2;
N1:=0.92557452045;
N2:=0.150082152465;
RECT_P();
RECT_P(0,0,319,239,#FF0000h,#FFFFFFh);
FOR I FROM 1 TO N DO
N1:=FP(11*N1+π);
R1:=IP(N1*318)+1;
N2:=FP(11*N2+π);
R2:=IP(N2*238)+1;
PIXON_P(R1,R2);
END;
END;

Второй вариант третьего генератора ПСЧ (с 1 и 2 формулами) не до конца заполняет экран, т.е. начиная с некоторого значения генерируемая последовательность начинает повторяться (рисование не завершено, а экран застыл, не обновляется). Генерируемая последовательность заметно короче чем у первого варианта третьего генератора.

Вариант программы "Звёздное небо" с двумя формулами:

EXPORT STARS_5(N)
BEGIN
LOCAL N1,N2,R1,R2;
N1:=0.92557452045;
N2:=0.150082152465;
RECT_P();
RECT_P(0,0,319,239,#FF0000h,#FFFFFFh);
FOR I FROM 1 TO N DO
N1:=FP((N1+π)^5);
R1:=IP(N1*318)+1;
N2:=FP((N2+π)^5);
R2:=IP(N2*238)+1;
PIXON_P(R1,R2);
END;
END;

Получается вот такой результат для 1 000 000 звёзд:

st's picture
Submitted by st on Tue, 24/06/2014 - 17:44

Очень наглядно, спасибо. На МК-61 такое было не нарисовать, а писать программу и ждать повторения последовательности - это дни счета.

На БК-0010 также были проблемы с ПСЧ, но там на экран выводились "летят утки" :) В НиЖ есть фото, присланные читателями того времени.