I am looking for an algorithm to multiply and divide fixed point 15.16 numbers.
I already have addition and subtraction. Those were easy - simple 32-bit add and subtract. With multiply and divide, I can also add many trigonometric and exponential/log functions. And I think I can deal with just multiply, as my library has a reciprocal function and I can use that to implement division: a * (1/b) = a / b. But a 32-bit multiply does not work as it ignores the radix point.
I am working on a 16-bit microcontroller, so I would like to avoid anything more than 32-bit multiply, which takes about 4 cycles on my processor. It's not crucial though, I'm just trying to replace floating point math.
I have heard I need to shift or rotate the result, but I am not sure how this would help or specifically how to shift it. Any suggestions or help appreciated!
Think of is this way: your number a.b is represented as (a.b * 65536)
If you multiply a.b * c.d the value you get is (a.b * 65536) * (c.d * 65536), so to put this back in the right representation you need to divide by 65536.
When you divide a.b / c.d the value you get is (a.b * 65536) / (c.d * 65536), so to put this back in the right representation you need to multiply by 65536. You should multiply by 65536 before the divide to preserve as many bits as possible in the result.
Of course you can substitute (<< 16) for (* 65536) if that is faster on your processor. Similarly you can substitute (>> 16) for (/ 65536).
Here's a.b * c.d:
uint32_t result_low = (b * d);
uint32_t result_mid = (a * d) + (b * c);
uint32_t result_high = (a * c);
uint32_t result = (result_high << 16) + result_mid + (result_low >> 16)