Custom linear congruential generator in JavaScript

▲
4
▼

I am trying to create a custom linear congruential generator (LCQ) in JavaScript (the one used in glibc).

Its properties as it's stated on Wikipedia are: m=2^31 , a=1103515245 , c=12345.

Now I am getting next seed value with

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

Although the generator seems to work, but when the numbers are tested on canvas:

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

They seem to be horribly biased: http://jsfiddle.net/7VmR9/3/show/

Why does this happen? By choosing a different modulo, the result of a visual test looks much better.

The testing JSFiddle is here: http://jsfiddle.net/7VmR9/3/

Update

At last I fixed the transformation to canvas coordinates as in this formula:

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

Now the pixel coordinates are not so much malformed as when used the modulo operation.

Updated fiddle: http://jsfiddle.net/7VmR9/14/

javascript
canvas
random
functional-testing
lcg
asked on Stack Overflow Jul 12, 2013 by Stano • edited Dec 4, 2020 by Peter Mortensen

2 Answers

▲
4
▼

For the generator the formula is (you forgot a modulus in the first part):

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

I realize that you try to optimize it so I updated the fiddle with this so you can use it as a basis for the optimizations:

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

answered on Stack Overflow Jul 13, 2013 by (unknown user)
▲
3
▼

Yes, it looks like you solved it. I've done the same thing.

A linear congruential generator is in the form:

seed = (seed * factor + offset) % range;

But, most importantly, when obtaining an actual random number from it, the following does not work:

random = seed % random_maximum;

This won't work because the second modulus seems to counteract the effect of the generator. Instead, you need to use:

random = floor (seed / range * random_maximum);

(This would be a random integer; remove the floor call to obtain a random float.)

Lastly, I will warn you: In JavaScript, when working with numbers that exceed the dword limit, there is a loss of precision. Thus, the random results of your LCG may be random, but they most likely won't match the results of the same LCG implemented in C++ or another low-level language that actually supports dword math.

Also due to imprecision, the cycle of the LCG is highly liable to be greatly reduced. So, for instance, the cycle of the glibc LCG you reference is probably 4 billion (that is, it will generate over 4 billion random numbers before starting over and re-generating the exact same set of numbers). This JavaScript implementation may only get 1 billion, or perhaps far less, due to the fact that when multiplying by the factor, the number surpasses 4 billion, and loses precision in doing so.

answered on Stack Overflow Apr 28, 2014 by Codesmith • edited Dec 4, 2020 by Peter Mortensen

User contributions licensed under CC BY-SA 3.0