Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: Random 64 bit number in stdc

Reply
Thread Tools

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
 
Reply With Quote
 
 
 
 
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
> bits would be adequate.


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
would be advantageous -- when reading /dev/random, for example,
it would be undesirable to consume more bits than absolutely
necessary.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
Öö 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).

 
Reply With Quote
 
James Dow Allen
Guest
Posts: n/a
 
      08-21-2013
Öö Tiib <(E-Mail Removed)> might have writ, in news:70280474-0cab-45cd-89bb-e1e4c5427111
@googlegroups.com:

> 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
 
Reply With Quote
 
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
> @googlegroups.com:
>
>> 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
 
Reply With Quote
 
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

 
Reply With Quote
 
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?


In this thread about (pseudo-) random number generation,
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/Gaussian_quadrature

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

--
Eric Sosman
(E-Mail Removed)d
 
Reply With Quote
 
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?

>
> In this thread about (pseudo-) random number generation,
> 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.
Instead I enumerated the answer to the similar problem, where instead of
2147483648 values, we have only ten values. This did not seem like an
abstruse analogy to understand, but YMMV.

Get it?

James
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Random 64 bit number in stdc jadill33@gmail.com C Programming 59 09-02-2013 07:41 PM
Re: Random 64 bit number in stdc Ben Bacarisse C Programming 2 08-07-2013 11:49 AM
32-bit Number * 32-bit Number = 64-bit result Jeff.M Javascript 6 05-04-2009 09:21 PM
Re: stdc++ fstream file permission Avner C++ 0 10-15-2005 05:34 AM
stdc++ fstream file permission Avner C++ 1 10-15-2005 03:29 AM



Advertisments