November 2009 - Darwin-dev - lists.apple.com

Re: rand() and srand() broken?
by Derek Gaston 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:subject:mime-version :content-type:from:in-reply-to:date:cc:content-transfer-encoding :message-id:references:to:x-mailer; bh=B9dYjggVI5lcTlegAXvOPOThK8I653rifac2q496Uls=; b=TU47kBaOBSWLeWsIceXqkAV86QRjBrGo4s1TAxZINNSQCNxMiwXaLiAK6tSoxyp/ne rpz+xTE7mSzh2WExebAqaCSUY1nkkoDGKDiU2SU5d1DETCb5ieCkLvOtIuDfCT+WIr4h IMFkYXqHJOda/hyB2R1odOxPtq6YyVLYpRknc= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=subject:mime-version:content-type:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to:x-mailer; b=QuHH9VyI34mV55S22iVFnmRlTfLeuAPfmqnG2JnbO76VQTTJBtY+coN2+iNkactqDg JlYmKd4fzr6V+MN9RZhVS2Pir6497CpKx5/UC68j5y4sMPRuLhHuzW22UDpru5zVSitJ kfNMqWZTqblX0Exe+kjDnoMu5V6tSJEe8yAQE= On Nov 25, 2009, at 12:41 PM, Clark Cox wrote: > Yes. If you pass the same value to seed(), you will get the same > sequence of values from rand(). Period. Any implementation of > srand/rand that does not do this is broken. From the C Standard: Indeed... note that this wasn't about passing the _same_ value... it was about passing similar values to srand... like singularly increasing integers... Derek _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Clark Cox 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=+CF8VbtHnu9RRA2EkOWizAbXRSOgZVC5cbSIQ+DuSis=; b=mObo35TwK+nbdTmB9TuoK59cSt2P8IFE/sLJBfQ8tNtXyrAXCI8n2e8eQhvr5z10+M eGX5NscKLC3ob2u4vmn6u84OVTTjOPNOiofRh0YogKutnYLCmC5xlcgpyItlY8hha650 kzF1MAB4UOvoFe5tDRsgZnccz69f9l5wAjP1Q= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=YDudICJ8UCMhp77tGNmcTQOv+WCb8HLWJpVTSx7OOi3tRYOB+3HP6cXpQebATPdRmx 89JnolOKouq2XL9wH23Gc0cDLPPlxrKVCpqlZMXE4O/HCf3SlOAFjQdc67pY3BNtEDvl Do6DuGewKRa4qY/jlRMNA+861o1BSCRxZkI0k= On Wed, Nov 25, 2009 at 1:40 PM, Derek Gaston <friedmud(a)gmail.com> wrote: > On Nov 25, 2009, at 10:47 AM, Jason Foreman wrote: > >> >> On Nov 25, 2009, at 11:26 AM, Derek Gaston wrote: >> >>> This piece of code should generate 100 random numbers between 0 and 1... >>> I am expecting that they be fairly spaced out as well... >> >> What basis do you have for this expectation? Is it spelled out in any >> specification or standard somewhere? >> >> You're seeding the RNG with a monotonically increasing seed, and getting >> what looks like monotonically increasing starting values for your random >> sequences. The fact that you get what you expect on Linux seems to be >> purely coincidental. > > Are you (and everyone else that replied) trying to tell me that the first > number out of rand() (after reseeding) should always be the predictable? Yes. If you pass the same value to seed(), you will get the same sequence of values from rand(). Period. Any implementation of srand/rand that does not do this is broken. From the C Standard: "The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated." -- Clark S. Cox III clarkcox3(a)gmail.com _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… This email sent to site_archiver(a)lists.apple.com

1 0

