Joe Mickley wrote:
> I am using a dsPIC30F3012 (writing in ASM, not C) on a project with very
> fast loop execution (<20 uSec in some cases)
> and need an effecient 32 bit by 32 bit unsigned divide algorithm.  The
> dsPIC30F family has organic 16 by 16 divide
> instruction (DIV.U and DIV.UD) and I would like to create a 32 by 32 usin=
g
> that instruction set.

Unlike multiplication, it is not possible to "compose" a large divide
operation from smaller ones.

One way to do a fast divide when you have a fast multiplier available (the
dsPIC has a single-cycle 17x17 mutliplier) is to compute the reciprocal of
the divisor using the Newton-Raphson method
(http://en.wikipedia.org/wiki/Newton%27s_method) and then multiply the
dividend by that.

> The traditional 32 by 32 divide using a shift/subtract (restoring)
> algorithms is slow (about 400 instruction cycles nominal). It
> should be possible to break the 32 by 32 into a set of 16 by 16 operation=
s,
> then combine the partials back into a 32 by 32
> result, but I lack the knowledge of how to do or drive this.  The dsPIC30=
F
> divide routine is fast (18 cycles, so
> any use of itshould have a marked improvement)

You might also consider implementing a "traditional" restoring/nonrestoring
divide in a radix other than 2; i.e., compute 4 (base 16) or 8 bits (base 2=
56)
of the result at a time. Again, having a hardware mulitplier at your dispos=
al
helps accelerate this.

If you want the ultimate speed, consider adding a hardware coprocessor. A
smallish CPLD should be able to implement a base-2 32-bit divide in a littl=
e
more than 32 clock cycles. And if you like, I could sell you a fully-pipeli=
ned
VHDL module for an FPGA that produces a new result on every tick of a 150 M=
Hz
clock (originally designed for real-time HD video processing).

-- Dave Tweed
--=20
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
.