ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ Российский патент 1995 года по МПК G06F7/58 

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

Известен датчик случайных чисел, распределенных по треугольному закону, содержащий генератор равномерно распределенных случайных чисел, сумматор и регистр памяти [1]
Недостатком датчика является невозможность имитации суперпозиций (сумм) усеченных законов распределений.

Наиболее близким по технической сущности является известный также датчик случайных чисел, распределенных по треугольному закону, включающий генератор равномерно распределенных случайных чисел, блок сравнения, умножитель, блок извлечения квадратного корня, вычитатель сумматор, пять регистров памяти, элемент задержки, два элемента И, шесть групп элементов И, две группы элементов ИЛИ [2]
Недостатком прототипа является также невозможность имитации суперпозиций усеченных законов распределений.

Цель изобретения расширение функциональных возможностей за счет получения распределения вероятностей суперпозиции равномерного и треугольного распределений.

Это достигается тем, что в генератор случайных чисел, содержащий генератор равномерно распределенных случайных чисел, умножитель, блок извлечения квадратного корня, первый вычитатель, сумматор, первый.пятый регистры памяти, первую.шестую группы элементов И, дополнительно введены второй и третий вычитатели, делитель, шестой.десятый регистры памяти 18, седьмая.девятая группы элементов И, синхронизатор, имеющий вход запуска, первый.четвертый управляющие выходы, первый.седьмой информационные входы, второй.шестой входы из которых подключены к выходам соответственно третьего.седьмого регистров памяти, а восьмой.десятый регистры памяти 16-18 соединены с информационными входами соответственно пятой.седьмой групп элементов И, выходы третьего регистра памяти подключены также к информационному входу третьей группы элементов И, первого и второго регистров памяти к информационным входам соответственно первой и второй групп элементов И, управляющие входы которых, а также вход генератора равномерно распределенных случайных чисел соединены с первым управляющим выходом синхронизатора, седьмой информационный вход которого соединен с выходом генератора равномерно распределенных случайных чисел, который подключен также к первому входу умножителя, вторым входом соединенного с выходом первой группы элементов 19, а выходом с входом уменьшаемого первого вычитателя, подключенного входом вычитаемого к выходу второй группы элементов И, а выходом к первому информационному входу синхронизатора, который соединен также с информационным входом четвертой группы элементов И, управляющий вход которой соединен с вторым управляющим выходом синхронизатора, к которому подключены также управляющие входы пятой, шестой и третьей групп элементов И, выход последней группы соединен с первым входом сумматора, вторым входом соединенного с выходом четвертой группы элементов И, а выходом с входом блока извлечения квадратного корня, выход которого соединен с входом делимого делителя, входом делителя соединенного с выходом пятой группы элементов И, а выходом подключенного входу уменьшаемого второго вычитателя и к входу вычитаемого третьего вычитателя, который входом уменьшаемого соединен с выходом седьмой группы элементов И, а выходом с информационным входом девятой группы элементов И, выходом соединенной с вторым выходом устройства, а управляющим входом с четвертым управляющим выходом синхронизатора, третий управляющий выход которого соединен с управляющим входом восьмой группы элементов И, соединенной выходом с первым выходом устройства, а информационным входом с выходом второго вычитателя, входом вычитаемого подключенного к выходу шестой группы элементов И.

На фиг.1 показана структурная схема генератора случайных чисел.

Генератор содержит генератор равномерно распределенных случайных чисел 1, умножитель 2, вычитатели 3, 4 и 5, сумматор 6, блок извлечения квадратного корня 7, делитель 8, регистры памяти 9-18, группы элементов И 19-27, и блок управления синхронизатор 28, информационные входы 29-35, вход запуска 36, управляющие выходы 37-40 синхронизатора 28, информационные выходы 41 и 42 генератора.

Все группы элементов И 19-27 аналогичны. Одна из групп-группа 19 раскрыта на фиг.2. Она построена на элементах И (на чертеже не показаны).

Блок управления cинхронизатор 28 (см.фиг.3) содержит блоки сравнения 43-46, элемент 47 задержки, элементы ИЛИ 48-51, группы элементов И 52-59, элементы И 60-73.

Генератор построен на типовых элементах комбинированного типа. Поэтому в исходном состоянии генератор готов к работе.

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

Найдем плотность вероятности суммы равномерного и треугольного распределений, определенных на одном интервале:
f(t) (1)
Значение плотности распределения при t t_м.

f(t_м) h Если взять интеграл от выражения (1), то получим функцию распределения следующего вида:
F(t)
Рассмотрим случай
t_н ≅t≅t_м.

C₁+

Преобразуем числитель
C₁tt_м С₁t_нt_м С₁tt_н + C₁t²_н + C₂t² 2C₂tt_м+ + C₂t²_н C₂t² + (C₁t_м С₁t_н 2C₂t_н)t + (C₂t²н -C₁t_нt_м + C₁t²_н).

