Help multiplying numbers..

[bobdole11122]

I am using an assembly language for a chip that is only able to multiply two 16 bit numbers at a time. I have to multiply two 24 bit numbers and I am trying to find the best way to do this. If anyone has an algorithm to do this using basic functions such as storing and adding with carry I would appreciate it.

[Jeff Reid]

If there is a unsigned multiply that outputs a 32 bit number you can use a longhand approach:


a b
c d
---------
ad bd
ac bc
----------------
ac ad+bc bd


If not, you'll need to seperate each number into three 8 bit parts to use cpu's multiply and use a similar long hand method. There are more complicated algorigthms that work with large numbers.

http://www.apfloat.org

[bobdole11122]

long hand would work fine, but I'm not sure on the proper sequence. I have two 24-bit numbers that need to be multiplied. Do you have a chart like the one above you posted for this? So the final product would be 6-bytes.

[Mark44]

Since your chip can multiply two 16-bit numbers, I'm assuming there is a register than can store a 32-bit result. You can use the longhand approach that Jeff Reid showed. His variables a, b, c, and d are as follows in your problem:
a holds bits 23 - 16
b holds bits 15 - 0 of one multiplicand.

c holds bits 23 - 16
d holds bits 15 - 0 of the other multiplicand.

The value you get for bd will go into the low 16 bits of your result. The value you get for ac will go into the high 16 bits of your result.

The values for ad and bc need to be split up, with the high 16 bits of each being added to ac, and the low 16 bits being added to bd.

Hope that helps.

[bobdole11122]

I am sorry but my micro controller only has 16bit registers, two 8bit registers A and B that are concatenated to make 16bit register D, and two 16bit registers x and y.

When the multiplication operation is performed between say y and d. it stores the answer in y:d, where d is concatenated with y.

This is what is making my problem difficult for me. It seems that the previous chart would work I am just not entirely sure how it is suppose to play out. I am content in doing long multiplication but I am just confused on how exactly to handle the carry and how to end up with the final 6byte product.

[Mark44]

So how then can your MC do a multiplication of two 16-bit numbers?

I am using an assembly language for a chip that is only able to multiply two 16 bit numbers at a time.

Did you mean that the chip could multiply two 8-bit numbers? If that's the case, your long multiplication is going to look like
a...b...c
d...e...f
--------
and you will have 9 partial products.

[Jeff Reid]

Going back to my example, if ac is non-zero you have an overflow condition. You end up with three 32 bit products. bd, ad, and bc. If the upper 16 bits of ad or bc are non-zero you have an overflow condition. Add the 16 bit values ad+bc, if you have a carry you have an overflow condition. Move this sum into the a register used to hold the upper 16 bits of the product. Add the upper 16 bits of the product bd to that register. Move the lower 16 bits of bd into the lower 16 bits of the product. Here is a diagram of the 3 products you sum:



|---------------|-----------------|
| bd (upr 16) | bd (lwr 16) |
|---------------|-----------------|

|---------------|-----------------|
| ad (lwr 16) | 0 |
|---------------|-----------------|

|---------------|-----------------|
| bc (lwr 16) | 0 |
|---------------|-----------------|

[bobdole11122]

Ok I've finally gotten it to work thanks to your help. When I start testing it the program works up to a certain value. When I try 1 mill x 1 mill it gives me the right answer but with extra digits to the left as in [0F4240 * 0F4240] I get [00E8D4A51000] where red is the erroneous digits. I should just get [D4A51000]. I'm not sure if this is something you can help me with without a copy of my code, but is there some limit to the value we multiply using your methods?

[Jeff Reid]

When I try 1 mill x 1 mill it gives me
E8D4A51000 Which is the correct answer, but one that doesn't fit in a 24 bit number. This an overflow case.