This is the mail archive of the
`libc-help@sourceware.org`
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] |

*From*: Patrick McGehearty <patrick dot mcgehearty at oracle dot com>*To*: libc-help at sourceware dot org*Date*: Thu, 31 May 2018 10:13:53 -0500*Subject*: Re: What is the reason for multiplying 10 in __srandom_r?*References*: <CAJkDRHd4BUPL-owpoHwHm0mWFkdNk47eOSckW1UeD77-o78HYA@mail.gmail.com>

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.

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);"

comparisons with different input conditions, etc. Any proposal to change

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

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)

**References**:**What is the reason for multiplying 10 in __srandom_r?***From:*Xinzhen Chen

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |