A question about mpz_popcount
Sisyphus
sisyphus1 at optusnet.com.au
Thu Feb 28 04:25:31 CET 2008
----- 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
More information about the gmp-discuss
mailing list