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\$
3
  • \$\begingroup\$ [self promotion]I wrote a bit about non-restoring signed and unsigned division. It's fairly complex : temlib.org/site/?p=351 \$\endgroup\$ – TEMLIB Apr 9 '19 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 '19 at 20:00
  • \$\begingroup\$ Can your substractor substract -1 to add +1? \$\endgroup\$ – bobflux May 8 at 13:33
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 '19 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 '19 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 '19 at 4:15
  • \$\begingroup\$ That's not the case on the x86. \$\endgroup\$ – anrieff Apr 10 '19 at 6:53

Your Answer

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

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