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

From: der Mouse <mouse_at_Rodents.Montreal.QC.CA>
Date: Thu Jun 24 00:06:37 2004

>>>> 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_at_rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
Received on Thu Jun 24 2004 - 00:06:37 BST