Пользовательский линейный конгруэнтный генератор в Javascript

Question

Я пытаюсь создать пользовательский линейный конгруэнтный генератор (тот, который используется в glibc) в Javacript.
Его свойства, как указано в Википедии: m=2^31, a=1103515245, c=12345,

Теперь я получаю следующее начальное значение с

x = (1103515245 * x + 12345) % 0x80000000 ; // (the same as &0x7fffffff)

Хотя генератор, кажется, работает, но когда числа проверены на холсте:

cx = (x & 0x3fffffff) % canvasWidth; // coordinate x (the same for cy)

они кажутся ужасно предвзятыми: http://jsfiddle.net/7VmR9/3/show/

Есть идеи о том, почему это происходит? При выборе другого по модулю результат визуального теста выглядит намного лучше.

Тестирование jsfiddle находится здесь: http://jsfiddle.net/7VmR9/3/

Обновить

Наконец я исправил преобразование в координаты холста, как в этой формуле:

var cx = ((x & 0x3fffffff)/0x3fffffff*canvasWidth)|0

Теперь координаты пикселей не так искажены, как при использовании операции по модулю.
Обновленная скрипка: http://jsfiddle.net/7VmR9/14/

Answer 1

Для генератора формула (вы забыли модуль в первой части):

current = (multiplier * current * modul + addend) % modulus) / modulus

Я понимаю, что вы пытаетесь оптимизировать его, поэтому я обновил скрипку, чтобы вы могли использовать ее в качестве основы для оптимизации:

http://jsfiddle.net/AbdiasSoftware/7VmR9/12/

Answer 2

Да, похоже, ты решил это. Я сделал то же самое.

Линейный конгруэнтный генератор имеет вид:

seed = (seed * factor + offset)% диапазон;

Но, самое главное, при получении из него фактического случайного числа следующее НЕ работает:

random = seed% random_maximum;

Это не будет работать, потому что второй модуль, кажется, противодействует эффекту генератора. Вместо этого вам нужно использовать:

случайный = пол (семя / диапазон * random_maximum);

(это будет случайное целое число; удалите floor позвоните, чтобы получить случайное число с плавающей точкой.)

---

Наконец, я предупрежу вас: в javascript при работе с числами, которые превышают предел dword, происходит потеря точности. Таким образом, случайные результаты вашего LCG могут быть случайными, но они, скорее всего, не будут совпадать с результатами того же LCG, реализованного в C++ или другом низкоуровневом языке, который фактически поддерживает математику dword.

Также из-за неточности, цикл LCG очень подвержен значительному сокращению. Так, например, цикл glibc LCG, на который вы ссылаетесь, составляет, вероятно, 4 миллиарда (то есть он сгенерирует более 4 миллиардов случайных чисел, прежде чем начинать заново и заново генерировать точно такой же набор чисел). Эта реализация js может получить только 1 миллиард, или, возможно, намного меньше, из-за того факта, что при умножении на коэффициент это число превышает 4 миллиарда, и при этом теряет точность.