Dave Angel <da...@davea.name> Wrote in message: > Oscar Benjamin <oscar.j.benja...@gmail.com> Wrote in message: >> On 4 March 2014 23:20, Dave Angel <da...@davea.name> wrote:
>>> >>> If anyone is curious, I'll be glad to describe the algorithm; >>> I've never seen it published, before or since. I got my >>> inspiration from a method used in mechanical, non-motorized, >>> adding machines. My father had shown me that approach in the >>> 50's. >> >> I'm curious. >> > > A later message, I guess. I can't write that much on the tablet. > > Given a microcodable architecture with no hardware support for multiply or divide, clearly multiply will be several times as fast as divide (at least).  There was a BCD ALU, so add and subtract of decimal values was quite reasonable.  All floating point logic, however, is just microcode. Divide is implemented via repeated subtraction of the divisor from the dividend.  The count of how many subtracts is done is the quotient. Naturally, this is combined with digit shifts, so you find one quotient digit at a time.  For a 13 digit result, the maximum subtracts are 13*10. Multiply is much faster, as you know ahead of time for each column how many adds you're supposed to do.  So you can have precalculated multiples of the divisor on hand, and you can subtract instead of add when appropriate. Square root is implemented as a kind of variable division, where the "divisor" is changing constantly.  Everyone knows that the sum of the first n odd numbers is n squared.  So if you started with a square, you could repeatedly subtract odd numbers from it till you reached zero, and the square root will be roughly half the last odd number subtracted. So to make this work across multiple columns it turns out you can accumulate these odd numbers, doing the appropriate shifts after each column, and if you take the last number shifted, you can just add 1 and divide by 2. In many architectures, that would be as far as you can go, but in the particular one I was using, generating those pesky odd numbers was more expensive than you'd expect.  So it turned out to be quicker to just do twice as many subtracts. Instead of subtracting 1,3, 5, etc., till the value went negative, we subtract 0 and 1, 1 and 2, 2 and 3, etc.  You have twice as many subtracts, but no divide by 2 at the end.  And for each column, you need not go beyond 8 + 9, since if it were more than that, we would have picked it up in the previous column.  So you do not have to propagate the carry across the trial divisor. Supposing the correct result will be 7.1234567, you will at one stage of operations, be subtracting     71230     71231     71231     71232     71232     71233     71233     71234 The next subtract will make the result go negative, so you either do it, detect negative and undo it, or you do some compare operation. I am here glossing over all the details of normalizing the dividend so the exponent is even, and calculating the final exponent, which at first approximation is half the original one. -- DaveA
-- https://mail.python.org/mailman/listinfo/python-list