gmp-devel Digest, Vol 1, Issue 89
tege at swox.com
Thu Sep 18 00:15:33 CEST 2003
[You might want to edit the subject and reply to just one subject
per message. It is hard to keep track of a thread otherwise, and
impossible to locate old messages by subject.]
Paul.Zimmermann at loria.fr (Paul Zimmermann) writes:
I suggest you first try your idea on Montgomery's multiplication,
where you *always* get the right "quotient".
We will also implement Montgomery, but since the problems there are
completely different, I think it isn't going to help much.
For the classical division, you could use the f-p unit to get a more
precise approximation of the quotient (on 32-bit machines). Also, the
next quotient limb mainly depends from the two top high limbs from the
mpn_submul_1, which may be computed apart.
We're not bothered at the moment with machines that use any
division instructions for mpn_divrem_1. We're optimizing it by
using pipelined integer (or fp) multiplication.
You might be talking about the case where the divisor is many
limbs (mpn_sb_divrem_mn). We're going to address that next, and
will make use of new parallel mpn_submul_2, mpn_submul_3, and
mpn_submul_4 for relevant machines.
And then Karl has written Newton/Barrett division for huge
More information about the gmp-devel