Efficient division using binary math

508 Views Asked by At

I'm writing code for an FPGA and I need to divide a number by $1.024$. I could use floating and/or fixed point and instantiate a multiplier but I would like to see if I could do this multiplication more efficiently.

I noticed that $2^0$ + $2^-$$^6$ + $2^-$$^7$ = $1.0234375$ which is 99.95% of $1.024$; well within my tolerance requirement. It feels like there is some way I can take advantage of this fact to divide a number by $1.0234375$ (essentially $1.024$) without having to do costly multiplication but I'm stuck on where to go from here. I've seen similar types of things done by early game developers to speed up their calculations and this is essentially what I'm trying to accomplish here but instead of maximizing speed I want to minimize FPGA utilization.

1

There are 1 best solutions below

5
On BEST ANSWER

$$\frac{1}{1.024} = \frac{1024-24}{1024} = \left(\frac{1024 - 16 - 8}{1024}\right)$$

So to divide N,

$$ N*\left(\frac{1000}{1024}\right) = ((N << 10) - (N << 4) - (N << 3)) >> 10 $$

You need 2 adders. Shift operation will be free in FPGA as all are powers of 2. If you want to use fraction of the result, simply use lower 10 bits of the addition. For FPGA specific questions, you can always try electronics.SE