What is the reason for multiplying 10 in __srandom_r?

What is the reason for multiplying 10 in __srandom_r?

[Xinzhen Chen]

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 libc.so.6 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);
setstate((char*)randt);
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
functions)

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

[Patrick McGehearty]

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
https://en.wikipedia.org/wiki/Pseudorandom_number_generator
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 libc.so.6 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);
> setstate((char*)randt);
> 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
> functions)