Questions about PRNGs

Log in or register to post comments
Go To Last Post
5 posts / 0 new
Author
Message
kk6gm
kk6gm's picture
Level: Raving Lunatic
Joined: Fri. Sep 11, 2009
Posts: 3947 View posts
Location: Sacramento, CA
#1
Posted by kk6gm: Tue. Oct 20, 2020 - 04:18 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have a few questions about PRNGs.  Maybe somebody can point me to some answers online, or even answer them here.  Many thanks beforehand!

 

1) If a particular seed produces some sequence, say 79, 14, will 14 always follow 79 whenever 79 shows up with a different seed?  I presume not, but I don't know.

 

2) For reasonably small N (e.g. less than 100 or 1000 for a 32-bit PRNG), does PRNG mod N behave equally "well" (as a random number) for different N?  Especially, when N is very small, say 10 or 20?  What about when N is a small power of 2?

 

Thanks again.

Tags:

Tools, Compilers and General Programming
Top
curtvm
curtvm's picture
Level: Raving Lunatic
Joined: Wed. Sep 21, 2005
Posts: 3486 View posts
Posted by curtvm: Tue. Oct 20, 2020 - 05:06 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

1) you would lose the P in PRNG if you could pull that off, although with some way to add more parameters in the mix could hide the P a little better. Since there is no true random when P is in use, you can always plug in the same parameters and get the same results.

 

2) It depends on the generator. If my generator function first produces all odd numbers then all even numbers, it would make for a very bad 2 bit random generator (using bit0). I would assume any library produced rand generator is going to be fine for most needs, for most users.

 

If in doubt about what you are getting, just run some tests and see what it produces-

https://godbolt.org/z/54eG5n

(this is compiled for x86 to get printf output, but is using avr libc random)

Top
Scroungre
Scroungre's picture
Level: Posting Freak
Joined: Wed. Apr 18, 2007
Posts: 1487 View posts
Location: Southern California
Posted by Scroungre: Tue. Oct 20, 2020 - 05:25 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A pseudo-random number generator (at this point I'm thinking an LFSR) will generate a certain sequence, and the only difference the seed makes is where in that sequence you are.  So you might get 79, 14, 22 or 79, 15, 83, or something else.  Unless you have a stupidly trivial generator, no one value should be able to predict the next one - unless you know the entire sequence, and where you are in it.  Thus the 'pseudo'.

 

This also applies, even better, to results 'modulo N' wherein the outputs from the PRNG don't tell you where you are in the sequence.  For example, if you were generating 32-bit numbers modulo 26 to get letters in the English language, receiving the sequence "ABCDE" could show up several times in a 32-bit sequence, and you cannot accurately predict the next letter is "F".

 

I wrote a Morse Code trainer gizmo using a 16-bit LFSR (with adjustable (modulo N!) alphabet) in an AVR awhile back.  Never really got ready for prime time, but the idea was that it would a) generate 'code groups' that were not predictable and b) could be replayed (for checking) by inputting the same seed, and the same sequence would come out.

 

S.

 

Top
christop
christop's picture
Level: Hangaround
Joined: Fri. Jan 28, 2011
Posts: 375 View posts
Location: Arizona, USA
Posted by christop: Tue. Oct 20, 2020 - 06:24 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If the seed and internal state of the PRNG are larger than the random numbers it produces (such as a 32-bit seed and internal state and a 16-bit output), then no, 14 will not necessarily always follow 79 with different seeds.

 

For any non-power-of-2 N, using modulus will give a distribution that is biased toward the lower end of the range. For small N, the bias can be small enough to ignore, but keep in mind that it's still there. For example, with N=10 and RAND_MAX=4294967295, values 0 through 4 will be generated with a probability of 429496730 / 4294967295 each, while values 5 through 9 have a slightly lower probability of "only" 429496729 / 4294967295 each.

 

For a power-of-2 N, the low bits are (generally) lower quality than the high bits, so it would make more sense to divide the random number by ((RAND_MAX+1)/N) instead of mod N.

 

See also Stack Overflow: Why do people say there is modulo bias when using a random number generator?

Top
kk6gm
kk6gm's picture
Level: Raving Lunatic
Joined: Fri. Sep 11, 2009
Posts: 3947 View posts
Location: Sacramento, CA
Posted by kk6gm: Tue. Oct 20, 2020 - 06:45 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks to all for the good info so far.

Top