Was division via reciprocal considered?

AllUltima1 . allultima1 at gmail.com
Mon Oct 5 09:38:30 UTC 2015

```I was wondering if you guys had considered dividing via a multiplicative
inverse (reciprocal), which some have considered to be the best way. I
reviewed
https://gmplib.org/manual/Division-Algorithms.html#Division-Algorithms and
it seems like it isn't used, but I wanted to know why not.

On page 312 of "Art of Computer Programming, Volume 2: Seminumerical
Algorithms", Knuth provides "Algorithm R" which is a high-precision
reciprocal. It provides a value of the form [0.n1n2n3...] which you would
multiply by in order to achieve division. Although it is an "approximate"
method, Knuth provides a proof that it is "accurate enough" for integer
division to be flawless.

Knuth says the time spent calculating the inverse is not asymptotically
significant... he says "so division can be calculated at a speed comparable
to multiplication except a constant factor". In other words, if you were
using Schönhage-Strassen for multiplication, you'd get the same asymptotic