# Pseudo Random Number Generator

16 messages
Open this post in threaded view
|

## Pseudo Random Number Generator

Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 Administrator Very nice. Thank you for contributing a good PRNG. --Mark
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 Hi, Are we allowed to use this PRNG in our projects? Thanks, -- Michal
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 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.
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 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.
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 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
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 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.
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 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 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
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 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?
Open this post in threaded view
|

## Re: Pseudo Random Number Generator

 Scratch that, I had a misunderstanding. I can get a random number in my desired range using the appropriate function in the LCGRandom class!
Open this post in threaded view
|

## Re: Pseudo Random Number Generator/Seed Questions & Clarification

 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 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
Open this post in threaded view
|

## Re: Pseudo Random Number Generator/Seed Questions & Clarification

 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
Open this post in threaded view
|

## Re: Pseudo Random Number Generator - Danger lurking in the low bits

 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: The entire length of the generated series is being used (plus a few more since the sequence is only 32748 long). Xn and Xn+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. This bit relationship causes the second half of the walk to be a diagonal reflection of the first half of the walk. 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.]
Open this post in threaded view
|

## Re: Pseudo Random Number Generator - Danger lurking in the low bits

 Coooool!