Search code examples
cinteger-arithmetic

How to rescale an int using two possibly bigger numbers in (a*X)/b formula

I have a formula in c that looks like this:

X = (a * X) / b;

This is used to rescale X with a/b. However X is 16 bit unsigned int and multiplication with a could easily overflow. How could I do this calculation using just integers with an accurate result.

I could of course use floating point arithmetic, but there is a high chance this operation will work on a processor without floating point hardware.

EDIT: I forgot to say that a and b are both 32 bit unsigned integers. Well my answer was to rightshift a and b until they both fit in 16 bits. That way a * X is 32 bits max and the final calculation is accurate.

Solution

  • You can promote a to a bigger data type, for example:

    X = ((long)a * X) / b;