1

From what I have seen, division is a highly expensive operation in terms of time or area (tradeoff). It is usually implemented as an operation of continuous subtraction of a number from another number to get the quotient bits.

While I understand how addition, subtraction and multiplication are implemented, there is some confusion surrounding division. I have 3 interrelated questions.

Q1: If division is merely recursion of subtractions until we are left with remainder, how would one get a fixed point output i.e output with both integer and fraction parts; since an integer quotient represents how many times we did subtraction in a loop.

Q2: How would one deal with recurring decimal numbers as quotient? I assume through round-off i.e we do not care if result is recurring decimal or not, we just calculate the result to certain digits of fractional part.

Q3: Provided that I have a divider IP that outputs remainder and quotient, how would I get the fractional part of the output since the remainder does not actually equal the fractional part?

quantum231
  • 11,218
  • 24
  • 99
  • 192
  • Is this a hardware question? (Sounds like a software one, but the title makes me unsure.) The rest reads to me as though you are struggling to write code to generate a display-formatted decimal value, with a decimal point and fractional digits. Not a real division-only question. What's the purpose here? Why are you asking these particular questions? What's the goal? – jonk Nov 29 '16 at 07:03
  • I want to understand how to carry out division with specific precision i.e fixed point division. I have an IP block in Quartus ii called lpm_div that gives quotient and remainder. However, it is not clear how to get fractional part of quotient to specific decimal places. – quantum231 Nov 29 '16 at 09:26
  • Where at all possible, I would try to implement your division as a multiplication by the reciprocal of the denominator. Alternatively, arrange things so that any divisions are by a power of two. – scary_jeff Dec 02 '16 at 12:25

1 Answers1

1

I don't know anything about that IP block. But since you don't yet have a better answer (mine won't be all that good), I'll offer some general advice. I'll draw on some vague assumptions I'll make:

  • You can define the width of the numerator and denominator, separately.
  • You can define the width of the quotient and remainder, separately.

I usually normalize both the numerator and denominator using a barrel shifter prior to any division. This counts the number of shifts required and I save those aside. As a result of this step: \$2\cdot denominator > numerator \ge \tfrac{1}{2}\cdot denominator\$.

Assume that the significant bits of your numerator are the same size as the denominator. But also consider a numerator width to the IP block that is twice the size of the denominator. The above normalized numerator is placed in the upper half of the double-width bus. You make a comparison. If the denominator is larger then shift the widened numerator down by one bit. This will guarantee that your quotient will fit in the same width as the denominator.

The upshot of the above is that the numerator bus width is twice that of the other three. An incoming numerator is placed in the upper half, but may be shifted down one bit. Both numerator and denominator are normalized, prior to division.

But let's say you don't use a barrel shifter and don't care to normalize. Then consider setting the numerator width of the IP block at twice the width of the other three. Your external numerator then goes into the upper half of that width (lane shift) and zeros always go into the lower half (optimize the logic for that case.)

Then the fractional part simply using the same divider but now by taking the resulting remainder and dividing it by the original divisor you used before.

You really haven't provided enough information AND I'm also ignorant of your IP block. So that's the best I can offer. Hopefully, someone else will do better.

jonk
  • 77,059
  • 6
  • 73
  • 185