On Fri, Dec 22, 2017 at 1:15 PM, <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.
It's not obvious to me that it's exactly 3 additional multiplications per reciprocal. Can you show me how to work this out? To compute reciprocals of A, B, and C, R = 1/ABC Then 1/A = RBC, 1/B = RAC, and 1/C = RAB So this looks like 8 multiplications. But when we computed ABC we could store the AB partial result, and then computing RAB takes only one more. And if we save RC when calculating RBC, we can reuse it when calculating RAC, so down to 6. So multiplications total, so the second saved reciprocal cost us 3 additional multiplications. How about the next one? R = 1/ABCD, 1/A = RBCD,1/B = RACD, 1/C = RABD, 1/D = RABC Again, naively this is 15 multiplications, but by reusing partial results, we can compute AB, ABC, ABCD, BC, BCD, RBCD, AC, ACD, RACD, ABD, RABD, RABC, or 12 multiplications, so it took us an extra 6. Maybe I could be cleverer in the intermediate results I calculate: AB, ABC, ABCD, CD, BCD, RBCD, ACD, RACD, ABD, RABD, RABC, so down to 11 multiplications, so now it only took an extra 5. Let's try yet again: AB, CD, ABCD, BCD, RBCD, ACD, RACD, ABD, RABD, ABC, RABC. still 11 multiplications. One more try: AB, CD, ABCD, RCD, RBCD, RACD, RAB, RABD, RACD. OK, I got down to 9 multiplications. Another possible order: AB, ABC, ABCD, RABC, RAB, RABD, CD, RCD, RACD, RBCD takes 10. Is there some easy way to see what the order of multiplications is that guarantees only 3 extra for each new reciprocal? Andy
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
-- Andy.Latto@pobox.com