This post was updated on .
[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://nand2tetrisquestionsandanswersforum.32033.n3.nabble.com/Randomnumbergeneratorforhackcputd4025503.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 2Clause 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/ufeen815m/p1192parkmiller.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..(M1) 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 2Clause 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; } } 
Administrator

Very nice. Thank you for contributing a good PRNG.
Mark 
Hi,
Are we allowed to use this PRNG in our projects? Thanks,  Michal 
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. 
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.

Administrator

This post was updated on .
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 
In reply to this post by sorbus
Thanks for contributing, Rowan!
Random number generator is very useful and I used your Generator in my code. 
Administrator

In reply to this post by sorbus
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 16bit =a= by 16bit =b= giving 32 bit // result, then divides 32 bit result by 16bit =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 
In reply to this post by sorbus
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?

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

In reply to this post by cadet1620
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 reseeded 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 
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: 
Administrator

This post was updated on .
In reply to this post by sorbus
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:
Here's the source for the test code:
Recommendations for safely using LCGRandom:
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.] 
Coooool!

In reply to this post by cadet1620
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 N1 to N, the chances of getting N are 2 in 3 against 1 in 3 for N1. 
Free forum by Nabble  Edit this page 