gmp-devel Digest, Vol 1, Issue 89

[Torbjorn Granlund]

[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
operands.

-- 
Torbjörn