Modern Electronics (was Re: List charter mods & headcount... ;

From: Tony Duell <ard_at_p850ug1.demon.co.uk>
Date: Wed Jun 23 23:17:08 2004

> >> I'd wager "long division" sets many scratching their heads...
> > Now, what about non-restoring long division?
>
> What's that? "Restoring" is not an adjective I know of any meaning for
> when attached to "log division". (I may know the referent, of course;
> I'm just sure I don't know the reference.)

It's a way of saving half an ALU operation per bit on average. I'll try
to explain it in binary (although it works in any base, and a friend of
mine has a mechanical calculator which does something similar in base 10).

OK, think of the normal long division algorithm :

Compare the divisor with the (shifted) remainder from the last time round
the loop. (1st ALU operation, a compare)

If it's divisor larger, append a 0 to the RH end of the quotient

If it's smaller, subtract the dvisior from the remainder, then append a 1
to the RH end of the quotient (2nd ALU operation, a possible subtract,
occurs half the time on average).

Shift the remainder left one bit (this is equivalent to moving the
divisor right one bit, of course, but reduces the size of the ALU you to
that of the divisor, not the dividend).

So on average 1.5 ALU operations per bit.

Now for the 'magic'.

The following is obviously equivalent :

Subtract the divisor from the remainder (the result may well be -ve here,
of course)

[I want to put LABEL A here, for a reason I'll explain below]

If the result is -ve, then you really shouldn't have done that
subtraction. Add the divisor back (this is the 'restoring' part), append
a 0 to the RH end of the quotient.

If the result is +ve, you should have done the subtraction. Leave the
remained alone, append a 1 to the RH end of the quotient

Shift the remainder left one bit (as above).

Now consider what happens to the remainder (let's call it R) as we go
round the loop form LABEL A to LABEL A (note this is not the start of the
loop as I've given it).

If the quotient bit is a 1 :
R := 2*R ; (that's the left shift by 1 bit)
R := R-D ; (that's the subtact at the start of the next loop)

So overall R := 2*R-D

If the quotient bit is a 0 :
R := R+D ; (restoration)
R : = 2*R ; (left shift)
R : = R-D ; (Subtract at the start of the next loop)

And overall R := 2*(R+D) - D, or R := 2*R + D

So this gives another algorithm :

If the result of the previous subtraction was +ve, append a 1 to the RH end
quotiend and subtract the divisor from the remainder

If the result of the pevious subtraction was -ve, append a 0 to the RH
end of the quotient and add the divisor to the remainder

Shift the remainder left one bit

(Oh, and always start by doing a subtraction).

This takes 1 ALU operation per bit.


 


>
> >>> How many even know the square root of 2 and 3?
> >> 2.236+ ;-)
> > No, that's the square root of 2+3.
>
> ...which is one of the possible meanings of the text quoted.

I know, I was being a little eccentric :-)

-tony
Received on Wed Jun 23 2004 - 23:17:08 BST