0
\$\begingroup\$

I figured a way to implement a fast divider (basically a ripple-carry divider) with deterministic delay, but it's stupidly-large, essentially requiring two AND gates (multiplier and a position test to line up the divisor and the dividend properly) and a full adder for half of n×n (to add the results of multiplication). It's essentially a combinational (i.e. unrolled) implementation of the below algorithm by Jain, Pancholi, Garg, and Saini:

Paravartya

In practice, the circuit would quickly grow so large as to have a relatively-high delay, so would be broken down into stages to avoid a low clock rate in e.g. a CPU or ALU. By pipelining the divider, you can put in one input per clock, and obtain a deterministic output with quotient and remainder once per clock; whereas if you're saving area, it wouldn't be pipelined, but would be a state machine and would remain busy until finished with the single division calculation several clock cycles later.

A single stage is two AND gates and a full adder for each bit of output, plus intermediate register to maintain state; a single asynchronous circuit has what amounts to ever-shorter horizontal ripple carry dividers at each stage feeding a vertical ripple-carry divider, so has the delay of e.g. a 64-bit ripple carry adder for 64x64 division. This doesn't seem to justify having what amounts to 64 ripple-carry adders running in parallel (at stage m, you need (n-m) full adders horizontally, and n-(n-m) full adders vertically).

The critical path would be 2 ripple-carry adders:

           1          2          3
X X X X X  C X X X X  C C X X X  C C C X X
  X X X X    X X X X    X X X X    C X X X
    X X X      X X X      X X X      X X X
      X X        X X        X X        X X
        X          X          X          X

4          5          6          7
C C C C X  C C C C C  C C C C C  C C C C C
  C C X X    C C C X    C C C C    C C C C
    X X X      C X X      C C X      C C C
      X X        X X        X X        C X
        X          X          X          X

8          9
C C C C C  C C C C C
  C C C C    C C C C
    C C C      C C C
      C C        C C
        X          C

It's still huge. Does anyone even use integer division? Is a combinational approach worthwhile, or is an iterative approach better for a general-purpose CPU?

\$\endgroup\$
9
  • \$\begingroup\$ Of course people use integer division. Whether a particular approach is "worthwhile" or "better" is a complex economic question, unless you would like to specify your criteria for "goodness". You should try to make your analysis relevant to modern techniques for implementing logic...no one has designed with actual AND gates for decades...so your estimate of gate count is probably not valid. \$\endgroup\$ Apr 20 '20 at 15:52
  • \$\begingroup\$ Fair enough, but you rarely see a DIV instruction in most code; tight-loop code with DIV seems unlikely, but I don't know. You're right about gate count (although an AND or OR gate is a single transistor, and XOR is two). \$\endgroup\$
    – John Moser
    Apr 20 '20 at 16:09
  • \$\begingroup\$ @JohnMoser you haven't indicated why you wouldn't use an MCU to implement this. Is there a really high clock rate? \$\endgroup\$
    – scorpdaddy
    Apr 20 '20 at 16:55
  • \$\begingroup\$ If you wanted to ask about the frequency of using a DIV instruction you should not have asked a yes/no question. And please elaborate on how you are building AND and OR gates with single transistors. \$\endgroup\$ Apr 20 '20 at 17:19
  • \$\begingroup\$ If you write fast code you try to avoid division, even to the extend that you multiply by the reciprocate if it is a constant. But you can't always avoid it. However more and more CPUs implement integer division. A prime example is the ARM cortex M3 (one of my favorites) which has SDIV and UDIV opcodes. These takes between 2 and 12 clock cycles. So they are very efficient! \$\endgroup\$
    – Oldfart
    Apr 20 '20 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.