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

 
 
jadill33@gmail.com
Guest
Posts: n/a
 
      08-07-2013
On Wednesday, August 7, 2013 5:07:44 AM UTC-4, Guillaume Dargaud wrote:
> Hello all,
>
> any idea on writing a macro to generate a pseudo-random number using all 64
>
> bits of a unsigned long long ?
>
>
>
> The problem is that RAND_MAX varies greatly between compilers: I have
>
> examples where it's 0x7FFF, 0x7FFFFFFF and 0xFFFFFFFF but no 64 bit version.
>
>
>
> I'd like to stay with the old rand() of standard C.
>
>
>
> For instance one solution when RAND_MAX is 0x7FFF is the following:
>
> #define RAND64 ( (rand()<<60ULL) | (rand()<<45ULL) | (rand()<<30ULL) |
>
> (rand()<<15ULL) | (rand()<<0ULL))
>
>
>
> But it gives me
>
> Warning: Conversion from 'unsigned __int64' to 'int' might lose data.
>
> Which kind of surprises me but maybe I'm using it wrong.
>
>
>
> Anybody can think of a more generic solution independent of RAND_MAX ?


Here's an excerpt of what I use for type 'int'. It essentially fills
in each byte with a random number, since 'RAND_MAX' is likely to be
larger than UCHAR_MAX. There sample has some extra constraint
checking ('c_return_value_if_fail' and 'c_unexpected'), and 'C_ABS'
is a macro for absolute value. You should be able to apply the same
principle to an 'unsigned long long'. If sequential random samples
from 'rand()' were truly independent, I think it should be a viable
way to construct a wider random integer value.

\code
/*!
* \brief The maximum number of \c rand samples \c c_random may use
* before exceeding the retry count.
*
* One can more easily test the behavior of the retry count feature
* by reducing the number of samples to 1.
*/
#define GC_MAXIMUM_RAND_SAMPLES 10

unsigned int c_time_seed( void )
{
time_t now;
unsigned char* p = (unsigned char*)&now;
unsigned int seed = 0;
size_t byte_itr;

now = time( NULL );

for ( byte_itr = 0; byte_itr < sizeof (time_t); ++byte_itr ) {
seed = seed * ( UCHAR_MAX + 2U ) + p[byte_itr];
}

return seed;
}

int c_random( int n )
{
int limit;
int r;
int bias_retry_count;

c_return_value_if_fail( 0 <= n && n <= RAND_MAX, rand() );

limit = RAND_MAX - RAND_MAX % n;

bias_retry_count = GC_MAXIMUM_RAND_SAMPLES;
do {
r = rand();
} while ( bias_retry_count-- > 0 && r >= limit );

c_unexpected( bias_retry_count < 0 );

return r % n;
}

int c_rand_int( void )
{
int rnd = 0;
size_t n;
unsigned char* ucp;

n = sizeof (int);
ucp = (unsigned char*)&rnd;

/* Assemble a random integer of width 'int' by filling each byte
with a random byte from rand(). */
while ( n-- != 0 ) {
*ucp++ = (unsigned char)c_random( UCHAR_MAX + 1 );
}

/*
* If the 'int' representation is two's complement, assign INT_MIN
* to zero to prevent integer overflow when taking the absolute
* value. The assignment also happens to make the distribution
* more uniform.
*/
#if ( INT_MIN < -INT_MAX )
if ( rnd == INT_MIN ) {
rnd = 0;
}
#endif

return C_ABS( rnd );
}
\endcode

Whether this is any better or (likely) worse than other random number
generators is unknown to me.

Best regards,
John D.

(First time posting under new google groups, I guess I'll see how bad
it is when I post it).
 
Reply With Quote
 
 
 
 
Tim Rentsch
Guest
Posts: n/a
 
      08-08-2013
http://www.velocityreviews.com/forums/(E-Mail Removed) writes:

> On Wednesday, August 7, 2013 5:07:44 AM UTC-4, Guillaume Dargaud wrote:
>> Hello all,
>> any idea on writing a macro to generate a pseudo-random number using all 64
>> bits of a unsigned long long ? [snip]
>> Anybody can think of a more generic solution independent of RAND_MAX ?

>
> Here's an excerpt of what I use for type 'int'. It essentially
> fills in each byte with a random number, since 'RAND_MAX' is
> likely to be larger than UCHAR_MAX. [and takes the absolute
> value to produce a non-negative number] [snip elaboration]


There are two things wrong with this approach:

1. It can generate trap representations. Note that trap
representations may exist even in implementations that use
twos complement and have no padding bits.

2. The possible existence of multiple representations for a
single value make it very difficult to produce a truly
uniform distribution.

A better approach is to generate an appropriate value directly in
unsigned char units, eg

#include <limits.h>

#define INT_BIT /* .. number of bits in INT_MAX .. */
/* This can be done directly from INT_MAX using
the well known IMAX_BITS macro */

int
uniform_nonnegative_int(){
unsigned mask_shift = (CHAR_BIT-1) - (INT_BIT-1) % CHAR_BIT;
unsigned mask = (unsigned char) -1 >> mask_shift;
int r = mask & (unsigned char) rand();
int i = (INT_BIT-1) / CHAR_BIT;

while( i-- > 0 ) r = r << CHAR_BIT + (unsigned char) rand();
return r;
}

Disclaimer: typed in, not compiled.
 
Reply With Quote
 
 
 
 
Phil Carmody
Guest
Posts: n/a
 
      08-13-2013
Tim Rentsch <(E-Mail Removed)> writes:
> (E-Mail Removed) writes:

