From: linux-os <linux-os@chaos.analogic.com>
To: "Patrick J. LoPresti" <patl@curl.com>
Cc: Linux kernel <linux-kernel@vger.kernel.org>
Subject: Re: /dev/random vs. /dev/urandom
Date: Mon, 10 Jan 2005 07:41:02 -0500 (EST) [thread overview]
Message-ID: <Pine.LNX.4.61.0501100735210.19253@chaos.analogic.com> (raw)
In-Reply-To: <s5gzmzjbza1.fsf@egghead.curl.com>
On Sat, 8 Jan 2005, Patrick J. LoPresti wrote:
> linux-os <linux-os@chaos.analogic.com> writes:
>
>> In this case I AND with 1, which should produce as many '1's as
>> '0's, ... and clearly does not.
>
> Actually, a fair coin flipped N times is unlikely to come up heads
> exactly N/2 times, and the probability of this drops quickly as N
> grows.
>
> What is true is that it will usually come up heads N/2 times, give or
> take sqrt(N). Mathematicians call this the "Central Limit Theorem".
>
> For example, take N=32. The square root of 32 is a little less than
> 6. So we expect to see between 16-6 (i.e., 10) and 16+6 (i.e., 22)
> heads in a typical trial. (Of course, in one trial out of 4 billion
> it will come up all heads. The Central Limit Theorem is about "usual"
> outcomes, not every outcome.)
>
> So we expect between 10 and 22 odds/evens in your trial.
>
>> Trying /dev/random
>> 0100000101010000010001000101000000000000000101000100010000000101
>> odds = 14 evens = 18
>> Trying /dev/urandom
>> 0001010001000100000101000100010001000000000000000000010000000000
>> odds = 10 evens = 22
>> LINUX> ./xxx
>> Trying /dev/random
>> 0100000100010101000101010101010101000100010000010001010000000101
>> odds = 20 evens = 12
>> Trying /dev/urandom
>> 0100000100000101010001000101010001010001000000010101010100010000
>> odds = 18 evens = 14
>
> Well how about that. Try it with larger N, and you will find it gets
> even harder to hit a case where the total is outside the sqrt(N) error
> margin. And of course, as a percentage of N, sqrt(N) only shrinks as
> N grows.
>
> If you doubt any of this, try it with a real coin. Or read a book on
> probability.
>
> - Pat
One is free to use any number of samples. The short number of samples
was DELIBERATELY used to exacerbate the problem although a number
or nay-sayers jumped on this in an attempt to prove that I don't
know what I'm talking about.
In the first place, the problem was to display the error of using
an ANDing operation to truncate a random number. In the limit,
one could AND with 0 and show that all randomness has been removed.
However, those who know nothing about the theory would then
probably jump upon this as a "special case" even though it usn't.
Cheers,
Dick Johnson
Penguin : Linux version 2.6.10 on an i686 machine (5537.79 BogoMips).
Notice : All mail here is now cached for review by Dictator Bush.
98.36% of all statistics are fiction.
next prev parent reply other threads:[~2005-01-10 12:41 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-01-07 19:05 /dev/random vs. /dev/urandom Ron Peterson
2005-01-07 19:16 ` Paulo Marques
2005-01-07 19:24 ` Chris Friesen
2005-01-07 19:26 ` Florian Weimer
2005-01-07 19:27 ` linux-os
2005-01-07 19:40 ` Robert Love
2005-01-07 20:50 ` Ron Peterson
2005-01-07 21:39 ` Andries Brouwer
2005-01-07 22:39 ` linux-os
2005-01-07 17:55 ` Michal Schmidt
2005-01-07 23:29 ` Andries Brouwer
2005-01-08 17:34 ` Patrick J. LoPresti
2005-01-10 12:41 ` linux-os [this message]
2005-01-10 13:03 ` Paulo Marques
2005-01-10 14:39 ` Felipe Alfaro Solana
2005-01-10 15:13 ` Patrick J. LoPresti
2005-01-10 19:24 ` David Schwartz
2005-01-11 14:38 ` Andrea Arcangeli
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.61.0501100735210.19253@chaos.analogic.com \
--to=linux-os@chaos.analogic.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-os@analogic.com \
--cc=patl@curl.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).