I was trying to figure out some solution for multiplication of 24bit dat with a 24 bit data on 8 bit microprocessor.

I got the idea like multiplying first bytes of both data and then the nex bytes taking care of carries and finally put it in to 8 bit micro with som adjustment(since a 8 bit micro cannot hold the result of multiplication o

2 24 bit micros).

Please correct me if Iam wrong. Any alternative solutions?

Multiplication longer than the machine's length is considerably more involved than subtraction or addition. It isn't simply a case of multiplying each pair of bytes together and 'taking care of' carries. In effect every byte needs multipltying with every other byte.

The first thing to bear in mind is the length of the results. Multiplication of two 24 bit numbers will in general result in a 48 bit result. 8 bit multiplication results in a 16 bit result. The following is off the top of my head, assumes unsigned numbers, and has not been tested but will hopefully serve as an initial pointer. For ease of reference, we will designate the operands A and B, the destination D, and number each byte of a value from 1 being the least significant. So for example A1 is the least significant byte of one of first operand, D5 is the second most signifcant byte of the result.

1) Multiply the A3 and B3 together. Stash the (16 bit) result in the D5 and D6.
2) Multiply A3 and B2. Put the low byte of the result in the D4 and add the high byte to D5. If this byte overflows increment the D6.
3) Multiply A3 with B1. Put the low byte in D3 add the high byte to D4. If that overflows increment D5. If that in turn overflows increment D6 (D6 won't overflow).
4) Multiply A2 and B2 together. Low order byte to D2 and add the high byte to D3. If that overflows increment the more significant bytes in turn up to D6 at step 3.
5) Multiply A2 with B1. Copy the low order byte to D1 and add the high byte to D2. Again, check for overflow of D2 and increment the subsequent bytes if necessary.
6) Multiply A1 and B1. The least significant byte goes to D1 and add the high byte to D2. Finally, if that overflows increment D2...D6 as appropriate.

Having said all this it seems the explanation above is as clear as mud. Find a good book on binary arithmetic - it should have some nice diagrams explaining the underlying principles.

-- Andrew Smallshaw snipped-for-privacy@sdf.lonestar.org

That is the textbook solution for a different problem - doing a word length multiply on a machine that lacks a hardware multiplier.

The problem here is in the 'Do a 6 byte shift' - that isn't a natural operation on an eight bitter. The method I posted was almost exclusively concerned with the practicalities of dealing with 24 or 48 bit quantities on an eight bitter in the minimum number of steps. Instead of 6 multiplies, five additions and carries you want to use 48 shifts, 64 adds and carries.

What do you think I was doing?

-- Andrew Smallshaw snipped-for-privacy@sdf.lonestar.org

You've essentially got it. I wrote a 24/36 bit integer math package for the PDP-8 (a 12 bit machine) in the late 70's. I can go dig out the (assembly) sources for that if you'd like.

Donald Knuth refers to these algorithms (addition, subtraction, etc.) as classic algorithms. He covers them in detail in Volume II (I believe) in his work "The Art of Computer Programming".

For the classic algorithms, the general issue is that the machine typically has instructions that operate on smaller operands, and the question is how to use the same instructions to operate on larger operands with larger results.

For addition and subtraction, the solution is obvious (ADD, ADC, ADC, ADC, etc.).

For multiplication, the solution is less obvious. As another poster pointed out, everything is multiplied with everything else.

You can get some insight into what needs to be done if you look up a classic method of multiplication sometimes taught to children. You write the two operands along the edges of tables, one digit per row or column. You split each cell into two parts. You carry out each digit multiplication and put the result in the the cell of the table. Then, you add diagonally. It becomes clear that there is only one least significant and one most significant term.

The most classic approach is to do the multiplication of the least significant term first, followed by terms where the results are of equal rank and process the carries, then to work "upwards" in rank so that one processes the carries upward at the same time.

For example, let's say one is multiplying A1, A0 by B1, B0. One does B0 * A0 first, then A1 * B0 and A0 * B1 + carry, then A1 * B1 + carries.

Knuth's classic work would be helpful to you.

Also, the GMP is a good reference. The non-processor-specific functions normally give a good reference for the best known ordering.

Division, by the way is the hardest. The question is how to use the small-operand-division instructions built into most processors to divide larger operands. It can be done ... but since you asked about multiplication, I won't give the details here.

If you need info about how to get Knuth's book inexpensively or want me to double-check which volume it is in before you buy or if there is anything else I can do, please write me directly at snipped-for-privacy@gmail.com. I actually know more than I have the energy to type about integer algorithms on microcontrollers.

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.