xor: how come so slow?

[Michele]

Hi,
I'm trying to encode a byte data. Let's not focus on the process of
encoding; in fact, I want to emphasize that the method
create_random_b lock takes 0.5s to be executed (even Java it's faster) on
a Dual-Core 3.0Ghz machine:

took 46.746999979s, avg: 0.46746999979s

Thus I suppose that the xor operation between bytes raise the execution
time to 0.5; why I suppose that?
Because in Python there's no support for bytes and even for xoring
bytes, so I used a workaround:
I cycle on the two strings to be xor-red
for every char in the strings
convert one char on integer and then xor them; (ord)
insert one char in the result, transforming the previous integer
in char (chr)

I suppose that ord() and char() are the main problems of my
implementation, but I don't know either way to xor two bytes of data
(bytes are represented as strings).
For more information, see the code attached.

How should I decrease the execution time?

Thank you
from __future__ import division
import random
import time
import sha
import os

class Encoder(object) :
def create_random_b lock(self, data, seed, blocksize):
number_of_block s = int(len(data)/blocksize)
random.seed(see d)
random_block = ['0'] * blocksize
for index in range(number_of _blocks):
if int(random.getr andbits(1)) == 1:
block = data[blocksize*index :blocksize*inde x+blocksize]
for bit in range(len(block )):
random_block[bit] =
chr(ord(random_ block[bit])^ord(block[bit])) # workaround per fare xor
bit a bit di str; xor e' solo supportato per int -ord
return ''.join(random_ block)
x = Encoder()
piece = os.urandom(1024 *1024)
blocksize = 16384
t1 = time.time()
for l in range(100):
seed = random.getrandb its(32)
block = x.create_random _block(piece, seed, blocksize)
t2 = time.time()
print 'took ' + str(t2-t1) + 's, avg: ' + str((t2-t1)/100.0) + 's'

[Aaron Brady]

Steven D'Aprano wrote:

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

>Steven D'Aprano <st***@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]

In message <gd**********@l ust.ihug.co.nz> , Lawrence D'Oliveiro wrote:

In message <01************ **********@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])