gmp-discuss digest, Vol 1 #111 - 2 msgs

Paul Zimmermann
Mon, 24 Mar 2003 13:56:20 +0100

   I have an application where I have a large mpz_t x, and a long p,
   and I want to compute the nearest integer y to x/2^p.   It seems I have
   two obvious ways:

   1. mpz_ui_pow_ui(temp,2,p-1);

   2. or, compute the quotient and remainder (this seems to need separate
   calls in gmp with the 2exp functions), and check the size of the remainder 
   compared to the divisor.

   Does anybody have any knowledge about which method is faster, or perhaps
   an idea for another method?

I would propose the following:

/* rop <- op/2^p, rounded to nearest (rounding away when middle) */
mpz_ndiv_q_2exp (mpz_t rop, mpz_t op, unsigned long p)
   if (p != 0)
         int rnd_bit = mpz_tstbit (op, p - 1);
         int sgn = mpz_sgn (op);

         mpz_tdiv_q_2exp (rop, op, p);
         if (rnd_bit)
            mpz_add_si (rop, rop, (sgn > 0) ? 1 : -1);

Paul Zimmermann