From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 51115 invoked by alias); 31 May 2018 15:14:01 -0000 Mailing-List: contact libc-help-help@sourceware.org; run by ezmlm Precedence: bulk List-Subscribe: List-Post: List-Help: , Sender: libc-help-owner@sourceware.org Received: (qmail 51091 invoked by uid 89); 31 May 2018 15:14:00 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy=study, H*UA:6.3, seed, Hx-languages-length:2724 X-HELO: userp2120.oracle.com Received: from userp2120.oracle.com (HELO userp2120.oracle.com) (156.151.31.85) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 31 May 2018 15:13:58 +0000 Received: from pps.filterd (userp2120.oracle.com [127.0.0.1]) by userp2120.oracle.com (8.16.0.22/8.16.0.22) with SMTP id w4VF6EdX001073 for ; Thu, 31 May 2018 15:13:57 GMT Received: from userv0021.oracle.com (userv0021.oracle.com [156.151.31.71]) by userp2120.oracle.com with ESMTP id 2j9ev87dxd-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Thu, 31 May 2018 15:13:57 +0000 Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by userv0021.oracle.com (8.14.4/8.14.4) with ESMTP id w4VFDuiH014413 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK) for ; Thu, 31 May 2018 15:13:56 GMT Received: from abhmp0004.oracle.com (abhmp0004.oracle.com [141.146.116.10]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id w4VFDusd017206 for ; Thu, 31 May 2018 15:13:56 GMT Received: from [10.39.252.48] (/10.39.252.48) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Thu, 31 May 2018 15:13:56 +0000 Subject: Re: What is the reason for multiplying 10 in __srandom_r? To: libc-help@sourceware.org References: From: Patrick McGehearty Message-ID: <4c4a34b2-640b-04c5-a578-eb68a5b24c90@oracle.com> Date: Thu, 31 May 2018 15:14:00 -0000 User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=8909 signatures=668702 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=1 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1805220000 definitions=main-1805310170 X-IsSubscribed: yes X-SW-Source: 2018-05/txt/msg00035.txt.bz2 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 > #include > > 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 , ,but > still can not totally understand the implementation of glibc random > functions)