Sign in to follow this  

Random Numbers

This topic is 4376 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Some chipsets (i820 was the first) can produce truly random numbers by sampling thermal noise. As an alternative, the technique (*) used by modern Unix variants for /dev/random is cryptographically secure and can therefore be called random. (pseudo-RNGs may satisfy statistical tests for randomness, but they are often predictable after observing a few outputs)

* gather entropy from various sources such as keyboard input and network traffic; mix together in a pool via strong hash function; return bytes from this pool.

Share this post


Link to post
Share on other sites
However, it should be noted that in practical applications being able to generate predictable and repeatable pseudo-random number sequences is often desirable. For example, if you're debugging a piece of code or some other stochastic simulation it's nice to be able to reproduce the same input values over and over so that they become a constant rather than a variable. For cryptography, maybe it's not so good. Just don't want anyone thinking that pseudo-random isn't as "good" as truly random because they both have their places.

Share this post


Link to post
Share on other sites
Also, in computer graphics you often need pseudorandom because you don't want procedural textures to be different each time. Practically "true" random is necessary mostly for cryptography, in fact i know of no other things that really can't use good pseudorandom number generator and need "true" randomness.

Share this post


Link to post
Share on other sites
"Common" methods for "random" numbers:

1) Psuedo-RNG - complex mathematical forumla creates seemingly random numbers. Good for games, not so good for cryptography. (/dev/random on *nix?)

2) Psuedo-RNG + Noise - things like a sampling of network activity XORed against the PRNG. Little benifit except added cryptography strength (/dev/srandom on *nix? - can block if not enough data from the environment to sample)

3) Quantum RNG - things like sampling thermal noise, sampling photons against a 50% opaque surface - link for some examples. The most cryptographically secure.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You can ask the user to move the mouse about for a few seconds and pick (x,y) points at regular intervals.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
You can ask the user to move the mouse about for a few seconds and pick (x,y) points at regular intervals.

This is amazingly not random, actually. Many people will perform the exact same motions every single time they're asked to do so, resulting in almost identical results every time. This is highly undesirable.

CM

Share this post


Link to post
Share on other sites
From the looks of the question, the OP just wants to know how some magical function could produce a seemingly random number?

It is typically implemented pretty much as follows.
long holdrand;
void srand(long seed)
{
holdrand = seed;
}
short rand()
{
return (short)((holdrand = holdrand * 214013 + 2531011) >> 16);
}
Simple eh!

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
From the looks of the question, the OP just wants to know how some magical function could produce a seemingly random number?

It is typically implemented pretty much as follows.
long holdrand;
void srand(long seed)
{
holdrand = seed;
}
short rand()
{
return (short)((holdrand = holdrand * 214013 + 2531011) >> 16);
}
Simple eh!


Not really. I think the right shift by 16 bits causes this to be a bad one!
For instance, off hand I guess that this version of rand returns numbers which will almost surely end with 0x26. Instead of taking a mod you are doing a shift. Not the same thing. Taking the lower 16 bits would probably have been better. Though i admit, your code needs more analysis to claim that this one is not a good one :-)...

I think what IMalc wanted to refer to is a Linear Congruential Generator

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Conner McCloud
Quote:
Original post by Anonymous Poster
You can ask the user to move the mouse about for a few seconds and pick (x,y) points at regular intervals.

This is amazingly not random, actually. Many people will perform the exact same motions every single time they're asked to do so, resulting in almost identical results every time. This is highly undesirable.

CM

That is not physiologically feasible. Draw a 2D spline on your screen and I defy you to go through the very same curve again and at the very same speed. Even your own signature is not perfectly identical.

BTW, this is how the encryption key is generated for RIM Blackberries.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
That is not physiologically feasible. Draw a 2D spline on your screen and I defy you to go through the very same curve again and at the very same speed. Even your own signature is not perfectly identical.

It isn't neccessary that it be perfectly identical...just close enough to disturb the randomness. And besides, I guarentee I can perform the same actions over and over again: just don't move it at all, or use a different input device that allows more precice motion.
Quote:
Original post by Anonymous Poster
BTW, this is how the encryption key is generated for RIM Blackberries.

It asks you to move the mouse for a few seconds? Doubtful, especially for encryption.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
Quote:
Original post by Anonymous Poster
You can ask the user to move the mouse about for a few seconds and pick (x,y) points at regular intervals.

This is amazingly not random, actually. Many people will perform the exact same motions every single time they're asked to do so, resulting in almost identical results every time. This is highly undesirable.

CM


You could pick at "random" intervals instead (using the built-in PRNG), and/or sample just the low-order bits of the mouse coordinates (difficult for the user to come to the exact same pixel each time)...

Edit: Yes, the "standstill input" is a problem if the user doesn't have a motivation to help out with the randomness... you need (if possible; otherwise use another method - this is probably bad for games, for example) to design the app so that there is motivation, and then if the user won't comply, the results are well deserved. :)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Conner McCloud
And besides, I guarantee I can perform the same actions over and over again: just don't move it at all {...}

