Think of your numbers as each composed of two large "digits."
A.B
x C.D
The "base" of the digits is the 2^bit_width, i.e., 2^16, or 65536.
So, the product is
D*B + D*A*65536 + C*B*65536 + C*A*65536*65536
However, to get the product shifted right 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 bit more complicated; it is often easiest to perform the arithmetic on the absolute values of x
and y
and then fix the sign (unless you overflow, which you can check for rather tediously).