Pseudo Random Number Generator

[sorbus]

[There is a bug in the randRange() function. See this post. --admin]


I needed a PRNG for my game. I found the one provided by Mark Armbrust here:
http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Random-number-generator-for-hack-cpu-td4025503.html

which was a good start for me. However this got me doing a bit more research and ended up implementing a Linear Congruential Generator using the Schrage Method. LCG is old, tried and tested. Not the best these days but simple enough to be implemented in Jack. The key point is selection of the A and M values. For this I used an often cited paper which lists 'good values'. See code below for references.

Code is released below under the Simplified BSD license.

Hope it may prove useful to people on this forum.

While I'm here, I must say how much I am enjoying working through the book and projects. Currently implementing my game for Project 9 which I will post about when finished.

Also a huge thanks to Mark (cadet1620) who has helped me and many others through his helpful and encouraging posts.

Rowan
------------

/* LCGRandom.jack, released under the BSD 2-Clause License, also known as Simplified BSD or FreeBSD License"
 * Copyright (c) 2013, Rowan Limb
 * All rights reserved.
 * This software implements a PRNG based on Linear Congruential Generator (Schrage Method).
 * Based on method documented here: http://www.cems.uwe.ac.uk/~irjohnso/coursenotes/ufeen8-15-m/p1192-parkmiller.pdf
 * and using constants for A and M from  "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure" by Pierre L'Ecuyer, 1999 (citeseer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1024)
 *
 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
*/

class LCGRandom {
    static int seed;
    static int A;
    static int M;
    static int Q;
    static int R;

    function void setSeed(int newSeed) {
        let seed = newSeed;
        if(seed=0) {
           let seed=1;
        }
        let A=219;
        let M=32749;
        let Q=M/A;
        let R=Utils.mod(M,A);
        return;
    }

    /* returns a random int in range 0..(M-1) inclusive */
    function int rand() {
        var int test;
        let test=(A*(Utils.mod(seed,Q)))-(R*(seed/Q));
        if(test<0) {
           let seed=test+M;
        }
        else {
           let seed=test;
        }
        return seed;
    }

    /* returns a random int in range low..high inclusive */
    function int randRange(int low, int high) {
       var int scale;
       let scale = (M / (high - low + 1));
       return (LCGRandom.rand() / scale) + low;
    }
}

/* Utils.jack, released under the BSD 2-Clause License, also known as Simplified BSD or FreeBSD License"
 * Copyright (c) 2013, Rowan Limb
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
 * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
*/

class Utils {

    /* returns a % b */
    function int mod(int a, int b) {
        var int d;
        var int r;
        let d = Math.divide(a,b);
        let r = a - (b * d);
        return r;
    }
}

[cadet1620]

Very nice. Thank you for contributing a good PRNG.

--Mark

[michalh]

Hi,

Are we allowed to use this PRNG in our projects?

Thanks,
-- Michal

[sorbus]

Yes, sure that's why I posted it. Just be sure to acknowledge it in your code and read
the licence text in the code I posted. Also if you find any bugs or make improvements please post them back.

[peterxu422]

Can someone explain what the purpose of a seed is in a Random Number Generator? I've read definitions of it but still don't quite understand why a PRNG needs to be seeded.

[cadet1620]

A Pseudo Random Number Generator uses a mathematical function to generate the next "random" number from the previous "random" number.  If the sequence begins with the same seed value, it returns the same series of values.

This can be useful in testing if a particular starting seed causes a bug, but in general we want different sequences returned for each run of the program.

--Mark

[yc+]

Thanks for contributing, Rowan!

Random number generator is very useful and I used your Generator in my code.

[cadet1620]

There is a slight bug in the randRange function.

For certain values of the range, randRange(low, high) can return high+1.  The problem is caused by integer truncation of the scale value.

A quick fix is to detect any result that is greater than high and compute the the next random number in the sequence.

    /* returns a random int in range low..high inclusive */
    function int randRange(int low, int high) {
       var int scale;
       var int rand;
       let scale = (M / (high - low + 1));
       let rand = (LCGRandom.rand() / scale) + low;
       
       // =rand= can be greater than =high= because =scale= suffers from integer
       // truncation.  The correct calculation should be
       //    rand = MulDiv(LCGRandom.rand(), high+1 - low, M) + low
       // Where MulDiv(a, b, c) multiplies 16-bit =a= by 16-bit =b= giving 32 bit
       // result, then divides 32 bit result by 16-bit =c=.
       //
       // MulDiv is hard to implement in Jack, so the cheap fix is to try again
       // if the number was too big.
       
       while (rand > high) {
          let rand = (LCGRandom.rand() / scale) + low;
          }
       return rand;
    }

