2
\$\begingroup\$

I've implemented a division algorithm on an FPGA using the long division algorithm. My implementation does not use pipelining, but works iteratively and requires very few logic elements since the algorithm mainly consists of a single subtraction and some shift registers.

For a signed version of the component I just use the absolute values of the inputs and negate the result as required. This works as expected, but negating two's complement numbers does require adding '1' after inverting all bits, which results in 3 full adders in the design. This results in roughly twice as many logic elements for a signed divider compared to an unsigned one.

Is there a way to adjust the long division algorithm, so it directly works with negative numbers? I've already figured out that I can include the '+1' for the denominator during the main subtraction by using a borrow bit. I haven't found out how to handle the numerator or how to directly produce a result with the correct sign.

\$\endgroup\$
4
  • \$\begingroup\$ [self promotion]I wrote a bit about non-restoring signed and unsigned division. It's fairly complex : temlib.org/site/?p=351 \$\endgroup\$
    – Grabul
    Apr 9, 2019 at 19:48
  • \$\begingroup\$ Add one more state to your controller and re-use the adder you already have in an extra cycle to do the extra increment? \$\endgroup\$
    – The Photon
    Apr 9, 2019 at 20:00
  • 2
    \$\begingroup\$ Can your substractor substract -1 to add +1? \$\endgroup\$
    – bobflux
    May 8, 2021 at 13:33
  • \$\begingroup\$ Without a block diagram or essential parts of the VHDL code it is hard to follow why you would need more than one adder/subtracter. An incrementer does not need a full adder. \$\endgroup\$
    – greybeard
    Jan 20, 2023 at 6:46

1 Answer 1

0
\$\begingroup\$

I don't think you can get away without more logic gates. Consider 16-bit signed divider:

  • -16384 / -1 = 16384
  • -32768 / -1 = overflow

(-32768 is a valid two's complement 16-bit signed integer).

It's situations like this when microcode seems very alluring...

\$\endgroup\$
4
  • \$\begingroup\$ I'm (currently) not concerned with the difference in bit width. When converting 16-bit signed values to unsigned I still use 16 bits. I'm more interested in avoiding these costly conversions/negations. \$\endgroup\$
    – sebi707
    Apr 9, 2019 at 19:38
  • \$\begingroup\$ Yes, but you cannot represent your (signed) output. It does not matter what sort of trickery you use to avoid those costly conversions/negations, because the result doesn't fit in the output register, unless you make it one bit larger. \$\endgroup\$
    – anrieff
    Apr 9, 2019 at 20:35
  • \$\begingroup\$ Typically -32768 / -1 = -32768 (i.e. it's allowed to overflow even though it gives the wrong answer) \$\endgroup\$
    – user253751
    Apr 10, 2019 at 4:15
  • \$\begingroup\$ That's not the case on the x86. \$\endgroup\$
    – anrieff
    Apr 10, 2019 at 6:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.