These might be helpful: http://ipa.ece.illinois.edu/mif/pubs/web-only/Frank-RawMemo12-1999.html https://homepage.divms.uiowa.edu/~jones/bcd/divide.html On Fri, Dec 22, 2017 at 11:15 AM, <rcs@xmission.com> wrote:
This is mostly for the old-timers.
Once upon a time, roughly <1965, division was expensive. Some computers even came without a Divide instruction, and had to use a subroutine. With floating point numbers, the division X/Y was sometimes done as X times 1/Y. A programming trick from that era came to be known as "one more reciprocal".
The idea of 1MR is to replace several reciprocal operations with a single one, minimizing the total execution time. The magic formula: Assume you need to compute 1/X and 1/Y. Compute R = 1/(XY), and then 1/X = RY and 1/Y = RX.
The idea extends to more reciprocals; potentially an arbitrary number of reciprocals can be replaced with a single one. Each avoided reciprocal costs an extra three multiplications. Whether this is worthwhile depends on the relative cost of Divide versus Multiplication, and some side costs: code complexity, storage, concern for over/underflow, and a slight loss of accuracy.
As division has cheapened, 1MR has mostly fallen out of use. 1MR is still used in modular arithmetic, where the relative costs favor it. Peter Montgomery introduced it for elliptic curve calculations c. 1985. It's also usable for matrices, if you are careful about non-commutativity.
There was a brief vogue for possible generalizations, perhaps when computing several square roots, or several multiplications -- a multiply can be replaced with two squarings. AFAIK, these didn't go anywhere.
I'm looking for some mention of 1MR, either in print or old memories. Google is unhelpful, and my Numerical Recipes is too recent.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com