--Mark

[elauzel]

I tried to read that article in order to select the optimum A and M for numbers up to but not including 1000, but the article broke my brain. Can someone help me with this, and optionally provide a plain English summary?

[elauzel]

Scratch that, I had a misunderstanding. I can get a random number in my desired range using the appropriate function in the LCGRandom class!

[jrd]

Understood the concept of a seed for the random number generator.  However, can you pls clarify two points:

1) In practice, should a random number generator be seeded once per overall program execution (for example, perhaps at the initial call of a "void run()" method)?  Or, should the random number generator be re-seeded right before every usage/call of a get random number function?

2) What are some feasible/easy ways to seed a random number generator in Jack pls?

Thanks.

- JRD

[ivant]

1. You should seed only once per program run. A common way to seed (in other computers,  not in HACK) is to use the real time clock. Since the CPU is usually many times faster than the real time clock you'd end up using the same seed, so you'll generate the same numbers.

Another downside of seeding multiple times is, that you'll loose the distribution properties.

2. You can ask the user to press any key on the keyboard and measure how much time it took them with loop counter. You can then use this as seed.

On Wed, Aug 19, 2015, 06:38 jrd [via Nand2Tetris Questions and Answers Forum] <[hidden email]> wrote:

Understood the concept of a seed for the random number generator.  However, can you pls clarify two points:

1) In practice, should a random number generator be seeded once per overall program execution (for example, perhaps at the initial call of a "void run()" method)?  Or, should the random number generator be re-seeded right before every usage/call of a get random number function?

2) What are some feasible/easy ways to seed a random number generator in Jack pls?

Thanks.

- JRD

---

If you reply to this email, your message will be added to the discussion below:

http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Pseudo-Random-Number-Generator-tp4026059p4029138.html

To start a new topic under Project 9, email [hidden email]
To unsubscribe from Nand2Tetris Questions and Answers Forum, click here.
NAML

[cadet1620]

I stumbled across this rather interesting creature—I hesitate to call it a bug—hiding in the lowest 2 bits of the values returned by LGGRandom.rand().

  

The is the result of a 32K "random" walk using dir = LCGRandom.rand()&3 to select the direction for each step. It doesn't matter what you use for the seed value; all that a different seed does is change which pixel of the image is at the starting point (center of the screen).

(LCGs are notorious for problems with their loworder bits and I was searching for an example to show that. I sure didn't expect anything this dramatic!)

Several things are coming together to make this happen:

1. The entire length of the generated series is being used (plus a few more since the sequence is only 32748 long).
2. X_n and X_n+16374 have this interesting relationship:
   Bit 1 in the second half of the series is identical to the corresponding bit in the first half,
   Bit 0 in the second half of the series is the inverse of the corresponding bit in the first half.
3. This bit relationship causes the second half of the walk to be a diagonal reflection of the first half of the walk.
4. This reflection guarantees that the path will return to its starting point, therefore it is a closed path; the same figure will be drawn regardless of the starting point (seed) in the series.

Here's the source for the test code:
  creature.zip

 

Recommendations for safely using LCGRandom:

• Never use more than 16374 values from LCGRandom.
• Always use randRange()

 

--Mark

[I've written a new random number generator that supplies better randomness for large quantities of numbers. The cost of the better randomness is that it runs slower. See LFSR32Rand.]

[ybakos]

Coooool!

[krawby]

If the only problem is that you might return high+1, doesn't it seem a bit excessive to redo the whole calculation? I believe returning high in this case will suffice.

[krawby]

krawby wrote

If the only problem is that you might return high+1, doesn't it seem a bit excessive to redo the whole calculation? I believe returning high in this case will suffice.

I realized that there's a situation where this is not ideal. Considering your range is from 1 to 99, using this fix would give you a 1% of getting any number from 1 to 98, but 99 would have a 2% chance of showing up.

Is this example, 2% against 1% may not look like much, but as the range gets smaller, it gets worse.

In the worst case, where the range is from N-1 to N, the chances of getting N are 2 in 3 against 1 in 3 for N-1.