Velocity Reviews > Re: Random 64 bit number in stdc

# Re: Random 64 bit number in stdc

James Dow Allen
Guest
Posts: n/a

 08-20-2013
Eric Sosman <(E-Mail Removed)> might have writ, in
news:kutrh1\$c7a\$(E-Mail Removed):

> ...
> msrand_t divisor, value;
> divisor = (MSRANDMAX - MSRANDMIN + 1) / limit;

Eric, am I correct that, typically, msrand_t will be uint32_t
but for the code to work MSRANDMAX will be only 0x7fffffff ?

In practice I usually do such to make arithmetic easier,
but for my "offical" random library, I (masochistically?)
use 32-bit generators.

James

Eric Sosman
Guest
Posts: n/a

 08-20-2013
On 8/19/2013 10:15 PM, James Dow Allen wrote:
> On Tuesday, August 20, 2013 2:26:24 AM UTC+7, Eric Sosman wrote:
>
>>> Seven lines altogether, even without bit conservation,

>
>> ...
>> while ( (value = (msrand() - MSRANDMIN) / divisor) >= limit )
>> ;

>
> I do NOT quibble with your fine code, but just seek to clarify
> my "7 lines": In my older age, I'll often use {} when ;
> could suffice. (Two of my 7 were together only "do {} ".
> Similarly, I also spend two lines for the "if (range > OTHER) {}"
> that has to be added.
>
> But much more importantly, your code will spend 31(?) random
> bits to pick a value in 0...14 while (slightly less than) 4

As I mentioned, the underlying PRNG is different from
yours. (It's Park & Miller's "Minimal Standard Random Number
Generator," a congruential algorithm with prime modulus.)
Each call to msrand() yields a result in the range 1 through
0x7fffffE, that is, just a smidgen less than 31 bits' worth.

I've never given any thought to economizing bit use with
this generator. It would certainly complicate things -- that
leftover 0.9999999986564 of a bit would be awkward in the
extreme! There certainly are settings, though, were parsimony
it would be undesirable to consume more bits than absolutely
necessary.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 08-20-2013
On 8/20/2013 12:52 AM, James Dow Allen wrote:
> Eric Sosman <(E-Mail Removed)> might have writ, in
> news:kutrh1\$c7a\$(E-Mail Removed):
>
>> ...
>> msrand_t divisor, value;
>> divisor = (MSRANDMAX - MSRANDMIN + 1) / limit;

>
> Eric, am I correct that, typically, msrand_t will be uint32_t
> but for the code to work MSRANDMAX will be only 0x7fffffff ?

#define MSRANDMIN 1 /* smallest value ever produced */
#define MSRANDMAX 2147483646 /* largest value (2**31 - 2) */

/* Define a signed integral type which can express all the generated
* values, along with negative quantities as low as -47664652 which
* may appear as intermediate values in the computations.
*/
#if (INT_MIN <= -47664652 && INT_MAX >= MSRANDMAX)
typedef int msrand_t;
#elif (LONG_MIN <= -47664652 && LONG_MAX >= MSRANDMAX)
typedef long msrand_t;
#else
/* Shouldn't happen */
# error "No suitable integral type for msrand_t exists!"
#endif

In hindsight, using a signed type for msrand_t was a blunder
on my part. The generator uses negative values internally, but
I shouldn't have let that dictate the interface. Nowadays I
guess uint_least31_t (!) would be a good choice -- but the choice
was made in the days before C99.

--
Eric Sosman
(E-Mail Removed)d

Öö Tiib
Guest
Posts: n/a

 08-21-2013
On Monday, 19 August 2013 16:38:37 UTC+3, James Dow Allen wrote:
> On Monday, August 19, 2013 8:19:56 PM UTC+7, Eric Sosman wrote:
> > On 8/19/2013 12:19 AM, James Dow Allen wrote:
> > > void rand_seed(int seed);

> >
> > That's not much entropy to seed a generator with lots
> > of internal state.

>
> Answered in my previous post, more or less. Marsaglia's
> or MTwister's numbers are very "random" just always one
> of the same (up to 4 billion different) random sequences. ::whack::
> If someone points me to a good write-up for seeding Marsaglia
> *without worry that pathological case will degrade the PRNG*,
> I will support it.
>
> > > /* Return random uniform 0 < x < 1 */
> > > double rand_prob(void);

> > That's peculiar: [0,1) is what I think most people expect.

>
> I want the mean value to be 0.5 exactly. (And I like symmetry.)
> Anyway, the measure of (p==0 exactly) event would be small anyway
> (2^-31).

That might be very useful for cases when we want a coin flipping
algorithm that has one coin from 2147483648 to stand on edge.
People need such thing rarely and more often they want p<0.5 and
p>=0.5 to have exactly equal probability (also sort of symmetry).

James Dow Allen
Guest
Posts: n/a

 08-21-2013
Öö Tiib <(E-Mail Removed)> might have writ, in news:70280474-0cab-45cd-89bb-e1e4c5427111

> On Monday, 19 August 2013 16:38:37 UTC+3, James Dow Allen wrote:
>> I want the mean value to be 0.5 exactly. (And I like symmetry.)
>> Anyway, the measure of (p==0 exactly) event would be small anyway
>> (2^-31).

>
> That might be very useful for cases when we want a coin flipping
> algorithm that has one coin from 2147483648 to stand on edge.
> People need such thing rarely and more often they want p<0.5 and
> p>=0.5 to have exactly equal probability (also sort of symmetry).

FWIW, my code doesn't produce 0.5 exactly, in addition to not producing
0 or 1 exactly. p < 0.5 and p > 0.5 do have equal probabilities regardless
of whether or where you place the "or equal."

What is the best way to position, say, ten samples evenly in [0,1]? I think
{0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95}
is an appropriate answer. Frankly I cannot imagine why anyone would
disagree with this!

James

Eric Sosman
Guest
Posts: n/a

 08-21-2013
On 8/21/2013 7:35 AM, James Dow Allen wrote:
> Öö Tiib <(E-Mail Removed)> might have writ, in news:70280474-0cab-45cd-89bb-e1e4c5427111
>
>> On Monday, 19 August 2013 16:38:37 UTC+3, James Dow Allen wrote:
>>> I want the mean value to be 0.5 exactly. (And I like symmetry.)
>>> Anyway, the measure of (p==0 exactly) event would be small anyway
>>> (2^-31).

>>
>> That might be very useful for cases when we want a coin flipping
>> algorithm that has one coin from 2147483648 to stand on edge.
>> People need such thing rarely and more often they want p<0.5 and
>> p>=0.5 to have exactly equal probability (also sort of symmetry).

>
> FWIW, my code doesn't produce 0.5 exactly, in addition to not producing
> 0 or 1 exactly. p < 0.5 and p > 0.5 do have equal probabilities regardless
> of whether or where you place the "or equal."
>
> What is the best way to position, say, ten samples evenly in [0,1]? I think
> {0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95}
> is an appropriate answer. Frankly I cannot imagine why anyone would
> disagree with this!

Looks suitably random, too.

--
Eric Sosman
(E-Mail Removed)d

James Dow Allen
Guest
Posts: n/a

 08-21-2013
Eric Sosman <(E-Mail Removed)> might have writ, in
news:kv2btm\$ea7\$(E-Mail Removed):
> Looks suitably random, too.

I'm curious what this means. Surely you don't misunderstand the context?

James

Eric Sosman
Guest
Posts: n/a

 08-21-2013
On 8/21/2013 9:08 AM, James Dow Allen wrote:
> Eric Sosman <(E-Mail Removed)> might have writ, in
> news:kv2btm\$ea7\$(E-Mail Removed):
>> Looks suitably random, too.

>
> I'm curious what this means. Surely you don't misunderstand the context?

you wrote

>>> What is the best way to position, say, ten samples evenly in [0,1]?

I think
>>> {0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95}
>>> is an appropriate answer. Frankly I cannot imagine why anyone would
>>> disagree with this!

Frankly, I cannot imagine why anyone would offer this collection
as a "random" sample.

Besides which, it is obvious that the *right* ten values to
use are

0.013047-
0.067468+
0.160295+
0.283302+
0.425563-
0.574437+
0.716698-
0.839705-
0.932532-
0.986953+

.... and this should be so transparently clear to even the feeblest
intellect that I cannot imagine why anyone would disagree!

http://en.wikipedia.org/wiki/Legendr...re_polynomials

--
Eric Sosman
(E-Mail Removed)d

James Dow Allen
Guest
Posts: n/a

 08-21-2013
Eric Sosman <(E-Mail Removed)> might have writ, in
news:kv2hlq\$d26\$(E-Mail Removed):

> On 8/21/2013 9:08 AM, James Dow Allen wrote:
>> Eric Sosman <(E-Mail Removed)> might have writ, in
>> news:kv2btm\$ea7\$(E-Mail Removed):
>>> Looks suitably random, too.

>>
>> I'm curious what this means. Surely you don't misunderstand the
>> context?

>
> you wrote
>
> >>> What is the best way to position, say, ten samples evenly in
> >>> [0,1]?

What does "evenly" mean?

> >>> I think
> >>> {0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95}
> >>> is an appropriate answer. Frankly I cannot imagine why anyone
> >>> would disagree with this!

>
> Frankly, I cannot imagine why anyone would offer this collection
> as a "random" sample.

Until now I'd never thought you were stupid. Unless yours is an
elaborate joke, apparently the feeling wasn't reciprocated.

Pay attention:

The rand_prob() we are discussing always returns one of 2,147,483,648
different values. AFAIK essentially all such routines function
similarly: which of those 2147483648 values is returned on a given call
is random; however the set of 2147483648 possibilities is fixed.

To understand rand_prob() we want to know about that set of 2147483648
distinct values. But that is a large number of values to enumerate.
2147483648 values, we have only ten values. This did not seem like an
abstruse analogy to understand, but YMMV.

Get it?

James