Prime number module

[Emile van Sebille]

> "Lulu of the Lotus-Eaters" <mertz at gnosis.cx> wrote:
>
> > Along those lines, what's the quickest way to count bits in Python?
> > Maybe someone has a clever idea... something that would run a whole
> > bunch faster than my bit mask style above for counting all the "1"s in a
> > multibyte string.
> >

FWIW, using array pops the speed up significantly for long strings:

import string, time, array

nibbles = [(w+x+y+z, w*8+x*4+y*2+z)
  for w in (0,1) for x in (0,1)
  for y in (0,1) for z in (0,1)]

bitcounts = [
    (chr(hinibblevalue*16 + lonibblevalue),
    hibitcount+lobitcount)
    for hibitcount, hinibblevalue in nibbles
    for lobitcount, lonibblevalue in nibbles ]

bytes = dict(bitcounts)

xlater = "".join([chr(bitcount) for byte, bitcount in bitcounts])

def bitcount1(bytestr):
    return sum([bytes[ii] for ii in bytestr])

def bitcount2(bytestr):
    return sum(map(ord, string.translate(bytestr,xlater)))

def bitcount4(bytestr):
    return sum(array.array("B",string.translate(bytestr,xlater)))

refstr = 'a'*1000000

t=time.time()
bitcount1(refstr)
print time.time()-t

t=time.time()
bitcount2(refstr)
print time.time()-t

t=time.time()
bitcount4(refstr)
print time.time()-t


--

Emile van Sebille
emile at fenx.com