Working with the set of real numbers
Dave Angel
davea at davea.name
Wed Mar 5 14:32:30 CET 2014
Dave Angel <davea at davea.name> Wrote in message:
> Oscar Benjamin <oscar.j.benjamin at gmail.com> Wrote in message:
>> On 4 March 2014 23:20, Dave Angel <davea at 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
More information about the Python-list
mailing list