Help with a random function -- thanks...

[almurph]

Hi,


Just wondering can you help me with these pls:


Q1: What does: (random()&2147483647) / 2147483648.0) return? int.
float, double?

Q2: What is is the range of the result?

Thanks for any replies.
Al.

 

[Martin Ambuhl]

Hi,


Just wondering can you help me with these pls:


Q1: What does: (random()&2147483647) / 2147483648.0) return? int.
float, double?

Whatever type 2147483648.0 is. What does your textbook say?

Q2: What is is the range of the result?

Surely this is obvious.

 

[Bartc]

Whatever type 2147483648.0 is. What does your textbook say?


Surely this is obvious.

Only if the range of random() is obvious.

 

[user923005]

Only if the range of random() is obvious.

If we assume that the bitwise and is operating on a two's complement
machine, then it is still obvious.
Smallest value is 0 and the largest value is less than 1 (might be a
lot less than 1 if random()'s maximum is less than 2147483647).
Note that the output is very gritty (not nearly as smooth and
continuous as it could be).
If the O.P. really wants a pseudo-random floating point value between
[0 and 1) then there are much better ways to do it.

 

[Bartc]

If we assume that the bitwise and is operating on a two's complement
machine, then it is still obvious.
Smallest value is 0 and the largest value is less than 1 (might be a
lot less than 1 if random()'s maximum is less than 2147483647).

Exactly. I tried the expression using a random() function returning 0. The
range was 0.0 to 0.0.

I'm not familiar with any standard C function 'random'.

 

[Bartc]

Note that the output is very gritty (not nearly as smooth and
continuous as it could be).

Why would the output be gritty?

(Assuming the random values are equally likely between 0 and 2147483647 (and
I would divide by 2147483647).)

 

[user923005]

Why would the output be gritty?

(Assuming the random values are equally likely between 0 and 2147483647 (and
I would divide by 2147483647).)

Consider a typical 8 byte floating point implementation. If we
examine float.h we might find a definition similar to this:
#define DBL_MANT_DIG 53

Now the log base 2 of 2147483648 is 31.

That means that there are titanic, spastic jumps between each value
formed by the divisions.

A proper floating point pseudo random number generator will populate
the bits evenly.

IOW,
0 / 2147483648.0 = 0
1 / 2147483648.0 = 0.0000000004656612873077392578125
2 / 2147483648.0 = 0.000000000931322574615478515625

There are a stupendous number of distinct values between each of these
numbers.

In summary, this is a really awful way to make a floating point prng
that returns values between [0 and 1).
There are some types of uses for which this is sufficient, but since
there are excellent generators available for nothing, why reinvent a
lopsided, triangular wheel when Pirellis are given away for free?

If we examine only the mantissa portion, we can easily see that with
52 mantissa bits (for instance) there are 2^53-1 different ways to
populate these bits. With a 31 bit source, there are only 2^32-1
distinct values to stuff into those slots.
Written out, that means that 9007199254740991 values are being
populated with only 4294967295 values. That ratio is:
4.7683715809210275047704353702546e-7
so about 1 out of 2,097,152 values are ever actually represented.

Print one item, skip 2 million. Print one item, skip 2 million.
There is no way to hit the values in between.

That's what I call gritty.

 

[jameskuyper]

user923005 wrote:
....

If we examine only the mantissa portion, we can easily see that with
52 mantissa bits (for instance) there are 2^53-1 different ways to
populate these bits. With a 31 bit source, there are only 2^32-1
distinct values to stuff into those slots.
Written out, that means that 9007199254740991 values are being
populated with only 4294967295 values. That ratio is:
4.7683715809210275047704353702546e-7
so about 1 out of 2,097,152 values are ever actually represented.

Print one item, skip 2 million. Print one item, skip 2 million.
There is no way to hit the values in between.

That's what I call gritty.

So long as you're using only a single 31-bit pseudo-random number to
determine which double-precision number you're going to generate, with
a uniform distribution, that's about as smooth as you can get. If you
really need a more even distribution, you'll have to do something like
using two 31-bit numbers to determine the results, rather than just
one.

 

[user923005]

user923005 wrote:

...




So long as you're using only a single 31-bit pseudo-random number to
determine which double-precision number you're going to generate, with
a uniform distribution, that's about as smooth as you can get. If you
really need a more even distribution, you'll have to do something like
using two 31-bit numbers to determine the results, rather than just
one.

Typically, good prngs have much larger internal storage. The Mersenne
Twister uses 624 unsigned long values to hold the current state:

/* Period parameters */
#define N 624
{snip}
static unsigned long mt[N]; /* the array for the state vector */

George Marsaglia's recent submission of the Kiss PRNG has 5 64 bit
entries:

unsigned long long x,
c,
y,
z,
t;

A smaller *seed* is possible, but the internal state vector has to be
bigger than 32 bits if a floating point PRNG is to be worth more than
the powder to blow it up with.

 

[user923005]

user923005 wrote:

...




So long as you're using only a single 31-bit pseudo-random number to
determine which double-precision number you're going to generate, with
a uniform distribution, that's about as smooth as you can get. If you
really need a more even distribution, you'll have to do something like
using two 31-bit numbers to determine the results, rather than just
one.

Another alternative is simply to call it twice.

 

[jameskuyper]

Typically, good prngs have much larger internal storage.

The size of the internal storage doesn't matter. Any method that
determines a consistent unique floating point value for each randomly
generated integer value can only determine a number of different
floating point numbers that is less than or equal to the number of
different integer values that can be generated. The internal state of
the prng is irrelevant to that conclusion. Only if the internal state
itself were used to determine the floating point number would it's
size be relevant.

 

[jameskuyper]

Another alternative is simply to call it twice.

Well, yes - that's how you get the two 31-bit numbers. That was
implicit in the context.

 

[Bartc]

user923005 wrote:


So would I.

And to see what happens in the real world with cash on the line when you
have a
gritty PRNG's
http://itmanagement.earthweb.com/entdev/article.php/616221

Interesting article but it didn't seem to say anything about gritty PRNGs.

From what I could understand of the poker games, given the first 5 cards of
a deck, and the shuffling algorithm, and some guesses as to what PRNG is
being used, it might be possible to find out which seed would generate the
same 5 cards, and therefore to predict the rest of the deck.

I think if the code is openly using the random generator in a specific
Pascal, and is openly seeded with the time-of-day for each shuffle, and
using simplistic shuffling methods, then that's asking for trouble.

Just use a dozen or so different pseudo random generators, it doesn't matter
how bad or inept they are, it might even help to build grittiness into some
of them. Perhaps one of them could just be a feed from the The Times
newspaper text from last week.

Xor half-a-dozen of these together to form the main random source. Use
another to perform the shuffle N times. Use another to decide whether to use
these random numbers, or try a few more times. And perhaps another to decide
which of the generators to use for the next round.

(in case anyone takes this seriously)

 

[user923005]

Well, yes - that's how you get the two 31-bit numbers. That was
implicit in the context.

I misinterpreted the statement as "two internal numbers" ... for
storage.
IOW, a 64 bit or more state vector.

 

[user923005]

The size of the internal storage doesn't matter. Any method that
determines a consistent unique floating point value for each randomly
generated integer value can only determine a number of different
floating point numbers that is less than or equal to the number of
different integer values that can be generated. The internal state of
the prng is irrelevant to that conclusion. Only if the internal state
itself were used to determine the floating point number would it's
size be relevant.

Consider a 1 bit internal state (only one bit is stored between
invocations). This device has a period of 2.
Generally speaking, the bit-size of the internal state vector limits
the maximum period of the device.
That's why the Mersenne twister has such a huge state vector {the
Mersenne twister has a period of 2^19937 - 1 by using the properties
of a Mersenne prime}.

 

[Phil Carmody]

We're straying somewhat from C's realm and risking an
incursion into comp.programming territory, but it's worth
noting that splicing two successive values of a PRNG into one
eventual output means that PRNG's two-dimensional "randomness"
limits that of the outputs. That is, the output depends not
on the statistical properties of x1,x2,x3,... but on those of
the sequence of points (x1,x2),(x3,x4),... Randomness usually
decreases with increasing dimension.

Only with naive PRNGs. If the internal state of the PRNG is
S bits, and you pull R bits out with the first call, then
you evidently don't have more than S-R bits of entropy left
for the second call. LC/MC/LFSR and other small generators do
indeed suffer from this problem. Given that the C standard
promises so little from its PRNG, I don't recommend their use
for anything apart from the most trivial toy programs.

One countermeasure is to use (x1,y1),(x2,y2),... where the
x's and y's are obtained from different and unrelated PRNG's,
ideally with dissimilar period lengths.

That would work, but you'd probably need some sophistication to
prove that the PRNGs were unrelated.

For simplicity, I always like lagged Fibs. Consecutive terms
may came from the same source, but can be made as weakly
correlated as you want by chosing the lengths correctly.
(HOwever, then you must take care with initialisation.)

... and at this point my prowess in matters mathematical
finds itself unable to dig much deeper into the subject. But
the lesson from those whose prowess exceeds mine is: You can't
get a "good" stream of random M*N-bit numbers by just pasting
together M successive values from an N-bit generator.

A workable generalisation. If the state of the generator is only
N bits, then it'd definitely true.

Phil

 

[Nate Eldredge]

user923005 wrote:
...

So long as you're using only a single 31-bit pseudo-random number to
determine which double-precision number you're going to generate, with
a uniform distribution, that's about as smooth as you can get. If you
really need a more even distribution, you'll have to do something like
using two 31-bit numbers to determine the results, rather than just
one.

That's still not quite perfect though.

Supposing that RAND_MAX is 2^31-1, if we did:

double random_double(void) {
unsigned long long r = ((unsigned long long)rand()) << 31 + rand();
return r / (2ULL << 62);
}

Assuming a standard IEEE-754 `double' with 53-bit mantissa and 11-bit
signed exponent, it can, for instance, represent the number 2^(-100)
exactly, so an ideal random number generator should have an appropriate
positive probability of returning that value. Ours does not; it will
never return any of the `double' values which are between 0 and 2^(-62).

A better approach might be something equivalent to the following sketch:

double random_double(void) {
unsigned long long mantissa = 0;
int exponent = 0;
int i;
while (random_bit() == 0) exponent--;
mantissa = 1;
for (i = 1; i < 53; i++) {
mantissa <<= 1;
mantissa += random_bit();
exponent--;
}
return mantissa * pow(2.0, exponent);
}