Prime number module

[Alex Martelli]

Alex Martelli wrote:

> Lulu of the Lotus-Eaters wrote:
>    ...
>> Along those lines, what's the quickest way to count bits in Python?
> 
> Probably gmpy's popcount function.
> 
>> 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.
> 
> I would try gmpy.mpz(multibytestring, 256).popcount().  E.g.:
> 
>>>> gmpy.mpz('gmpy IS pretty fast for many kinds of things',256).popcount()
> 163
> 
> and, on my trusty 30-months-old Athlon box...:
> 
> [alex at lancelot python2.3]$ python timeit.py -s'import gmpy' \
>> -s'x="gmpy IS pretty fast for many kinds of things"' \
>> 'gmpy.mpz(x,256).popcount()'
> 100000 loops, best of 3: 8.13 usec per loop
> [alex at lancelot python2.3]$

Silly me, for not including a "pure Python" alternative run on the
same machine for comparison purposes -- sorry.  Given the following
bitcount.py module (only the initialization is coded with gmpy,
and just because I'm lazy -- that doesn't affect timings!):

import gmpy

byte_bit_counts = dict([(chr(b), gmpy.popcount(b)) for b in range(256)])

def popcount(s, bbc=byte_bit_counts):
    return sum([bbc[c] for c in s])

>>> import bitcount
>>> x="gmpy IS pretty fast for many kinds of things"
>>> bitcount.popcount(x)
163

and, on the same box:

[alex at lancelot python2.3]$ python timeit.py -s'import bitcount' \
> -s'x="gmpy IS pretty fast for many kinds of things"' \
> 'bitcount.popcount(x)'
10000 loops, best of 3: 82.2 usec per loop

So, the speed advantage of gmpy is just about one order of magnitude
for this trivial operation.


Alex