It's not that complicated to detect when a mouse doesn't move or when the range of movements is not large enough to be significant.
Quote:
Original post by Conner McCloud
{...} or use a different input device that allows more precice motion.

Input devices tend to increase in precision, not the other way around. Besides, the increase in precision makes it even more difficult to repeat the *exact* same movements. Remember that you can register mouse position, speed and acceleration, all of which are very difficult to replicate *exactly* by a human.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aryabhatta
Quote:
Original post by iMalc
From the looks of the question, the OP just wants to know how some magical function could produce a seemingly random number?

It is typically implemented pretty much as follows.
long holdrand;
void srand(long seed)
{
holdrand = seed;
}
short rand()
{
return (short)((holdrand = holdrand * 214013 + 2531011) >> 16);
}
Simple eh!


Not really. I think the right shift by 16 bits causes this to be a bad one!
For instance, off hand I guess that this version of rand returns numbers which will almost surely end with 0x26. Instead of taking a mod you are doing a shift. Not the same thing. Taking the lower 16 bits would probably have been better. Though i admit, your code needs more analysis to claim that this one is not a good one :-)...

I think what IMalc wanted to refer to is a Linear Congruential Generator
You unfortunately don't know what you're talking about. I didn't just pull this out of thin air.
This is a standard implementation of a random number generator, taken from a common runtime library. Search for the above two prime numbers on google and you'll most likely get tons of search results with variants of this prng.
The upper 16 bits are far more random than the lower 16.
I know that this is a Linear congruential generator.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by Aryabhatta
<snip>

Though i admit, your code needs more analysis to claim that this one is not a good one :-)...

I think what IMalc wanted to refer to is a Linear Congruential Generator
You unfortunately don't know what you're talking about. I didn't just pull this out of thin air.
This is a standard implementation of a random number generator, taken from a common runtime library. Search for the above two prime numbers on google and you'll most likely get tons of search results with variants of this prng.
The upper 16 bits are far more random than the lower 16.
I know that this is a Linear congruential generator.



Whoa! Slow down there pal...Sorry If I offended you. I didn't mean to.

I did say your code needs more analysis before anyone can claim it is a bad one! What I stated was my opinion.. Hence the words "I think".

Upon rereading the chapter in Knuth, in LCG's the higher order bits are more random than the lower order bits if the modulus equals the word size, which is true in this case. So taking the higher order 16 bits is right.. but this RNG is pretty bad nonetheless.

[Edited by - Aryabhatta on December 19, 2005 3:52:49 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
I didn't just pull this out of thin air.
This is a standard implementation of a random number generator, taken from a common runtime library.


It's a standard RNG used by many standard C library implementations, and it's good enough for simple applications, but it's actually a pretty poor selection of parameters. It fails certain tests of randomness and degenerates into very short sequences given certain seed values.

A better selection might be Lewis, Goodman, and Miller's rand0 (a=16807, c=0, m=2147483647) or possibly the Lehmer generator (a=48271, c=0, m=2147483647). These have been thoroughly analysed and found much better than the rand() function.

You can eliminate the LCG's pairwise sawtooth with a lagged fibonacci seived through a discard block filter (google for James's luxury-level-3 integer adaptation of Luescher's generator) or better yet, Matsumoto and Nishimura's Mersenne Twister. Both lagged fibonacci and the mersenne twister are faster, and produce better "randomness" by most accepted definitions, and have longer periods than the good ol' LCG, but they take considerably more memory.

It is important, however, to realize that the bitshift is a better way to select an integral subrange than is using the % operator, which is what most people do.

--smw

Share this post


Link to post
Share on other sites
Quote:
Original post by Aryabhatta
Quote:
Original post by iMalc
Quote:
Original post by Aryabhatta
<snip>

Though i admit, your code needs more analysis to claim that this one is not a good one :-)...

I think what IMalc wanted to refer to is a Linear Congruential Generator
You unfortunately don't know what you're talking about. I didn't just pull this out of thin air.
This is a standard implementation of a random number generator, taken from a common runtime library. Search for the above two prime numbers on google and you'll most likely get tons of search results with variants of this prng.
The upper 16 bits are far more random than the lower 16.
I know that this is a Linear congruential generator.



Whoa! Slow down there pal...Sorry If I offended you. I didn't mean to.

I did say your code needs more analysis before anyone can claim it is a bad one! What I stated was my opinion.. Hence the words "I think".

Upon rereading the chapter in Knuth, in LCG's the higher order bits are more random than the lower order bits if the modulus equals the word size, which is true in this case. So taking the higher order 16 bits is right.. but this RNG is pretty bad nonetheless.
I'm sorry, I shouldn't have acted so defensively. I've oft heard that it isn't a terrific prng, but one seldom comes across a case where anything more random is needed (especially for a beginner). For example a particle generator animation would look indistinguishable from one with a better prng. It's only when you come to analyse where every individual droplet landed over a long period of time that you'd notice any difference.

Share this post


Link to post
Share on other sites

This topic is 4376 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this