24 bit math on 8 bit micros

Hi,

Even in 8-bit micros, you will find 16-bit registers and you can make use them and proceed the way you mentioned.

-dK

aamer wrote:

Look here for ideas......

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

No No No...... Do a 6 byte shift..... shift in a 1 or a 0 depending , repeat

24 times. Back to school for you, you and you :) Of course, you may do an 8x8 multiply,if the micro code supports it.

e

eat

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

Hi Foe,

Didn't they teach how to multiply big numbers in the elementary school?

VLV

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.

RB

Which one, there are plenty of ...

Where did you get it from, maybe you can get the solution from there as well ?

Why don't you try out your solution ? You will see if it is wrong.

--
42Bastian
Do not email to bastian42@yahoo.com, it's a spam-only account :-)
Use @monlynx.de instead !

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.

Dave A.

On more thing. My post is with the assumption that the micro can already do

8x8, 8x16, or 16x16 multiplies in the silicon. If it can't ... my post has no relevance.

The AVR has 32 x 8 bit registers, what is the problem???

First value R18:R17:R16 Second value R21:R20:R19 Result of multiply 2 x 8 bit integers: R23:R22 Accumulator R7:R6:R5:R4:R3:R2 ZERO R0

ACK = ((R19 * R16)