Учитывая знаменатель, получаем квадратное уравнение вида
at² + bt + c,
где a b
c
Выразим t через равномерно распределенную случайную величину
at² + bt + c α
at² + bt + c α 0;
t
Нас интересует случай t ≥ 0, это возможно при выполнении следующих условий:
если b > 0,
^-b±0
≥ b
b² 4a(c- α) ≥ b²;
-4a(c- α) ≥ 0;
а(с- α) ≅0
с- α ≅ 0;
c ≅ α!
t= (2)
если b < 0;
-b ± ≥ 0
b² 4a(c- α) ≅ b²;
-4a(c- α) ≅ 0;
а(с- α) ≥ 0;
c ≥ α!
t= ; (3)
t= . (4)
Для случая t_м ≅ t ≅ t_к имеем
+ C1-

Производя аналогичные преобразования, получаем
C₁tt_к C₁tt_м С₁t_нt_к + C₁t_нt_м +C₂t²_к C₂t_кt_м С₂t_нt_к + +C₂t_нt_м C₂t²_к- -2C₂tt_к C₂t² -С₂(t²) + (C₁t_к C₁t_м + 2C₂t_к)t + +(C₁t_нt_м C₁t_нt_к C₂t_кt_м C₂t_нt_к + C₂t_нt_м).

at² + bt + c,
где a b
c
at² + bt + c α
at² + bt + c α 0;
t= т. к. a < 0 для t ≥ 0 получаем следующие условия
-b ± ≅ 0
b² 4а(с- α) ≅ b²,
-4а(с- α) ≅ 0;
4а(c- α) ≥ 0
c ≥ α
t= (5)
t= (6)
Введем обозначения:
β 4ac; h
ν 4а; P b²;
λ 2а; Z -h.

Тогда зависимости (2)-(6) примут вид
t11

Генератор работает следующим образом.

Предварительно в регистры памяти 9-18 заносятся коэффициенты, характеризующие вид функции плотности распределения вероятностей генерируемых чисел: β, ν, λ, h Р, Z, b, С, "0", q,
где q
Порядок занесения коэффициентов может быть любым (цепи занесения на чертеже не показаны).

При подаче запускающего импульса на вход 36 начинает работать синхронизатор 28 (см.фиг.3). Импульс с выхода 37 синхронизатора 28 запускает генератор равномерно распределенных случайных чисел 1, который генерирует очередное случайное число α в интервале (0,1), поступающее на первый вход умножителя 2. Это число умножается на коэффициент ν, записанный в первом регистре памяти 9. Произведение ν α поступает на вход уменьшаемого первого вычитателя 3. Из ν α вычитается коэффициент β хранящийся во втором регистре памяти 10. Разность ν α β поступает на вход синхронизатора 28.

Эта разность сопоставляется с коэффициентом β записанным в третьем регистре памяти 11. Если р ≥ν α-β (т.е. дискриминант ≥ 0), то работа генератора по формированию случайных чисел t при данном α продолжается. В противном случае на выходе элемента 61 появляется импульс, который, пройдя через элемент ИЛИ 49, элемент задержки 47 и элемент ИЛИ 48, с выхода 37 запускает генератор 1 для получения нового случайного числа α.

Пусть р ≥ν α-β Импульс появляется на выходе элемента И 60, вследствие чего элементом 44 сравнения сопоставляется α с коэффициентом q, хранящимся в седьмом регистре памяти 15. Этим сопоставлением α ≥ q определяется принадлежность α к одному из двух интервалов (см.фиг.4).

Одновременно элементом сравнения 46 также α сопоставляется с коэффициентом с, хранящимся в шестом регистре памяти 14, а элементом сравнения 45 проверяется условие b ≥ 0 (0 хранится в пятом регистре памяти 13, а коэффициент b в четвертом регистре памяти 12).

В результате сопоставления возможны различные варианты формирования случайных чисел по зависимостям (7) (11). Эти варианты представлены на фиг. 5.

На фиг.5 указаны номера выходов синхронизатора 28, на которых появляются сигналы при выполнении приведенных условий, а ниже номеров выходов номера зависимостей, по которым формируются случайные числа.

1. α < q,b ≥ 0, с≥α В этом случае импульсы появляются на выходах элементов И 63, 68, 72. Срабатывает элемент И 66 и далее импульс проходит на выход 37. Формирование случайного числа прекращается.

2. α <q, b ≥ 0, c < α Импульсы появляются на выходах элементов И 63, 68, 73, 67 и элемента ИЛИ 50 третьем выходе 39 синхронизатора 28.

Поскольку зависимости (7) (11) могут быть сведены к двум, а вычисления по ним отличаются прибавлением к коэффициенту результата, полученного после извлечения квадратного корня, или вычитанием этого результата, то порядок формирования случайных чисел следующий.

