5
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Isn't $2^0 + 2^6 + 2^7 = 193$?? $\endgroup$
    – Nathaniel Bubis
    Commented Oct 24, 2013 at 1:58
  • $\begingroup$ @nbubis Thank you, I left out the proper signs, fixed $\endgroup$
    – SiegeX
    Commented Oct 24, 2013 at 2:10
  • 5
    $\begingroup$ Not sure what the efficient operations are for FPGAs, but if you can support shifting and addition then $x / 1.024$ is the same as $125x/128 = x - \text{shiftright}(x, 5) + \text{shiftright}(x,7)$. $\endgroup$
    – Erick Wong
    Commented Oct 24, 2013 at 2:30
  • $\begingroup$ Isn't multiplication cheap on most hardware? Division's the one that tends not to be. $\endgroup$
    – dfeuer
    Commented Oct 24, 2013 at 2:32
  • 1
    $\begingroup$ @ErickWong This is exactly what I'm looking for. If you could create a bonafide answer that explains how you came up with your answer I will certainly accept it. Thank you! $\endgroup$
    – SiegeX
    Commented Oct 25, 2013 at 18:35

1 Answer 1

Reset to default
5
$\begingroup$

$$\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

$\endgroup$
5
  • $\begingroup$ Thank you, shifting is exactly what I'm looking to do because as you say, it's a free operation in FPGA. $\endgroup$
    – SiegeX
    Commented Oct 25, 2013 at 21:21
  • 3
    $\begingroup$ Just a bit of an update. Using this trick I was able to save two DSP48 multipliers from being used. Considering this FPGA only has 68 of them, that is significant to me. $\endgroup$
    – SiegeX
    Commented Oct 26, 2013 at 0:48
  • $\begingroup$ @SiegeX, that's cool. $\endgroup$
    – mj6174
    Commented Oct 26, 2013 at 15:36
  • $\begingroup$ Nice to hear, @SiegeX! I just wanted to add that the first line is unnecessarily modest: the left and right end-values are exactly equal so there's no need for the intermediate approximations. $\endgroup$
    – Erick Wong
    Commented Oct 26, 2013 at 17:15
  • $\begingroup$ @ErickWong You are right. Its cleaner this way. $\endgroup$
    – mj6174
    Commented Oct 26, 2013 at 18:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .