Working with the set of real numbers

[Dave Angel]

 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