want fast bit set/extract

D. J. Bernstein djb at cr.yp.to
Sun Apr 18 11:47:38 CEST 2004

Yes, the functions can be combined into a single operation. For example,
GMP could support a function

   void mpz_copybits_fdiv(
     mpz_t rop,unsigned long t,
     mpz_t op,unsigned long s,
     unsigned long b)

to compute

   rop - 2^t (floor(rop / 2^t) mod 2^b) + 2^t (floor(op / 2^s) mod 2^b)

and put the result into rop; in other words, to copy bits s...s+b-1 of
op to bits t...t+b-1 of rop. Crude, untested, sample implementation:

   void mpz_copybits_fdiv(mpz_t rop,unsigned long t,mpz_t op,unsigned long s,
     unsigned long b)
     while (b-- > 0) (mpz_tstbit(op,s++) ? mpz_setbit : mpz_clrbit)(rop,t++);

If op and rop are nonnegative and rop already has enough space allocated
then the time should be linear in b, with a small constant, particularly
when s, t, and b are multiples of the word size. The above code has this
property except that the constant is much larger than it ought to be.

Please make this faster, and add official support for it.

An mpz_copybits_tdiv---which would be faster for negative numbers, and
simpler, with your current integer representation---would be fine for
typical applications. I suggested fdiv above because you seem to have
mpz_tstbit = mpz_tstbit_fdiv, etc., without tdiv versions. Of course, if
you make the sensible switch to twos-complement, you'll regret having to
support the tdiv versions.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

More information about the gmp-discuss mailing list