Генерация псевдонима

Question

Ниже приведен текст из структуры данных и анализа алгоритмов Марка Аллена Вессиса.

Следующее x (i + 1) следует читать как индекс x i + 1, а x (i) должен быть читать как x индекс i.

x (i + 1) = (a * x (i)) mod m.

Кроме того, общие для возврата случайного вещественного числа в открытом интервале (0, 1) (0 и 1 не являются возможными значениями); это можно сделать с помощью , делясь на m. Из этого случайного числа в любом отрезке [a, b] можно вычислить путем нормализации.

Проблема с этой подпрограммой заключается в том, что умножение может быть переполнение; хотя это не ошибка, она влияет на результат и , таким образом, псевдослучайность. Schrage дал процедуру, в которой все вычисления могут быть выполнены на 32-битной машине без переполнения. Мы вычисляем частное и остальное от m/a и определяем их как q и r соответственно.

В нашем случае при М = 2147483647 A = 48,271, Q = 127,773, г = 2,836, и г < д.

Мы

x(i + 1) = (a*x(i))mod m.---------------------------> Eq 1. 
      = ax(i) - m (floorof(ax(i)/m)).------------> Eq 2 

Также автор упоминает о:

x(i) = q(floor of(x(i)/q)) + (x(i) mod Q).--->Eq 3 

Мой вопрос

1. что делает автор в виду, случайного числа вычисляется путем нормализации?

2. Как автор пришел с Eq 2 из Eq 1?

3. Как автор пришел с Eq 3?

Answer 1

1. Если у Вас есть случайное число в диапазоне [0,1], вы можете получить число в диапазоне [2,5] (например) путем умножения на 3 и добавление 2.

Answer 2

1. Нормализация означает, что если у вас есть X ∈ [0,1], и вам необходимо, чтобы получить Y ∈ [а, Ь] можно вычислить

   Y = а + X * (Ь - а)

EDIT: 2. Предположим

a = 3, x = 5, m = 9 

Тогда мы имеем

где [ax/m] означает целую часть. Таким образом, мы имеем 15 = [ax/m]*m + 6
Нам нужно получить 6. 15 - [ax/m]*m = 6 =>ax - [ax/m]*m = 6 =>x(i+1) = ax(i) - [ax(i)/m]*m