A new classification method for RNGs: Significance Level

[joe]

My experiments show that the random number generator
in Microsoft's VC++6 compiler is a statistical RNG with a
significance level 1.0%.
Statistical testing at SL >1.0% (for example 1.001%) passes the test,
but 1.0% does not pass...

Can anybody confirm this finding?

The RNG function of the various SW products can be
analyzed and classified better using its significance level
as shown above.
I think this IMO important finding deserves a deeper research... :-)

For the testing method see:
http://en.wikipedia.org/wiki/Binomial_test
http://en.wikipedia.org/wiki/Binomial_distribution

[joe]

"Jerry Coffin" <jc*****@taeus. comwrote:

jo*@iamnotathom e.org.invalid says...

[ ... ]

The two loops I used are not that important.
I just simulate 30 days with each day 500 rand's (ie. spins, draws etc.).
At the beginning of each day the frequency stats are cleared.
Ie. the tests are done for intraday stats only.
I hope this makes it clear.

BTW, there is also a parallel discussion on this in sci.math
under the subject "Detecting biased random number generators".

Out of curiosity, what exact code are you using to get from the original
range of the generator to the 0-35 that you're using?

Jerry, it is 0 to 36.
As recommended in many books (for example Phillip Good
"Permutatio n, Parametric and Bootstrap Tests of Hypotheses")
I use the following:

int genrand(int lo, int hi)
{
int z = rand() % (hi - lo + 1) + lo;
return z;
}
....
int r = genrand(0, 36);

[Richard Heathfield]

joe said:

<snip>

Pete, can you confirm that then the max possible value
one can get is RAND_MAX - 1, and not RAND_MAX ?

He can't, because it isn't so.

The Standard says that "RAND_MAX [...] expands to an integral constant
expression, the value of which is the maximum value returned by the rand
function".

<snip>

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[joe]

"Richard Heathfield" <rj*@see.sig.in validwrote:

>
The Standard says that "RAND_MAX [...] expands to an integral constant
expression, the value of which is the maximum value returned by the rand
function".

My final version:

int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;
const unsigned maxr = RAND_MAX + 1 - ((RAND_MAX + 1) % range);
unsigned value = maxr;
while (value >= maxr)
value = rand();
return value % range;
}

[Jerry Coffin]

In article <g5**********@a ioe.org>, jo*@iamnotathom e.org.invalid says...

[ ... ]

Jerry, it is 0 to 36.

Okay -- not that it makes any real difference in terms of the algorithm.

As recommended in many books (for example Phillip Good
"Permutatio n, Parametric and Bootstrap Tests of Hypotheses")
I use the following:

int genrand(int lo, int hi)
{
int z = rand() % (hi - lo + 1) + lo;
return z;
}
...
int r = genrand(0, 36);

I had a hunch you might be doing it in a manner that was biased, and I
was right. Here's how I do it:

#include <stdlib.h>

int rand_lim(int limit) {
/* return a random number between 0 and limit inclusive.
*/

int divisor = RAND_MAX/(limit+1);
int retval;

do {
retval = rand() / divisor;
} while (retval limit);

return retval;
}

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Pete Becker]

On 2008-07-12 22:59:09 -0400, "joe" <jo*@iamnotatho me.org.invalids aid:

"Richard Heathfield" <rj*@see.sig.in validwrote:

>>
The Standard says that "RAND_MAX [...] expands to an integral constant
expression, the value of which is the maximum value returned by the rand
function".

My final version:

int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;

This last step isn't right. If the caller asks for random numbers in a
particular range, either return random numbers in that range or report
an error.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[vippstar]

On Jul 13, 2:35 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-07-12 22:59:09 -0400, "joe" <j...@iamnotath ome.org.invalid said:

"Richard Heathfield" <[e-mail].i nvalidwrote:

The Standard says that "RAND_MAX [...] expands to an integral constant
expression, the value of which is the maximum value returned by the rand
function".

My final version:

int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;

This last step isn't right.

<snip>
It's redundant, but not wrong.

[Pete Becker]

