You are here
Генерация псевдослучайных последовательностей
В массово-калькуляторную эпоху еще до появления МК-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
Результаты тестирования генераторов ПСЧ
Первый - третий генераторы ПСЧ проверил на HP Prime.
Для первого генератора (с простым параметром) при использовании одной формулы (первое значение - икс, второе [следующее] значение - игрек) получается дискретная диагональ для всего экрана. При использовании двух формул (одна для икс, другая для игрек) с разными начальными значениями получается дискретное заполнение экрана (см. скриншот).
Вариант программы "Звёздное небо" с двумя формулами:
Результат работы программы для 1 000 000 звёзд:
Второй генератор ПСЧ с одной формулой порождает семейство линий (экран перечёркивается несколькими линиями). При использовании двух формул экран заполняется полностью (при однократной проверке c 1000000 звёзд только один пиксель не закрасился), но имеется некоторый "градиентный" эффект, т.е. в процессе рисования плотность точек выше в левом верхнем углу экрана, а ниже в правом нижнем углу (самыми последними закрашиваются пиксели, расположенные ближе к правому нижнем углу).
Вариант программы "Звёздное небо" с двумя формулами:
Третий генератор ПСЧ с числом ПИ (1 вариант) с одной формулой порождает горизонтальную прямую. Вариант с двумя формулами (самый шустрый) целиком заполняет экран.
Вариант программы "Звёздное небо" с двумя формулами:
Второй вариант третьего генератора ПСЧ (с 1 и 2 формулами) не до конца заполняет экран, т.е. начиная с некоторого значения генерируемая последовательность начинает повторяться (рисование не завершено, а экран застыл, не обновляется). Генерируемая последовательность заметно короче чем у первого варианта третьего генератора.
Вариант программы "Звёздное небо" с двумя формулами:
Получается вот такой результат для 1 000 000 звёзд:
Очень наглядно
Очень наглядно, спасибо. На МК-61 такое было не нарисовать, а писать программу и ждать повторения последовательности - это дни счета.
На БК-0010 также были проблемы с ПСЧ, но там на экран выводились "летят утки" :) В НиЖ есть фото, присланные читателями того времени.