Re: [APPL:DarwinDev] Re: rand() and srand() broken?
by Derek Gaston 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:references:x-mailer; bh=UH9gMzZP+1PA4349tqCC6Z1m3GA9VSnrvlIkM7sPgAI=; b=Nh3o56K6oc9tda5InWR4yXatgY1Kj53XVBYPks7Gc0hkk4SDxlP/IcEdowO5yoaNuK bW+Z2N8JmlOUgxB4c2N2T9wZmG8hRYwV1G7d/vMpAJM+S2ShLeypFY+3gFBLVX0lhZjn hbaklfA/XK2WUjL104p+5waE4le/zqJ1YJU6Y= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=Nza21wlnDYEDbF42X+AUb7IYpdpX5XWTFQBHm6aR9nidw2DVNx/e6g73R039IOEPzf AK8sVwsmaRP4XsI8xmGSwq0IqI5F9pBehkYpeJY4DlnMydgI/Wl9XiJbZtk7pW02HsL0 Q7ti0fn+OjKCi52+sgUSk0jU9USj4ae0kLlfI= On Nov 25, 2009, at 11:59 AM, Jay A. Kreibich wrote: This is, I suspect, part of the problem. When random() replaced rand() in the BSD sources ages ago, I'm guessing nobody ever went back and made rand() better. It was understood that you just didn't use rand() and "fixing" it by changing the algorithm would break applications like yours. This is less true in Linux. For one thing, the source code has a much younger lineage, and I'm guessing someone decided it was a good idea to "improve" rand() at some point, even if that meant breaking backwards compatibility. I haven't. Derek _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… Have you tried you test on a BSD-based system? Regardless, in that situation I'd write my own PRNG. That way you can exactly control the balance between performance and quality and, more importantly, you'll have cross-platform compatibility. From what you're doing, you don't really need a "random" number, you just need a good hash that will go from regular numbers (row/column) to a good coverage of the number domain. Even something like a CRC might be a good choice... unlike many crypto hashes, it does well with just a few bytes of data to chew on. Thanks for the idea of using a CRC... I hadn't thought about that. A random hash really is what we're going for here... and I'm starting to see that bastardizing rand/srand for that maybe wasn't the best idea ;-) This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Derek Gaston 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:references:x-mailer; bh=AyfbOrsn14kNwCHymwBFy8zZW9g7913MUEcOsWETWao=; b=A+2keBN1RuJ2TxrBMYOXwS1bF1zfJb3/HSHVnhUFa7DOrB9NM+QemL0VjAu7bOr2kN XL91Ex2Cp+gYo0Oo8ZOTi9AqAMDsiEsD/x3v7ZFwVQ9nM0dWxZIiCdpIRcE0mrlf9OlF Sexp+NfLabo456QM5MWuu8p3hzPQRSwpjBdt8= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=NaesM5xJWK84dyVaVZf3QoGSHdCO3hGUcUl3mbgCa98en8NA/ZrqI7haWso0t64Yf2 Qgj9sayhW9KdvX26IsokwgN4kaCq00DKDr0N29ttD9ELS3XX9ymCPlBs6v8cCLx5N/qq 8S1/BwrzZ0MmhVmfX2fjP0P4rSGdDu59ZWv8M= On Nov 25, 2009, at 11:56 AM, Terry Lambert wrote: Derek _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… Tour requirements sound like a sequence offset restarttable CSPRNG for use in a block cipher for use in whole device or file/block level encryption for a mass storage device. You will need to carry around your own CSPRNG code for this, as system supplied PRNGs are generally not CSPRNGs, and their implementation can (and does) change. Such things generally generate their nonce (the initial seed value) from a passphrase or cryptographically generated key block stored some place like a USB key fob. The way you are trying to go about this is very guessable and not at all secure; I merely need to feed in monotonically increasing integers until I get a matching output value, and then monotonically increase my input for each subsequent value in order to decode your ciphertext. A high school student could break your message in under an hour, and under 5 minimum if it were using in band metadata for structured contents (e.g. an RFC-822 email message). Ah - I should have specified that this application has nothing (at all) to do with cryptography. In case people are interested... this is an engineering simulation application. We just need to generate random input into it (but like I said... on a grand scale... and with the ability to both get the same numbers back at points.... AND change the numbers throughout the simulation at specific times). The strength of the random numbers matters little. Also... the portability doesn't matter... in that we're not worried about getting different numbers on different machines... as long as every machine spews numbers throughout the range we want. This email sent to site_archiver(a)lists.apple.com

1 0

