I'd wager
"long division" sets many scratching their heads...
Now, what about
non-restoring long division?
What's that?
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)
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
