24 bit math on 8 bit micros

"David T. Ashley" <dta@e3ft.com> wrote in message 
news:vp6dnYQZAJAktPjVnZ2dnUVZ_tXinZ2d@giganews.com...
> "aamer" <raqeebhyd@yahoo.com> wrote in message 
> news:8tCdnfWmZeRDzMLVnZ2dnUVZ_rDinZ2d@giganews.com...
>> Hi Friends,
>>
>> I was trying to figure out some solution for multiplication of 24bit data
>> with a 24 bit data on 8 bit microprocessor.
>>
>> I got the idea like multiplying first bytes of both data and then the 
>> next
>> bytes taking care of carries and finally put it in to 8 bit micro with 
>> some
>> adjustment(since a 8 bit micro cannot hold the result of multiplication 
>> of
>> 2 24 bit micros).
>>
>> Please correct me if Iam wrong. Any alternative solutions?
>
> 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 dashley@gmail.com.  I actually 
> know more than I have the energy to type about integer algorithms on 
> microcontrollers.

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. 

aamer wrote:
> Hi Friends,
>
> I was trying to figure out some solution for multiplication of 24bit
> data with a 24 bit data on 8 bit microprocessor.
>
> I got the idea like multiplying first bytes of both data and then the
> next bytes taking care of carries and finally put it in to 8 bit
> micro with some adjustment(since a 8 bit micro cannot hold the result
> of multiplication of 2 24 bit micros).
>
> Please correct me if Iam wrong. Any alternative solutions?
>

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) << 0) +
            ((R19 * R17) << 8) +
            ((R19 * R18) << 16) +

            ((R20 * R16) << 8) +
            ((R20 * R17) << 16) +
            ((R20 * R18) << 24) +

            ((R21 * R16) << 16) +
            ((R21 * R17) << 24) +
            ((R21 * R18) << 32);

> Thanks and Regards
> Aamer

-- 
Best Regards,
Ulf Samuelsson
This is intended to be my personal opinion which may,
or may not be shared by my employer Atmel Nordic AB