Fast method to multiply integer by proper fraction without floats or overflow

Question

My program frequently requires the following calculation to be performed:

Given:

• N is a 32-bit integer
• D is a 32-bit integer
• abs(N) <= abs(D)
• D != 0
• X is a 32-bit integer of any value

Find:

• X * N / D as a rounded integer that is X scaled to N/D (i.e. 10 * 2 / 3 = 7)

Obviously I could just use r=x*n/d directly but I will often get overflow from the x*n. If I instead do r=x*(n/d) then I only get 0 or x due to integer division dropping the fractional component. And then there's r=x*(float(n)/d) but I can't use floats in this case.

Accuracy would be great but isn't as critical as speed and being a deterministic function (always returning the same value given the same inputs).

N and D are currently signed but I could work around them being always unsigned if it helps.

A generic function that works with any value of X (and N and D, as long as N <= D) is ideal since this operation is used in various different ways but I also have a specific case where the value of X is a known constant power of 2 (2048, to be precise), and just getting that specific call sped up would be a big help.

Currently I am accomplishing this using 64-bit multiply and divide to avoid overflow (essentially int multByProperFraction(int x, int n, int d) { return (__int64)x * n / d; } but with some asserts and extra bit fiddling for rounding instead of truncating).

Unfortunately, my profiler is reporting the 64-bit divide function as taking up way too much CPU (this is a 32-bit application). I've tried to reduce how often I need to do this calculation but am running out of ways around it, so I'm trying to figure out a faster method, if it is even possible. In the specific case where X is a constant 2048, I use a bit shift instead of multiply but that doesn't help much.

Answer 1

Tolerate imprecision and use the 16 MSBits of n,d,x

Algorithm
while (|n| > 0xffff) n/2, sh++
while (|x| > 0xffff) x/2, sh++
while (|d| > 0xffff) d/2, sh--
r = n*x/d  // A 16x16 to 32 multiply followed by a 32/16-bit divide.
shift r by sh.

When 64 bit divide is expensive, the pre/post processing here may be worth to do a 32-bit divide - which will certainly be the big chunk of CPU.

If the compiler cannot be coaxed into doing a 32-bit/16-bit divide, then skip the while (|d| > 0xffff) d/2, sh-- step and do a 32/32 divide.

Use unsigned math as possible.