Was division via reciprocal considered?
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
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
runtime out of your division.
Was this considered? Is it practical? Or obsolete? Are newer algorithms
like Barrett division better for some reason? I'm having a hard to coming
up with any direct comparison so I was wondering if anyone here had
More information about the gmp-discuss