Multiplying 23 bit datatypes in a system with no long long

Question

I am trying to implement floating point operations in a microcontroller and so far I have had ample success.

The problem lies in the way I do multiplication in my computer and it works fine:

unsigned long long gig,mm1,mm2;
unsigned long m,m1,m2;
mm1 = f1.float_parts.mantissa;
mm2 = f2.float_parts.mantissa;

m1 = f1.float_parts.mantissa;
m2 = f2.float_parts.mantissa;



gig = mm1*mm2; //this works fine I get all the bits I need since they are all long long, but won't work in the mcu

gig = m1*m2//this does not work, to be precise it gives only the 32 least significant bits , but works on the mcu

So you can see that my problem is that the microcontroller will throw an undefined refence to __muldi3 if I try the gig = mm1*mm2 there.

And If I try with the smaller data types, it only keeps the least significant bits, which I don't want it to. I need the 23 msb bits of the product.

Does anyone have any ideas as to how I can do this?

Answer 1

Apologizes for the short answer, I hope that someone else will take the time to write a fuller explanation, but basically you do exactly as when you multiply two big numbers by hand on a paper! It's just that instead of working with base 10, you work in base 256. That is, treat your numbers as a byte vectors, and do with each byte what you do to a digit when you "hand multiply".

Answer 2

Back on the Intel 8088 (the original PC CPU and the last CPU I wrote assembly code for) when you multiplied two 16 bit numbers (32 bits? whoow) the CPU would return 2 16 bit numbers in two different registers - one with the 16 msb and one with the lsb.

You should check the hardware capabilities of your micro-controller, maybe it has a similar setup (obviously you'll need the code this in assembly if it does).

Otherwise you'll have to implement multiplication on your own.

Answer 3

The comments in the FreeBSD implementation of __muldi3() have a good explanation of the required procedure, see muldi3.c. If you want to go straight to the source (always a good idea!), according to the comments this code was based on an algorithm described in Knuth's The Art of Computer Programming vol. 2 (2nd ed), section 4.3.3, p. 278. (N.B. the link is for the 3rd edition.)