This is the mail archive of the mailing list for the glibc project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: What is the reason for multiplying 10 in __srandom_r?

It is highly desirable for a pseudo-random number generation library routine
to have good statistical properties. Supposedly minor changes to
an algorithm can play havoc with the algorithm's statistical properties.

These days, if an efficient integer multiplication is not available in the HW,
the compiler can easily generate a "x+x+8*x" sequence which is nearly
as efficient as "8*x".  Certainly it is a tiny cost compared to
the 10*x calls to " (void) __random_r (buf, &discard);"

In addition, for Monte-Carlo simulation, part of the value of pseudo-random number generators is the ability to reproduce results for a given seed in order to allow
comparisons with different input conditions, etc. Any proposal to change
a standard library routine that provides a pseudo-random number will rightfully
be met with great resistance.

Pseudo-random number generation is an area where there has been a lot of
deep mathematical study for a long time.  See
for an introduction to the field and follow up with the links to that article
if you find a need for further study.

- patrick

On 5/30/2018 10:03 PM, Xinzhen Chen wrote:
Hello, glibc developers :-)

I was trying to understand what functions like rand() do under the hood. I
compiled glibc 2.27 from source and link the new compiled to my
test C program in the following:

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char const* argv[])
int randt[32] = {0};
initstate(2, (char*)randt, 128);
printf("%d\n", rand());
return 0;

I used gdb to step into initstate() function and got confused when I
stepped into the following line of  __srandom_r function:

   kc = buf->rand_deg;
   for (i = 1; i < kc; ++i)
       /* This does:
    state[i] = (16807 * state[i - 1]) % 2147483647;
but avoids overflowing 31 bits.  */

   buf->fptr = &state[buf->rand_sep];
   buf->rptr = &state[0];
   kc *= 10;
   while (--kc >= 0)
       int32_t discard;
       (void) __random_r (buf, &discard);

I also read the comment of  __srandom_r function which says "Lastly, it
cycles the state information a given number of times to get rid of any
initial dependencies introduced by the L.C.R.N.G.".

My questions are:
1. Why the " given number of times" is "kc * 10" instead of "kc * 8" or "kc
* 16" which is more efficient in multiplication?
2. Are there papers or books which dive into glibc random implementation
?(I've read some chapters of <TAOCP vol 2>, <Advanced mordern algebra>,but
still can not totally understand the implementation of glibc random

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]