xor: how come so slow?

[Tim Roberts]

Re: xor: how come so slow?

Steven D'Aprano <steve@REMOVE-THIS-cybersource.com .auwrote:

>
>On Fri, 17 Oct 2008 20:51:37 +1300, Lawrence D'Oliveiro wrote:
>

>Is piece really meant to be random? If so, your create_random_b lock
>function isn't achieving much--xoring random data together isn't going
>to produce anything more exciting than less random data than you started
>with.

>
>Hmmm... why do you say that xoring random data with other random data
>produces less randomness than you started with?
>
>I'm not saying that you're wrong, and certainly it is pointless since
>you're not going to improve on the randomness of /dev/urandom without a
>lot of work. But less random?

For those who got a bit lost here, I'd would point out that Knuth[1] has an
excellent chapter on random numbers that includes a detailed discussion of
this effect. His net takeaway is that most of the things people do to
increase randomness actually have exactly the opposite effect.
-----
[1] Knuth, Donald. The Art of Computer Programming, Volume 2,
Seminumerical Algorithms.
--
Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

[Steven D'Aprano]

Re: xor: how come so slow?

On Sun, 19 Oct 2008 16:38:37 +1300, Lawrence D'Oliveiro wrote:

In message <010a9c3f$0$206 53$c3e8da3@news .astraweb.com>, Steven D'Aprano
wrote:
>

>On Sat, 18 Oct 2008 09:16:11 +1300, Lawrence D'Oliveiro wrote:
>>

>>Data can come in fractional bits. That's how compression works.

>>
>If you don't believe me, try compressing a single bit and see if you
>get a "fractional bit".

>
If both states of the bit are not equally likely, then you do indeed
have a fractional bit, since
>
nrbits = (- logbase2(P[bit = 0]) - logbase2(P[bit = 1])) / 2

That's an arithmetic mean of the logarithms. It doesn't imply that there
are fractional bits any more than an average family having 2.3 children
implies that there are 0.3 of a child wandering around the streets.

Using the Shannon measure of information, you can have messages which
contain fractional information (technically, "surprisal" ), when measured
in bits. But that doesn't imply the existence of fractional bits. Look at
it this way: consider a barter economy where I agree to swap 5 chickens
for 2 axes. So each axe is equivalent to 2.5 chickens. But that doesn't
imply that there is such a thing as 0.5 of a chicken -- at least not a
*live* chicken. While I can blithely talk about bartering fractional
chickens, in practice when I actually go to make good on my promise, it
must be an integer number of chickens.

Similarly, we can talk about messages containing fractional bits of
information, but when we actually store or transmit that message in
practice, we can only use integer numbers of bits.

As Wikipedia puts it:

It is important to differentiate between the use of "bit" in referring to
a discrete storage unit and the use of "bit" in referring to a
statistical unit of information. The bit, as a discrete storage unit, can
by definition store only 0 or 1. A statistical bit is the amount of
information that, on average[citation needed], can be stored in a
discrete bit. ... If these two ideas need to be distinguished, sometimes
the name bit is used when discussing data storage while shannon is used
for the statistical bit.

http://en.wikipedia.org/wiki/Bit

--
Steven

[Steven D'Aprano]

Re: xor: how come so slow?

On Sun, 19 Oct 2008 04:38:04 +0000, Tim Roberts wrote:

Steven D'Aprano <steve@REMOVE-THIS-cybersource.com .auwrote:

>>
>>On Fri, 17 Oct 2008 20:51:37 +1300, Lawrence D'Oliveiro wrote:
>>

>>Is piece really meant to be random? If so, your create_random_b lock
>>function isn't achieving much--xoring random data together isn't going
>>to produce anything more exciting than less random data than you
>>started with.

>>
>>Hmmm... why do you say that xoring random data with other random data
>>produces less randomness than you started with?
>>
>>I'm not saying that you're wrong, and certainly it is pointless since
>>you're not going to improve on the randomness of /dev/urandom without a
>>lot of work. But less random?

>
For those who got a bit lost here, I'd would point out that Knuth[1] has
an excellent chapter on random numbers that includes a detailed
discussion of this effect. His net takeaway is that most of the things
people do to increase randomness actually have exactly the opposite
effect.

I don't doubt it at all. But xoring random data with more random data?
I'm guessing that if the two sources of data are independent and from the
same distribution, then xoring them is pointless but not harmful. Here's
a rough-and-ready test which suggests there's little harm in it:

>>import os, math
>>def rand_data(size) :

.... return [ord(c) for c in os.urandom(size )]
....

>>def mean(data):

.... return sum(data)/len(data)
....

>>def stdev(data):

.... return math.sqrt( mean([x**2 for x in data]) - mean(data)**2 )
....

>>A = rand_data(1000) # good random data
>>B = rand_data(1000) # more good random data
>>AB = [a^b for (a,b) in zip(A, B)] # is this still good random data?
>>assert len(AB) == len(A) == len(B)
>>>
>>mean(A), stdev(A)

(126, 73.918874450305 31)

>>mean(B), stdev(B)

(128, 74.242844773082 339)

>>mean(AB), stdev(AB)

(129, 74.390859653589 16)


Note: I wouldn't take the above terribly seriously. Mean and standard
deviation alone are terrible measures of the randomness of data. But this
does suggest that any deviation from uniform randomness will be quite
subtle.



--
Steven

[MRAB]

Re: xor: how come so slow?

On Oct 19, 7:13 am, Dennis Lee Bieber <wlfr...@ix.net com.comwrote:

On Sun, 19 Oct 2008 04:38:04 GMT, Tim Roberts <t...@probo.com declaimed
the following in comp.lang.pytho n:
>
>
>

For those who got a bit lost here, I'd would point out that Knuth[1] has an
excellent chapter on random numbers that includes a detailed discussionof
this effect.  His net takeaway is that most of the things people do to
increase randomness actually have exactly the opposite effect.

>
        Some decade I'll have to obtain his volumes... But they've never
shown up in a $60 special offer from a book club (unlike the compact
editions of the OED) <G>.
>
        And while XOR may seem significant, just consider die rolls...
>
        If each "byte" were one die roll, you'd expect a nearly even
distribution... (for a 6 sided die, 1/6 would have each value). But
using the sum of two die, your begin to get a bell curve: 2 and 12
appear 1/36 of the time (each), but 7 occurs 6/36 of the time. Use three
die, and it gets worse: 3 and 18 occur 1/216, "10.5" occurs much more
often...
>

That should be one die, two dice, etc. :-)

[Steve Holden]

Re: xor: how come so slow?

Lawrence D'Oliveiro wrote:

In message <010a9c3f$0$206 53$c3e8da3@news .astraweb.com>, Steven D'Aprano
wrote:
>

>On Sat, 18 Oct 2008 09:16:11 +1300, Lawrence D'Oliveiro wrote:
>>

>>Data can come in fractional bits. That's how compression works.

>If you don't believe me, try compressing a single bit and see if you get
>a "fractional bit".

>
If both states of the bit are not equally likely, then you do indeed have a
fractional bit, since
>
nrbits = (- logbase2(P[bit = 0]) - logbase2(P[bit = 1])) / 2

What's happening here is that the two different meanings of "bit" are
being confused. A bit is both a binary digit and a measure of information.

Obviously you can't create a bit stream with half a bit in it.

In a coding system where all messages of N binary digits are equally
likely then each message contains N bits of information content. This is
the theoretical upper bound on the information content.

In most practical systems, however, the messages have differing
probabilities; then an N-binary-digit message conveys less than N bits
of information, as Lawrence indicated above. Fractional bits are
perfectly valid as a measure of information content.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/

[Aaron Brady]

Re: xor: how come so slow?

Steven D'Aprano wrote:

On Sun, 19 Oct 2008 04:38:04 +0000, Tim Roberts wrote:
>

>Steven D'Aprano <steve@REMOVE-THIS-cybersource.com .auwrote:

>>>
>>>On Fri, 17 Oct 2008 20:51:37 +1300, Lawrence D'Oliveiro wrote:
>>>
>>>Is piece really meant to be random? If so, your create_random_b lock
>>>function isn't achieving much--xoring random data together isn't going
>>>to produce anything more exciting than less random data than you
>>>started with.
>>>
>>>Hmmm... why do you say that xoring random data with other random data
>>>produces less randomness than you started with?
>>>
>>>I'm not saying that you're wrong, and certainly it is pointless since
>>>you're not going to improve on the randomness of /dev/urandom without a
>>>lot of work. But less random?

>>
>For those who got a bit lost here, I'd would point out that Knuth[1] has
>an excellent chapter on random numbers that includes a detailed
>discussion of this effect. His net takeaway is that most of the things
>people do to increase randomness actually have exactly the opposite
>effect.

>
I don't doubt it at all. But xoring random data with more random data?
I'm guessing that if the two sources of data are independent and from the
same distribution, then xoring them is pointless but not harmful. Here's
a rough-and-ready test which suggests there's little harm in it:
>
>

>>>import os, math
>>>def rand_data(size) :

... return [ord(c) for c in os.urandom(size )]
...

>>>def mean(data):

... return sum(data)/len(data)
...

>>>def stdev(data):

... return math.sqrt( mean([x**2 for x in data]) - mean(data)**2 )
...

>>>A = rand_data(1000) # good random data
>>>B = rand_data(1000) # more good random data
>>>AB = [a^b for (a,b) in zip(A, B)] # is this still good random data?
>>>assert len(AB) == len(A) == len(B)
>>>>
>>>mean(A), stdev(A)

(126, 73.918874450305 31)

>>>mean(B), stdev(B)

(128, 74.242844773082 339)

>>>mean(AB), stdev(AB)

(129, 74.390859653589 16)
>
>
Note: I wouldn't take the above terribly seriously. Mean and standard
deviation alone are terrible measures of the randomness of data. But this
does suggest that any deviation from uniform randomness will be quite
subtle.
>
>
>

Operations like 'and' and 'or' will tend to destroy randomness. 'and'
tends to the 0-string and 'or' tends to the 1-string. I feel like 'xor'
should be safe (like Steven), but is the proof merely the half-and-half
split of the truth table?

[Lawrence D'Oliveiro]

Re: xor: how come so slow?

In message <gdea3t$4tj$1@l ust.ihug.co.nz> , Lawrence D'Oliveiro wrote:

In message <010a9c3f$0$206 53$c3e8da3@news .astraweb.com>, Steven D'Aprano
wrote:
>

>On Sat, 18 Oct 2008 09:16:11 +1300, Lawrence D'Oliveiro wrote:
>>

>>Data can come in fractional bits. That's how compression works.

>>
>If you don't believe me, try compressing a single bit and see if you get
>a "fractional bit".

>
If both states of the bit are not equally likely, then you do indeed have
a fractional bit, since
>
nrbits = (- logbase2(P[bit = 0]) - logbase2(P[bit = 1])) / 2

Oops, sorry, the formula should of course be

nrbits = - P[bit = 0] * logbase2(P[bit = 0])
- P[bit = 1] * logbase2(P[bit = 1])