При выполнении условия Р ≥ν α-β (дискриминант ≥ 0) появляется импульс на выходе элемента И 60, который проходит на выход 38 и вызывает срабатывание по управляющему входу третьей, четвертой, пятой и шестой групп элементов И 21, 22, 23, 24 и 25. Вследствие этого осуществляется сумматором 6 сложение Р + ( ν α-β); блоком 7 извлечение квадратного корня делителем 8 деление квадратного корня на коэффициент λ, хранящийся в восьмом регистре памяти 16; вторым вычитателем 4 вычитание коэффициента h, хранящегося в девятом регистре памяти 17, из результата деления третьим вычитателем 5 вычитание из коэффициента Z (хранится в десятом регистре памяти 18) результата деления
Z
Таким образом, каждый раз вычисления осуществляются по зависимости (7) (11), однако на первый и второй выходы 41 и 42 проходят согласно тому, какой из элементов И 26, 27 (или оба) открыты по одному из входов импульсами с третьего и четвертого выходов 39 и 40 синхронизатора 28.

В рассматриваемом случае случайное число формируется по зависимости (7) и случайное число появляется на первом выходе 41 генератора.

3. α < q, b < 0, с < α Импульсы появляются на выходах элементов И 63, 69, 73, 70 и элемента ИЛИ 50 третьем выходе 39. Случайное число формируется по зависимости (8) и появляется на первом выходе 41 генератора.

4. α < q, b < 0, c ≥α Импульсы появляются на выходах элементов И 63, 69, 72, 71 и элементов ИЛИ 50, 51 третьем и четвертом выходах 39 и 40. Случайные числа формируются по зависимости (8) и (9) и выдаются с первого и второго выходов соответственно 41 и 42 генератора.

5. α ≥ q, c < α Импульсы появляются на выходах элементов И 62, 73, 65 и элемента ИЛИ 51 четвертом выходе 39 и 40. Случайное число формируется по зависимости (10) и (11) и выдается с второго выхода 42 генератора.

6. α ≥ q, c ≥ α Импульсы появляются на выходах элементов И 62, 72, 64 и элемента ИЛИ 50 и 51 третьем и четвертом выходах 39 и 40. Случайные числа формируются по зависимостям (10) и (11) и выдаются с первого и второго выходов 41 и 42 генератора.

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

Использование изобретения позволяет расширить функциональные возможности генератора за счет моделирования суперпозиции равномерного и треугольного распределения вероятностей.

Изобретение относится к области вычислительной технике и может быть использовано для решения задач статистического моделирования. Цель изобретения расширение функциональных возможностей за счет получения распределения вероятностей суперпозиции равномерного и треугольного распределений. Генератор содержит генератор равномерно распределенных случайных чисел 1, умножитель 2, вычитатели 3, 4 и 5, сумматор 6, блок извлечения квадратного корня 7, делитель 8, регистры памяти 9 18, блоки элементов И 19 27, блок управления 28, информационные входы 29 35, вход запуска 36, управляющие входы 37 40 блока 28, информационные выходы 41 и 42 генератора. Цель достигается введением двух вычитателей, делителя, пяти регистров памяти, трех блоков элементов И, блока управления с соответствующими связями. 5 ил.

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ, содержащий генератор равномерно распределенных случайных чисел, умножитель, блок извлечения квадратного корня, первый вычитатель, сумматор, пять регистров памяти, шесть блоков элементов И, отличающийся тем, что в него введены второй и третий вычитатели, делитель, пять регистров памяти, три блока элементов И, блок управления, вход запуска которого подключен к входу запуска генератора, с первого по пятый информационные входы блока управления соединены с выходами одноименных регистров памяти, выходы шестого, седьмого и восьмого регистров памяти соединены с информационными входами соответственно первого, второго и третьего блоков элементов И, выход первого регистра памяти соединен также с информационным входом четвертого блока элементов И, выходы девятого и десятого регистров памяти с информационными входами соответственно пятого и шестого блоков элементов И, управляющие входы которых и вход запуска генератора равномерно распределенных случайных чисел соединены с первым выходом блока управления, шестой информационный вход которого соединен с выходом генератора равномерно распределенных случайных чисел, подключенным к первому входу умножителя, второй вход которого подключен к выходу пятого блока элементов И, выход умножителя соединен с входом уменьшаемого первого вычитателя, вход вычитаемого которого подключен к выходу шестого блока элементов И, выход первого вычитателя соединен с первым информационным входом блока управления, соединенным с информационным входом седьмого блока элементов И, управляющий вход которого соединен с вторым выходом блока управления, подключенным к управляющим входам первого четвертого блоков элементов И, выход четвертого блока элементов И соединен с первым входом сумматора, второй вход которого подключен к выходу седьмого блока элементов И, выход сумматора соединен с входом блока извлечения квадратного корня, выход которого подключен к входу делимого делителя, вход делителя которого соединен с выходом первого блока элементов И, выход делителя подключен к входу уменьшаемого второго и третьего вычитателей, вход уменьшаемого третьего вычитателя соединен с выходом третьего блока элементов И, выход третьего вычитателя соединен с информационным входом восьмого блока элементов И, выход которого является первым выходом генератора, управляющий вход восьмого блока элементов И соединен с третьим выходом блока управления, четвертый выход которого соединен с управляющим входом девятого блока элементов И, выход которого соединен с вторым выходом генератора, информационный вход девятого блока элементов И соединен с выходом второго вычитателя, вход вычитаемого которого подключен к выходу второго блока элементов И.