A question about mpz_popcount

[Sisyphus]

----- Original Message ----- 
From: <jdevoto.uba at gmail.com>
To: <gmp-discuss at swox.com>
Sent: Thursday, February 28, 2008 9:09 AM
Subject: A question about mpz_popcount


> Hi,
>
> I haven't used gmp for many years so my question might have an obvoius
> answer.
>
> I have some millions of numbers of 7296 bits (a multiple of 16). I
> would like to count the bits in each of the 16 equal parts of the
> number. For example I have one part from bit 0 to bit 456, a second
> one from bit 457 to bit ... etc. And I would like to produce a number
>
> b_15 b_14 ... b_0
>
> were each one of the bits b_j is the quantity of bits in part j.
>

In terms of gmp, I would do it as follows:

Set:
 and = (2^456) - 1

Then do (in a loop):
b_0 = popcount (number & and)
number >>= 456
b_1 = popcount(number & and)
number >>= 456
.
.
b_14 = popcount(number & and)
number >>= 456
b_15 = popcount(number & and)

The right shifts are done using mpz_tdiv_q_2exp - popcount and bitwise-& are 
done (obviously) with mpz_popcount and mpz_and.

Not sure what the result is supposed to look like - I assume a string of 16 
space-delimited digits  - eg:

237 225 230 232 227 236 244 247 217 254 241 233 242 219 227 241

I wrote and timed a perl script that does that (using gmp, of course) and 
the processing of 10,000 such (random)7296-bit numbers took just under 1 
second. That includes the time it took to create the formatted strings (as 
per above) in memory, but not any I/O operations. That is, it was the time 
taken for the *processing* alone. A rate of 100 seconds per million numbers 
seems reasonable to me .... but you've given no indication of what is 
acceptable from your point of view :-)

I'm using a 2.4GHz Athlon, 32-bit build of gmp-4.2.2.

Cheers,
Rob