....
> A better approach is to generate an appropriate value directly in
> unsigned char units, eg
>
> #include <limits.h>
>
> #define INT_BIT /* .. number of bits in INT_MAX .. */
> /* This can be done directly from INT_MAX using
> the well known IMAX_BITS macro */
>
> int
> uniform_nonnegative_int(){
> unsigned mask_shift = (CHAR_BIT-1) - (INT_BIT-1) % CHAR_BIT;
> unsigned mask = (unsigned char) -1 >> mask_shift;
> int r = mask & (unsigned char) rand();
> int i = (INT_BIT-1) / CHAR_BIT;
>
> while( i-- > 0 ) r = r << CHAR_BIT + (unsigned char) rand();


Conventional wisdom, from decades of experience, says that the lower
bits tend to be at least as crappy as the upper bits, so shifting them
out is better than masking them in. I would also presume the "planes"
property (relations between subseqent terms) is less likely to kick in
too, but don't have the mathematical teeth to prove such a claim.

Phil
--
If "law-abiding citizens have nothing to fear" from privacy-invading
technologies and policies, then law-abiding governments should have
nothing to fear from whistleblowers.
 
Reply With Quote
 
Jorgen Grahn
Guest
Posts: n/a
 
      08-13-2013
On Tue, 2013-08-13, Phil Carmody wrote:
....
> Conventional wisdom, from decades of experience, says that the lower
> bits tend to be at least as crappy as the upper bits, so shifting them
> out is better than masking them in.


Decades of experience, or decades-old experience?

If you're saying you have a rand() with bad randomness in the low bits
/today/, I'm interested to learn which implementation that is. I've
asked a few times, but as far as I can recall noone has claimed to
have seen one since the 1990s or so.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      08-14-2013
On Tuesday, 13 August 2013 22:34:05 UTC+3, Jorgen Grahn wrote:
> On Tue, 2013-08-13, Phil Carmody wrote:
> ...
> > Conventional wisdom, from decades of experience, says that the lower
> > bits tend to be at least as crappy as the upper bits, so shifting them
> > out is better than masking them in.

>
> Decades of experience, or decades-old experience?
>
> If you're saying you have a rand() with bad randomness in the low bits
> /today/, I'm interested to learn which implementation that is. I've
> asked a few times, but as far as I can recall noone has claimed to
> have seen one since the 1990s or so.


What implementation has good rand()? Usually it is not good for anything
serious. Even portable games can not use it because its badness is not
portable (you get different artifacts of rand() weaknesses on different
platforms). C++11 standard library <random> has useful generators.
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      08-14-2013
On Tue, 13 Aug 2013 19:34:05 +0000, Jorgen Grahn wrote:

> If you're saying you have a rand() with bad randomness in the low bits
> /today/, I'm interested to learn which implementation that is. I've asked
> a few times, but as far as I can recall noone has claimed to have seen one
> since the 1990s or so.


The MSVCRT rand() in Visual Studio 10 uses an LCG with a 32-bit state, and
uses bits 16-31 of the state as the result, so the LSB will have a period
of at most 2^17.

Whether or not that's "bad" is subjective, but the lower bits will have
shorter periods than the higher bits.

If by "bad" you mean "returns the low bits of an LCG instead of the high
bits", then I haven't seen that since around 1993-94 (and the compiler
wasn't necessarily the latest version).

 
Reply With Quote
 
Geoff
Guest
Posts: n/a
 
      08-14-2013
On Wed, 14 Aug 2013 07:30:46 +0100, Nobody <(E-Mail Removed)> wrote:

>On Tue, 13 Aug 2013 19:34:05 +0000, Jorgen Grahn wrote:
>
>> If you're saying you have a rand() with bad randomness in the low bits
>> /today/, I'm interested to learn which implementation that is. I've asked
>> a few times, but as far as I can recall noone has claimed to have seen one
>> since the 1990s or so.

>
>The MSVCRT rand() in Visual Studio 10 uses an LCG with a 32-bit state, and
>uses bits 16-31 of the state as the result, so the LSB will have a period
>of at most 2^17.
>
>Whether or not that's "bad" is subjective, but the lower bits will have
>shorter periods than the higher bits.
>
>If by "bad" you mean "returns the low bits of an LCG instead of the high
>bits", then I haven't seen that since around 1993-94 (and the compiler
>wasn't necessarily the latest version).


In Visual Studio versions 2005 and later, rand_s() calls
RtlGenRandom() which is available on Windows XP and later systems. It
is a cryptographically secure (whatever that means these days) random
number generator that generates a random number between 0 and UINT_MAX
and doesn't depend on srand().
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      08-15-2013
On Wed, 14 Aug 2013 14:34:38 -0700, Geoff wrote:

> In Visual Studio versions 2005 and later, rand_s() calls
> RtlGenRandom() which is available on Windows XP and later systems. It
> is a cryptographically secure (whatever that means these days) random
> number generator that generates a random number between 0 and UINT_MAX
> and doesn't depend on srand().


In fact, it doesn't seem to be able to be seeded at all (and it isn't
clear whether it's actually pseudo-random or random), which makes it
effectively useless for many applications requiring pseudo-random numbers.

 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      08-15-2013
Jorgen Grahn <(E-Mail Removed)> writes:

> On Tue, 2013-08-13, Phil Carmody wrote:
> ...
> > Conventional wisdom, from decades of experience, says that the lower
> > bits tend to be at least as crappy as the upper bits, so shifting them
> > out is better than masking them in.

>
> Decades of experience, or decades-old experience?


The former, and fortunately enough of a memory for the latter too.

> If you're saying you have a rand() with bad randomness in the low bits
> /today/, I'm interested to learn which implementation that is. I've
> asked a few times, but as far as I can recall noone has claimed to
> have seen one since the 1990s or so.


Well, lets try the system I'm typing on right now:
gcc 4.6/eglibc6 2.15/linux 3.5/x86_64
but I'm 100% sure I could reproduce these on systems which differ
from that configuration in every possible way.


dieharder on 8*268435456 bits of the 1u<<0 bit, packed into u8s:

#================================================= ============================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#================================================= ============================#
diehard_operm5| 0| 1000000| 100|0.00000000| FAILED
diehard_rank_6x8| 0| 100000| 100|0.00000000| FAILED
diehard_oqso| 0| 2097152| 100|0.00000000| FAILED
diehard_count_1s_byt| 0| 256000| 100|0.00000000| FAILED
diehard_parking_lot| 0| 12000| 100|0.00000000| FAILED
diehard_2dsphere| 2| 8000| 100|0.00000000| FAILED
diehard_3dsphere| 3| 4000| 100|0.00000000| FAILED
diehard_squeeze| 0| 100000| 100|0.00000000| FAILED
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
rgb_bitdist| 3| 100000| 100|0.00001119| WEAK
rgb_bitdist| 4| 100000| 100|0.00000000| FAILED
rgb_bitdist| 5| 100000| 100|0.00000000| FAILED
rgb_bitdist| 6| 100000| 100|0.00000000| FAILED
rgb_bitdist| 7| 100000| 100|0.00000000| FAILED
rgb_bitdist| 8| 100000| 100|0.00007518| WEAK
....

dieharder on 8*268435456 bits of the 1u<<14 bit, packed into u8s:

#================================================= ============================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#================================================= ============================#
diehard_operm5| 0| 1000000| 100|0.54507141| PASSED
diehard_rank_6x8| 0| 100000| 100|0.82359872| PASSED
diehard_oqso| 0| 2097152| 100|0.19046187| PASSED
diehard_count_1s_byt| 0| 256000| 100|0.67168735| PASSED
diehard_parking_lot| 0| 12000| 100|0.41559726| PASSED
diehard_2dsphere| 2| 8000| 100|0.18176928| PASSED
diehard_3dsphere| 3| 4000| 100|0.00056702| WEAK
diehard_squeeze| 0| 100000| 100|0.40881629| PASSED
marsaglia_tsang_gcd| 0| 10000000| 100|0.00004519| WEAK
rgb_bitdist| 3| 100000| 100|0.91896269| PASSED
rgb_bitdist| 4| 100000| 100|0.19499995| PASSED
rgb_bitdist| 5| 100000| 100|0.08335413| PASSED
rgb_bitdist| 6| 100000| 100|0.56964832| PASSED
rgb_bitdist| 7| 100000| 100|0.98227556| PASSED
rgb_bitdist| 8| 100000| 100|0.26112239| PASSED
....


People I know claim to see weak default PRNGs all the time, I have no
idea where your 1990s claim comes from. You seriously need to reevaluate
your presumptions in this direction.

Phil
--
If "law-abiding citizens have nothing to fear" from privacy-invading
technologies and policies, then law-abiding governments should have
nothing to fear from whistleblowers.
 
Reply With Quote
 
Jorgen Grahn
Guest
Posts: n/a
 
      08-17-2013
On Wed, 2013-08-14, Nobody wrote:
> On Tue, 13 Aug 2013 19:34:05 +0000, Jorgen Grahn wrote:
>
>> If you're saying you have a rand() with bad randomness in the low bits
>> /today/, I'm interested to learn which implementation that is. I've asked
>> a few times, but as far as I can recall noone has claimed to have seen one
>> since the 1990s or so.

>
> The MSVCRT rand() in Visual Studio 10 uses an LCG with a 32-bit state, and
> uses bits 16-31 of the state as the result, so the LSB will have a period
> of at most 2^17.
>
> Whether or not that's "bad" is subjective, but the lower bits will have
> shorter periods than the higher bits.
>
> If by "bad" you mean "returns the low bits of an LCG instead of the high
> bits", then I haven't seen that since around 1993-94 (and the compiler
> wasn't necessarily the latest version).


I was looking more generally for a rand() where 'rand() % N' (adjusted
for the case when RAND_MAX % N != 0) is not the best way to use it to
generate a random number between 0 and N-1.

So yes, your VS10 rand() qualifies.

/Jorgen
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
 
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 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
is this prog stdc? Heinrich Pumpernickel C Programming 7 09-10-2007 05:31 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