Fixed-point multiplication without temporary 64-bit

Question

Hi, I am implementing some fixed-point math for embedded systems, and I am trying to do the multiplication of two fixed-point numbers 16.16 without creating a 64-bit temporary. So far, here is the code I came up with that generates the smallest instructions.

int multiply(int x, int y){ int result; long long temp = x; temp *= y; temp >>= 16; result = temp; return result; } 

the problem with this code is that it uses a temporary 64-bit integer, which seems to produce bad build code. I'm trying to create a system that uses two 32-bit integers instead of 64-bit. Does anyone know how to do this?

Answer 1

Think about your numbers, each of which consists of two large "numbers".

  AB x CD 

The "base" of the digits is 2 ^ bit_width, i.e. 2 ^ 16 or 65536.

So the product

 D*B + D*A*65536 + C*B*65536 + C*A*65536*65536 

However, to get the product offset by 16, you need to divide all these terms by 65536, so

 D*B/65536 + D*A + C*B + C*A*65536 

In C:

 uint16_t a = x >> 16; uint16_t b = x & 0xffff; uint16_t c = y >> 16; uint16_t d = y & 0xffff; return ((d * b) >> 16) + (d * a) + (c * b) + ((c * a) << 16); 

The signed version is a little more complicated; it is often easier to do arithmetic on the absolute values ​​of x and y , and then fix the sign (if you don't overflow, which you can check is pretty tedious).