What is the fastest way to perform hardware division of an integer by a fixed constant?

Question

I have a 16 bit number which I want to divide by 100. Let's say it's 50000. The goal is to obtain 500. However, I am trying to avoid inferred dividers on my FPGA because they break timing requirements. The result does not have to be accurate; an approximation will do.

I have tried hardware multiplication by 0.01 but real numbers are not supported. I'm looking at pipelined dividers now but I hope it does not come to that.

Answer 1

Conceptually: Multiply by 655 (= 65536/100) and then shift right by 16 bits. Of course, in hardware, the shift right is free.

If you need it to be even faster, you can hardwire the divide as a sum of divisions by powers of two (shifts). E.g.,

1/100 ~= 1/128                  = 0.0078125
1/100 ~= 1/128 + 1/256          = 0.01171875
1/100 ~= 1/128 + 1/512          = 0.009765625
1/100 ~= 1/128 + 1/512 + 1/2048 = 0.01025390625
1/100 ~= 1/128 + 1/512 + 1/4096 = 0.010009765625
etc.

In C code the last example above would be:

uint16_t divideBy100 (uint16_t input)
{
    return (input >> 7) + (input >> 9) + (input >> 12);
}

Answer 2

Assuming that

• the integer division is intended to truncate, not round (e.g. 599 / 100 = 5)
• it's ok to have a 16x16 multiplier in the FPGA (with a fixed value on one input)

then you can get exact values by implementing a 16x16 unsigned multiplier where one input is 0xA3D7 and the other input is your 16-bit number. Add 0x8000 to the 32-bit product, and your result is in the upper 10 bits.

In C code, the algorithm looks like this

uint16_t divideBy100( uint16_t input )
{
    uint32_t temp;

    temp = input;
    temp *= 0xA3D7;     // compute the 32-bit product of two 16-bit unsigned numbers
    temp += 0x8000;     // adjust the 32-bit product since 0xA3D7 is actually a little low
    temp >>= 22;        // the upper 10-bits are the answer

    return( (uint16_t)temp );
}

Answer 3

Generally, you can multiply by the inverse and shift. Compilers do this all the time, even for software.
Here is a page that does that for you: http://www.hackersdelight.org/magic.htm
In your case that seems to be multiplication by 0x431BDE83, followed by a right-shift of 17.

And here is an explanation: Computing the Multiplicative Inverse for Optimizing Integer Division