24 Jun
2004
24 Jun
'04
3:28 a.m.
On Thu, 24 Jun 2004, der Mouse wrote:
It's a
way of saving half an ALU operation per bit on average.
Well, if you're doing it in a real CPU...
while (appropriate condition)
Subtract the divisor from the shifted remainder
If the result is
positive or zero
replace the remainder with it
shift a 1 bit into the quotient
negative
shift a 0 bit into the quotient
Shift the remainder left one bit (possibly shifting in a new
dividend bit if the dividend is wider than the divisor)
This is a simple way to do divide on a FPGA since the carry chain is fast and
conditionally loading a register is easy...
There are faster divide routines that calculate more than a bit at a time (SRT
dividers for example)
> I'd
wager "long division" sets many scratching their heads...
Now, what about non-restoring long division?
What's that?
Functionally equivalent. It does require either a register to hold the
difference or the ability to block/permit the store based on the sign
bit of the difference, which presumably isn't an issue if you're
designing the silicon. :-) The algorithm you gave requires one bit of
storage to remember the result of the previous subtract, which may be
easier or harder than the gated store, depending....
Of course, if this is for doing division in software on a machine that
doesn't have it, then that doesn't apply - but in that case, you
probably care more about clock cycles than ALU operations per se.
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse(a)rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Peter Wallace
Mesa Electronics