Re: [APPL:DarwinDev] Re: rand() and srand() broken?
by Jay A. Kreibich 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com User-agent: Mutt/1.5.18 (2008-05-17) On Wed, Nov 25, 2009 at 10:45:42AM -0800, Jens Alfke scratched on the wall: > > On Nov 25, 2009, at 9:26 AM, Derek Gaston wrote: > >> Hello everyone... I've been struggling with rand and srand on OSX 10.6 >> and 10.5. It seems to me that something is terribly broken. > > You shouldn't be using rand; it's not a good PRNG and it was obsoleted > ages ago by random(). > Even the man page tells you not to use it: > > RAND(3) BSD Library Functions Manual > RAND(3) > > NAME > rand, rand_r, srand, sranddev -- bad random number generator > ... > DESCRIPTION > These interfaces are obsoleted by random(3). This is, I suspect, part of the problem. When random() replaced rand() in the BSD sources ages ago, I'm guessing nobody ever went back and made rand() better. It was understood that you just didn't use rand() and "fixing" it by changing the algorithm would break applications like yours. This is less true in Linux. For one thing, the source code has a much younger lineage, and I'm guessing someone decided it was a good idea to "improve" rand() at some point, even if that meant breaking backwards compatibility. Have you tried you test on a BSD-based system? Regardless, in that situation I'd write my own PRNG. That way you can exactly control the balance between performance and quality and, more importantly, you'll have cross-platform compatibility. From what you're doing, you don't really need a "random" number, you just need a good hash that will go from regular numbers (row/column) to a good coverage of the number domain. Even something like a CRC might be a good choice... unlike many crypto hashes, it does well with just a few bytes of data to chew on. -j -- Jay A. Kreibich < J A Y @ K R E I B I.C H > "Our opponent is an alien starship packed with atomic bombs. We have a protractor." "I'll go home and see if I can scrounge up a ruler and a piece of string." --from Anathem by Neal Stephenson _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Derek Gaston 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:references:x-mailer; bh=JwNepvi3IAtic/rVKh1dfgqZRY5fFM4GljjkP0jPN10=; b=ZUA35/xenjdVFgDDiXnNlpS+ufRhP53crX3oMYissq6shGyrHTWGUq3sHOA58SkyLe XpaWZfQPKlwVuU4iqidK+kYoxDML5MNBCJ+/AdmRxvjwBDbnpXQ9dsD2CcY3tlX8oQm7 qPTPBcal57xoVaxvYPKiGcAq+S7trhu6+Bck4= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=t3MHHscv+ZWQA96j6DEV0hCYjJKwiS3UgkbZr8G4zXG+mzd0HTzKfoLKxmz5H6iL71 ihW7k2RhG+bu0oRpdqxcdrg7yHUwtRu31u97Pr+I27WGHS0MpTnwXV261gzXZxsgBPbW z+YQEHwuWddTGvIQnV+rdvJfVyvMvLE+irjrE= On Nov 25, 2009, at 11:45 AM, Jens Alfke wrote: Thanks for the reply! Derek _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… You shouldn't be using rand; it's not a good PRNG and it was obsoleted ages ago by random(). Even the man page tells you not to use it: Understood... but in an application like mine where I need to query a random number millions of times... random() is much too slow. I think the answer is just to take a few numbers of rand() to get the number I'm looking for.... which is still quite a bit faster than using random(). This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Derek Gaston 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:references:x-mailer; bh=9etiSrH+2M+nmE7oHEY+xqjljsb/ARhCE4IiIgU6St4=; b=dw09b+jcLI+PV668xE10hukRbabP6Vf8Sjp1bywXgUIYr5T+oWmaSi6qP7vGg/pJ9Z iQORI25WtrV9P+iPapecz0wmXR3wbdLiJyi/evqkwoem9fKuTZhhRcyKYvxt2k4xZdgZ 2HWTe/3rluUB42YF4YE7Ot9522yipB1/qNSCo= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=lePsp0IV3QkEKNhRaIGTGZ0X+VaSOhiAgZCM+nLKiYPSeIDv6gg0cPyktAf0X9/H9I AjIOla2fKZQtKhb35Pixv/3FGY+fn58grfZSrKNv4rOWETTtMjYU8T3Lo7aGfjOq5Fwi +ULIZLmgVJStVIgSovNw1wC4ihN2dEIKrH6MI= Thank you for the great explanation... that really does help a lot. Thanks again for all the prompt replies from everyone! Derek On Nov 25, 2009, at 11:31 AM, Terry Lambert wrote: However, his expectations and conclusions in this case are both bogus. -- Terry On Nov 25, 2009, at 11:26 AM, Derek Gaston wrote: _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… I think what I'm going to do is just change my algorithm so that I throw away the first (or maybe the first couple) entry by just calling rand() directly after calling srand(). The second number will still always reliably be the same given the same seed... and it is better spread out through the range. The relevant standards are FIPS 140-2, FIPS 186-2, NIST SP 800-90, ANSI X9.17-1985, ANSI x9.31-1998, and ANSI X9.62-2005. On UNIX systems, rand() is a simple PRNG, not a CSPRNG, and has historically used the 48 bit linear congruential PRNG algorithm derived from BSD UNIX. The BSD algorithim is what glibc, which houses Linux's implementation, still uses. In 10.4, Mac OS X went to use of /dev/random, which uses a kernel implementation of the CSPRNG based on the Yarrow algorithm. This was done in order that people who were using rand() incorrectly as if it were not a simple PRNG for things like nonce generation did not incorrectly introduce weaknesses into what was intended to be cryptographically secure code by their non-understanding of UNIX libraries. This was not a general fix, but provided a degree of hardening against first order attacks. In any case, compliance with cryptographic standards is neither a goal nor desirable for rand() and its family of functions. By reseeding with monotonocally increasing values each time he is resetting the sequence start value to a value which in Yarrow is directly derived, and further is tending to start with mostly zero bits and effect only the 7 least significant bits of the seed space, and only impact a few at a time. The conclusions of non-randomness on a sample size of 100 is also bogus and unjustifiable, due to his sample size being not statistically significant enough for him to draw any mathematically valid conclusions. To make a valid argument here, he would minimally need to apply the test suite providided in NIST Special Publication 800-22 before drawing any conclusions. This suite requires on the order of hundreds of millions of sequence runs before drawing any conclusions. PS: Minimally, unless the application is the intentional construction of a logically and mathematically flawed strawman argument, the reseeding must go. The initial value for a given input seed says absolutely nothing about the randomness of the subsequent sequences following from that seed; almost all PRNGs are based on feedback from previous results, and regardless of the algorithm being used, it is being denied its previous result. On Nov 25, 2009, at 9:47 AM, Jason Foreman <jason(a)threeve.org> wrote: This piece of code should generate 100 random numbers between 0 and 1... I am expecting that they be fairly spaced out as well... What basis do you have for this expectation? Is it spelled out in any specification or standard somewhere? You're seeding the RNG with a monotonically increasing seed, and getting what looks like monotonically increasing starting values for your random sequences. The fact that you get what you expect on Linux seems to be purely coincidental. This is actually indicative of what we actually do in one of our applications (I know it doesn't usually make much sense to reseed all the time... but you're just going to have to trust me that it's necessary in our case ;-) I think you're going to have to explain why you feel reseeding is necessary. You probably shouldn't be doing it. Jason This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Jens Alfke 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com On Nov 25, 2009, at 9:26 AM, Derek Gaston wrote: NAME rand, rand_r, srand, sranddev -- bad random number generator ... DESCRIPTION These interfaces are obsoleted by random(3). —Jens _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… Hello everyone... I've been struggling with rand and srand on OSX 10.6 and 10.5. It seems to me that something is terribly broken. You shouldn't be using rand; it's not a good PRNG and it was obsoleted ages ago by random(). Even the man page tells you not to use it: RAND(3) BSD Library Functions Manual RAND(3) This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Daniel M. Zimmerman 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com On Nov 25, 2009, at 10:47 AM, Jason Foreman wrote: On Nov 25, 2009, at 11:26 AM, Derek Gaston wrote: This piece of code should generate 100 random numbers between 0 and 1... I am expecting that they be fairly spaced out as well... What basis do you have for this expectation? Is it spelled out in any specification or standard somewhere? You're seeding the RNG with a monotonically increasing seed, and getting what looks like monotonically increasing starting values for your random sequences. The fact that you get what you expect on Linux seems to be purely coincidental. Are you (and everyone else that replied) trying to tell me that the first number out of rand() (after reseeding) should always be the predictable? Because that's essentially what I'm seeing. This, to me, feels very wrong. If I change the seed.... I should see a different first number. (snip) The issue is that we need to be able to reliably _regenerate_ different random numbers over and over.... but on a grand scale. Think of a matrix... you need to be able to get a random number for each entry in the matrix (let's say it's 10000000x10000000... so a LOT of numbers). BUT... you don't want to _store_ all of those numbers.... you just want to be able to query what the random number for any given entry is. So we come up with a way of guaranteeing unique seed numbers (for instance, using combinations of row and column numbers for this matrix example). Then we can always query a place in the matrix just by reseeding and calling rand(). It will reliably always give us back the same number over and over for a given seed. -Dan ------------------------------------------------------------------ Daniel M. Zimmerman TFF Enterprises 1900 Commerce St. Box 358426 http://www.tffenterprises.com/~dmz/ Tacoma, WA 98402 USA dmz(a)tffenterprises.com _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… --On 25 November 2009 11:40:10 -0700 Derek Gaston <friedmud(a)gmail.com> wrote: And you are... but the first number is, by definition, a function of the seed, and apparently the function Apple is using is not to your liking. That doesn't make it wrong; it just isn't the same non-guaranteed behavior you were relying on. Sure. But then you are highly dependent on the particular PRNG function being used by rand() on that platform, which is of course not particularly well specified. Maybe to get the random number for a particular row/column, you could seed the PRNG with your row/column number combination (however you calculate that) and then discard the first K random numbers it generates, where K is an easy-to-compute function of your row/column numbers. That would probably give you the "randomness" you're looking for, and would probably not be too much extra overhead. This email sent to site_archiver(a)lists.apple.com

1 0

Re: rand() and srand() broken?
by Derek Gaston 25 Nov '09

25 Nov '09

site_archiver(a)lists.apple.com Delivered-To: darwin-dev(a)lists.apple.com Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:content-transfer-encoding:mime-version :subject:date:references:x-mailer; bh=ytBCN9bBrm59msDm1sViendp20lU+84/yd3kkKOwr4A=; b=W4JWZFoa2hR+5vpV25RXdRom3fdcxyqpmWjhFQ5trjUaOU8fzQ8iaMzYQBysoUw0xs 8dCuIoi/kQKQS487FiJhbFNXtF5rYL+ADZIfELy2j/CUSf4fhWcq1IHk9Lkiy2fTSJoL ULJB3rJoH2kUny3LI/xEoxGDPz9XhVwbgX3l0= Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=N8z7pTicNSKFPwQyREuumox31cqBBxYXeQ3UDPIFuiWagD0u+7KQCjp7o6tCWk1mmr p6IZ02ZhAhqEhdBQb0pdtxeBLGAPs1h6niND/g0TH94GxmOdRW2cOmxpVc4LUWbIYO8N 3BIxsTfucasdXhifEDbtRFalhrhQ0cwyXjAN4= On Nov 25, 2009, at 10:47 AM, Jason Foreman wrote: On Nov 25, 2009, at 11:26 AM, Derek Gaston wrote: _______________________________________________ Do not post admin requests to the list. They will be ignored. Darwin-dev mailing list (Darwin-dev(a)lists.apple.com) Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/darwin-dev/site_archiver%40lists.app… This piece of code should generate 100 random numbers between 0 and 1... I am expecting that they be fairly spaced out as well... What basis do you have for this expectation? Is it spelled out in any specification or standard somewhere? You're seeding the RNG with a monotonically increasing seed, and getting what looks like monotonically increasing starting values for your random sequences. The fact that you get what you expect on Linux seems to be purely coincidental. Are you (and everyone else that replied) trying to tell me that the first number out of rand() (after reseeding) should always be the predictable? Because that's essentially what I'm seeing. This, to me, feels very wrong. If I change the seed.... I should see a different first number. Yes... I agree that later numbers will possibly look more random (depending on the algorithm used). But again, if the seed has changed... the first number out of rand() should be _different_. OSX is the only OS acting this way. It's really hard for me to believe that the first number out of rand after calling srand is so predictable. It seems like a poor choice of PRNG algorithm... This is actually indicative of what we actually do in one of our applications (I know it doesn't usually make much sense to reseed all the time... but you're just going to have to trust me that it's necessary in our case ;-) I think you're going to have to explain why you feel reseeding is necessary. You probably shouldn't be doing it. Heh - I knew this would come up. The issue is that we need to be able to reliably _regenerate_ different random numbers over and over.... but on a grand scale. Think of a matrix... you need to be able to get a random number for each entry in the matrix (let's say it's 10000000x10000000... so a LOT of numbers). BUT... you don't want to _store_ all of those numbers.... you just want to be able to query what the random number for any given entry is. So we come up with a way of guaranteeing unique seed numbers (for instance, using combinations of row and column numbers for this matrix example). Then we can always query a place in the matrix just by reseeding and calling rand(). It will reliably always give us back the same number over and over for a given seed. Our actually application is much more complicated than this... but I think this demonstrates our general need. Also... as someone else mentioned I did try using random() instead... and it works fine... but is CRAZY slow. It easily takes over 80% of the runtime of our application! (where rand() is in the noise). Yes... this means it's using a better algorithm... but there has to be a balance. On Linux rand() works correctly _and_ is fast. This email sent to site_archiver(a)lists.apple.com

1 0