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

From: Peter C. Wallace <pcw_at_mesanet.com>
Date: Thu Jun 24 10:28:46 2004

On Thu, 24 Jun 2004, der Mouse wrote:

> >>>> 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)

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)


>
> 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
>

Peter Wallace
Mesa Electronics
Received on Thu Jun 24 2004 - 10:28:46 BST