Velocity Reviews > rand() % n Revisited

# rand() % n Revisited

Rich Fife
Guest
Posts: n/a

 10-23-2008
Quick rand() question:

I know you're not supposed to use "rand() % 1024" for instance,
because it focuses on the lower bits. However, it seems to me that
given that the argument is not a power of two (or near a power of
two), that this is not an issue. The upper bits will participate
equally in the result with the lower. Am I missing something?

Thanks!

-- Rich --

Paul Hsieh
Guest
Posts: n/a

 10-23-2008
On Oct 22, 6:04 pm, Rich Fife <(E-Mail Removed)> wrote:
> Quick rand() question:
>
> I know you're not supposed to use "rand() % 1024" for instance,
> because it focuses on the lower bits. However, it seems to me
> that given that the argument is not a power of two (or near a
> power of two), that this is not an issue. The upper bits will
> participate equally in the result with the lower. Am I missing
> something?

Yes, you are missing some mathematical analysis to back up what you
just said. If you do (rand() % 1023) on Microsoft Visual C++ or
WATCOM C/C++, 32 of the possible outputs will have an extra 3% bias no
matter how good your random number generator is. No C compiler's
rand() that I have ever seen has, by itself, a worse effect on random
output than that.

The C.L.C. FAQ about this gives extremely misleading advice on this
point and it should seriously be ignored. If you want to seriously
deal with random numbers just read my page about it:

http://www.pobox.com/~qed/random.html

I build up a *REAL* ranged random number generator with reasonable
performance characteristics, culminating in the randrange() function
that removes all the primary problems with ranged random numbers. If
you want something with pure random bit quality you can always use the
Mersenne Twister or Fortuna as a base for my generator function.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

lawrence.jones@siemens.com
Guest
Posts: n/a

 10-23-2008
Paul Hsieh <(E-Mail Removed)> wrote:
> No C compiler's
> rand() that I have ever seen has, by itself, a worse effect on random
> output than that.

Then you've never seen the truely bad BSD rand() that fostered most of
the paranoia about rand. With it, rand() % 1 generated the sequence 0,
1, 0, 1, 0, 1, ....
--
Larry Jones

This game lends itself to certain abuses. -- Calvin

Kelsey Bjarnason
Guest
Posts: n/a

 10-23-2008
On Thu, 23 Oct 2008 10:46:39 -0400, lawrence.jones wrote:

> Paul Hsieh <(E-Mail Removed)> wrote:
>> No C compiler's
>> rand() that I have ever seen has, by itself, a worse effect on random
>> output than that.

>
> Then you've never seen the truely bad BSD rand() that fostered most of
> the paranoia about rand. With it, rand() % 1 generated the sequence 0,
> 1, 0, 1, 0, 1, ....

That would be bad, as rand() % 1 should only ever produce 0.

CBFalconer
Guest
Posts: n/a

 10-23-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Paul Hsieh <(E-Mail Removed)> wrote:
>
>> No C compiler's rand() that I have ever seen has, by itself, a
>> worse effect on random output than that.

>
> Then you've never seen the truely bad BSD rand() that fostered
> most of the paranoia about rand. With it, rand() % 1 generated
> the sequence 0, 1, 0, 1, 0, 1, ....

FYI the value of "rand() % 1" is identically 0. Except it may be
considerably slower than just writing "0".

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

Phil Carmody
Guest
Posts: n/a

 10-23-2008
Keith Thompson <(E-Mail Removed)> writes:
> Kelsey Bjarnason <(E-Mail Removed)> writes:
>> On Thu, 23 Oct 2008 10:46:39 -0400, lawrence.jones wrote:
>>
>>> Paul Hsieh <(E-Mail Removed)> wrote:
>>>> No C compiler's
>>>> rand() that I have ever seen has, by itself, a worse effect on random
>>>> output than that.
>>>
>>> Then you've never seen the truely bad BSD rand() that fostered most of
>>> the paranoia about rand. With it, rand() % 1 generated the sequence 0,
>>> 1, 0, 1, 0, 1, ....

>>
>> That would be bad, as rand() % 1 should only ever produce 0.

>
> Obviously Larry is using a font that doesn't distinguish clearly
> enough between '%' and '&'. Yeah, that's it.

I had presumed that ``const int l=2;'' was the line before.

Obfuscatorially yours,
Phil
--
The fact that a believer is happier than a sceptic is no more to the
point than the fact that a drunken man is happier than a sober one.
The happiness of credulity is a cheap and dangerous quality.
-- George Bernard Shaw (1856-1950), Preface to Androcles and the Lion

