From: Pete Becker on
kevin.hall(a) wrote:
>>Which C library is "the C library"?
> Ok, you're right here. What I should have said to be more clear is
> "Many implementations of the C library use 'simple' PNRGs that are
> notorious for this behavior.

What you've said is quite clear. Your basis for saying it is not.

Which simple implementations are notorious for this behavior? Which C
libraries use these simple implementations?

> In particular, many older libraries use
> linear congruential generators which are known to display this
> behavior".

Which libraries are those, and which ones are still in use?


Pete Becker
Dinkumware, Ltd. (

[ See for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: kevin.hall on
> You must qualify your assertion to modulo a power of 2. Those are
> the only ones where the high order bits have no contribution.

No, the assertion is still true. You are right that modulos of numbers
that are not a power of two do have all bits contribute. But they do
not all contribute equally. This is easily demonstrated:

Take the following extreme example. The highest bit is random. All
other bits are non-random. The nth random number is:

Rn = n + <random bit>*(1<<30)

Then we choose our modulo to be something close to a power of two. Say
8193. Here's an example output:

1073741825 => 17 (after mod 8193)
1073741826 => 18
3 => 3
4 => 4
1073741829 => 21
1073741830 => 22
1073741831 => 23
8 => 8
1073741833 => 25
1073741834 => 26
11 => 11
12 => 12
13 => 13
14 => 14
1073741839 => 31
16 => 16
1073741841 => 33
18 => 18
1073741843 => 35
1073741844 => 36
21 => 21
1073741846 => 38
1073741847 => 39
24 => 24
25 => 25
26 => 26
1073741851 => 43
1073741852 => 44
1073741853 => 45
1073741854 => 46
1073741855 => 47

Not very random! (If you keep generating more numbers, you'll see a
definite linear pattern). Anyway, I know this is an extreme example,
but it does illustrate a point. In a modulo -- even with a number
that's not a power of two -- the lower bits have a greater significance.

[ See for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Carlos Moreno on
kanze wrote:

> Still, if you have an application where you must have a certain
> quality generator, you have to provide your own; the C++
> standard doesn't give any guarantee.

I don't mean to jump in sounding like a suck-up (:-)), but I do
believe this is really the most relevant and most precise aspect
mentioned so far in the thread.

My initial take was based on the premise that rand() was to be
used, and that that part was not necessarily an option. Under
that premise, my take is that using modulo *could* introduce
a particular problem in some situations, whereas division does
not introduce that problem, or any other obvious problem (notice
that there is emphasis on whether the operation -- modulo or
division -- *introduces* an additional problem, in addition to
any problems already present in the given PRNG). For that
reason, I defend the idea of choosing division up front, without
asking too many questions (in that situation, of course).

Of course, I can't remember the last time I used rand(), or
even the rand48 family :-)



[ See for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Martin Eisenberg on
kevin.hall(a) wrote:

> I use the mersenne-twister for anything that really matters in my
> work. Though I believe the MT is less susceptible to having lower
> order bits be less random, I haven't yet seen a study that proves
> that. says:
"In the rare case that the rounding-off error becomes a problem,
obtain minimum integer n such that N<=2^n, generate integer random
numbers, take the most significant n bits, and discard those more
than or equal to N."

Note the penultimate part. Whether that's grounded in any way or just
erring on the safe side, the authors are probably in the best
position to tell you.


Quidquid latine scriptum sit, altum viditur.

[ See for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Seungbeom Kim on
Francis Glassborow wrote:
> However I see so many requests for functionality to select at random one
> element from a range that I begin to wonder if we should not have a
> standard library function template that simply returns a random member
> from a container. We could then apply it to an array of int when we
> wanted to select an integer value from a small range.

I have to agree strongly. The pair of rand() and RAND_MAX is so
primitive, and puts the same kind of arithmetic burden over and over
upon the shoulders of those programmers who need random numbers in a
specific range. It is further justified by the fact that the value of
rand() is pretty useless unless it's further conditioned to fall into a
specific range; we'd never use the value directly, which means *every*
user of rand() would be doing the same thing manually.

Shouldn't we have in the standard library something like nrand(n) which
returns a random number in the range [0, n)? Of course we do have
Boost.Random, but since it's much more complex and it has a much steeper
learning curve, I think it's better to leave it for more serious tasks
and let simpler tasks take advantage of rand() more easily.

Seungbeom Kim

[ See for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]