# query: nearest integer divide

**Jason Moxham
**
j.l.moxham@maths.soton.ac.uk

*Mon, 24 Mar 2003 11:54:45 +0000*

On Monday 24 Mar 2003 10:59 am, Torbjorn Granlund wrote:
>* [Let's try again. Last reply had some typos that made it hard to
*>* understand.]
*>*
*>* keith.briggs@bt.com writes:
*>*
*>* 1. mpz_ui_pow_ui(temp,2,p-1);
*>* mpz_add(y,x,temp);
*>* mpz_tdiv_q_2exp(y,y,p);
*>*
*>* It would save a lot of time to perform that mpz_ui_pow_ui with
*>* mpz_mul_2exp instead. That would bring time down from O(M(2^p)) to
*>* O(2^p), where M(n) is the time for multiplying two n-bit numbers.
*>*
*>* (If your x is computed for the sole purpose of getting this
*>* nearest integer, you might be able to save a great amount of time
*>* by not computing the full precision of x, and instead just some
*>* upper part of it.)
*
Assuming the x is needed only for getting this nearest integer I have found
the papers below to be useful
On computing short products , Thom Mulders , Technical Report No 276
Department of Computer Science ETH Zurich , Nov 1997
www.inf.ethz.ch/research/publications/data/tech-reports/2xx/276.ps
Efficient Multiprecision Floating point Multiplication with exact rounding ,
Werner Krandick , Jeremy R Johnson
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-74.ps.gz
Detecting Perfect Powers in essentially linear time , Daniel J Bernstein
http://cr.yp.to/papers.html