On 2008-07-13 09:17:51 -0400, vi******@gmail. com said:

On Jul 13, 2:35 pm, Pete Becker <p...@versatile coding.comwrote :

>On 2008-07-12 22:59:09 -0400, "joe" <j...@iamnotath ome.org.invalid said:

>>"Richard Heathfield" <[e-mail].i nvalidwrote:

>>>The Standard says that "RAND_MAX [...] expands to an integral constant
expression , the value of which is the maximum value returned by the rand
function".

>>My final version:

>>int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

>>if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;

This last step isn't right.

<snip>
It's redundant, but not wrong.

How is it redundant? If the caller asks for a range that's larger than
this distribution can handle and this check isn't present, the
algorithm will not return values that cover the requested range.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[vippstar]

On Jul 13, 5:04 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-07-13 09:17:51 -0400, vipps...@gmail. com said:

On Jul 13, 2:35 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-07-12 22:59:09 -0400, "joe" <j...@iamnotath ome.org.invalid said:

>"Richard Heathfield" <[e-mail].i nvalidwrote:

>>The Standard says that "RAND_MAX [...] expands to an integral constant
expression, the value of which is the maximum value returned by the rand
function".

>My final version:

>int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

>if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;

This last step isn't right.

<snip>
It's redundant, but not wrong.

How is it redundant? If the caller asks for a range that's larger than
this distribution can handle and this check isn't present, the
algorithm will not return values that cover the requested range.

Whether that second if is present or not, the behavior of the
algorithm is the same.

[Pete Becker]

On 2008-07-13 10:11:09 -0400, vi******@gmail. com said:

On Jul 13, 5:04 pm, Pete Becker <p...@versatile coding.comwrote :

>On 2008-07-13 09:17:51 -0400, vipps...@gmail. com said:

>>On Jul 13, 2:35 pm, Pete Becker <p...@versatile coding.comwrote :
On 2008-07-12 22:59:09 -0400, "joe" <j...@iamnotath ome.org.invalid said:

>>>>"Richard Heathfield" <[e-mail].i nvalidwrote:

>>>>>The Standard says that "RAND_MAX [...] expands to an integral constant
>expression , the value of which is the maximum value returned by the rand
>function ".

>>>>My final version:

>>>>int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

>>>>if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;

>>>This last step isn't right.
<snip>
It's redundant, but not wrong.

How is it redundant? If the caller asks for a range that's larger than
this distribution can handle and this check isn't present, the
algorithm will not return values that cover the requested range.

Whether that second if is present or not, the behavior of the
algorithm is the same.

It should produce an error. The fact that it doesn't means it's wrong,
not that it's redundant.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[vippstar]

On Jul 13, 6:48 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-07-13 10:11:09 -0400, vipps...@gmail. com said:

On Jul 13, 5:04 pm, Pete Becker <p...@versatile coding.comwrote :

On 2008-07-13 09:17:51 -0400, vipps...@gmail. com said:

>On Jul 13, 2:35 pm, Pete Becker <p...@versatile coding.comwrote :
On 2008-07-12 22:59:09 -0400, "joe" <j...@iamnotath ome.org.invalid said:

>>>"Richard Heathfield" <[e-mail].i nvalidwrote:

>>>>The Standard says that "RAND_MAX [...] expands to an integral constant
expressio n, the value of which is the maximum value returned by the rand
function" .

>>>My final version:

>>>int genrand(unsigne d range)
{ // generates random number between 0 and range-1
// range can be maximally RAND_MAX + 1
// THIS IS THE RECOMMENDED CORRECT METHOD
// (recommended by me and others :-)

>>>if (range < 2)
return 0;
if (range (RAND_MAX + 1))
range = RAND_MAX + 1;

>>This last step isn't right.
<snip>
It's redundant, but not wrong.

How is it redundant? If the caller asks for a range that's larger than
this distribution can handle and this check isn't present, the
algorithm will not return values that cover the requested range.

Whether that second if is present or not, the behavior of the
algorithm is the same.

It should produce an error. The fact that it doesn't means it's wrong,
not that it's redundant.

You're wrong.