Charles Richmond
Guest
Posts: n/a

 10-24-2008
CBFalconer wrote:
> (E-Mail Removed) wrote:
>> Paul Hsieh <(E-Mail Removed)> wrote:
>>
>>> No C compiler's rand() that I have ever seen has, by itself, a
>>> worse effect on random output than that.

>> Then you've never seen the truely bad BSD rand() that fostered
>> most of the paranoia about rand. With it, rand() % 1 generated
>> the sequence 0, 1, 0, 1, 0, 1, ....

>
> FYI the value of "rand() % 1" is identically 0. Except it may be
> considerably slower than just writing "0".
>

Not if your compiler has a good optimizer...

--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+

Keith Thompson
Guest
Posts: n/a

 10-24-2008
Charles Richmond <(E-Mail Removed)> writes:
> CBFalconer wrote:
>> (E-Mail Removed) wrote:
>>> Paul Hsieh <(E-Mail Removed)> wrote:
>>>
>>>> No C compiler's rand() that I have ever seen has, by itself, a
>>>> worse effect on random output than that.
>>> Then you've never seen the truely bad BSD rand() that fostered
>>> most of the paranoia about rand. With it, rand() % 1 generated
>>> the sequence 0, 1, 0, 1, 0, 1, ....

>> FYI the value of "rand() % 1" is identically 0. Except it may be
>> considerably slower than just writing "0".
>>

>
> Not if your compiler has a good optimizer...

Maybe. rand() has side effects, so a call to it can't be optimized
away, *unless* the compiler can prove that the side effects don't
affect the program's output.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

William Hughes
Guest
Posts: n/a

 10-24-2008
On Oct 22, 11:48 pm, Paul Hsieh <(E-Mail Removed)> wrote:
> On Oct 22, 6:04 pm, Rich Fife <(E-Mail Removed)> wrote:
>
> > Quick rand() question:

>
> > I know you're not supposed to use "rand() % 1024" for instance,
> > because it focuses on the lower bits. However, it seems to me
> > that given that the argument is not a power of two (or near a
> > power of two), that this is not an issue. The upper bits will
> > participate equally in the result with the lower. Am I missing
> > something?

>
> Yes, you are missing some mathematical analysis to back up what you
> just said. If you do (rand() % 1023) on Microsoft Visual C++ or
> WATCOM C/C++, 32 of the possible outputs will have an extra 3% bias no
> matter how good your random number generator is.

Well, 3% certainly meets the informal meaning of small. If your
problem
is such that you are worried about the 3% you should probably be more
worried about the fact that the rand() you are using has an output
space of only 16 bits.

> No C compiler's
> rand() that I have ever seen has, by itself, a worse effect on random
> output than that.

Then you have not seen a rand() implementation that switched parity
on each call. I understand such an implementation not only existed
but
was relatively widespread.

>
> The C.L.C. FAQ about this gives extremely misleading advice on this
> point and it should seriously be ignored.

No. Using the advice given in the C.L.C. means that you will get
reasonable
results, even if rand() implementation is poor, as long as rand()
produces
integers that are more or less uniformly distributed in 0...RAND_MAX.
If you use the "rand() % n" technique you have no such guarantee.
The bias is small. Do not confuse detectablity with importance.
(The use of "signifcance" in the term "statistical significance"
leads many people astray).

- William Hughes

Nate Eldredge
Guest
Posts: n/a

 10-24-2008
William Hughes <(E-Mail Removed)> writes:

>> No C compiler's
>> rand() that I have ever seen has, by itself, a worse effect on random
>> output than that.

>
> Then you have not seen a rand() implementation that switched parity
> on each call. I understand such an implementation not only existed
> but
> was relatively widespread.

Right you are. Here is the rand() implementation from the very
influential 4.4BSD-Lite.

#define RAND_MAX 0x7fffffff

static u_long next = 1;

int
rand()
{
return ((next = next * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
}

void
srand(seed)
u_int seed;
{
next = seed;
}

 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 OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Silverstrand Front Page News 0 09-22-2005 01:37 PM Caploc Firefox 3 12-16-2004 12:37 AM Brian Cisco 9 01-06-2004 06:02 PM Brad Tarver Cisco 0 07-09-2003 12:01 AM Brad Tarver Cisco 0 07-09-2003 12:00 AM

Advertisments