> 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
Reply by David T. Ashley●June 27, 20082008-06-27
"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.
Reply by David T. Ashley●June 27, 20082008-06-27
"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.
Dave A.
Reply by 42Bastian Schick●June 24, 20082008-06-24
On Mon, 23 Jun 2008 02:33:50 -0500, "aamer" <raqeebhyd@yahoo.com>
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.
Which one, there are plenty of ...
>I got the idea like multiplying first bytes of both data and then the next
Where did you get it from, maybe you can get the solution from there
as well ?
>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?
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 <same-name>@monlynx.de instead !
Reply by Rube Bumpkin●June 23, 20082008-06-23
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?
>
> Thanks and Regards
> Aamer
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
Reply by Vladimir Vassilevsky●June 23, 20082008-06-23
aamer wrote:
> Hi Friends,
Hi Foe,
> I was trying to figure out some solution for multiplication of 24bit data
> with a 24 bit data on 8 bit microprocessor.
Didn't they teach how to multiply big numbers in the elementary school?
VLV
Reply by Andrew●June 23, 20082008-06-23
On 23 Jun, 14:44, "TT_Man" <Some...@ntlworld.com> wrote:
> "Andrew" <andr...@sdf.lonestar.org> wrote in message
>
> news:818f6e78-c8cb-4109-b7ca-b5c295a847f7@e39g2000hsf.googlegroups.com...
>
> > Having said all this it seems the explanation above is as clear as
> > mud. =A0Find a good book on binary arithmetic - it should have some nic=
e
> > diagrams explaining the underlying principles.
>
> No No No...... Do a 6 byte shift..... shift in a 1 or a 0 depending , rep=
eat
> 24 times. Back to school for you, you =A0and you :)
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.
> Of course, you may do an 8x8 multiply,if the micro code supports it.
What do you think I was doing?
--
Andrew Smallshaw
andrews@sdf.lonestar.org
Reply by TT_Man●June 23, 20082008-06-23
"Andrew" <andrews@sdf.lonestar.org> wrote in message
news:818f6e78-c8cb-4109-b7ca-b5c295a847f7@e39g2000hsf.googlegroups.com...
> On 23 Jun, 08:33, "aamer" <raqeeb...@yahoo.com> wrote:
>
>> 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).
>
> 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
> andrews@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.
Reply by Andrew●June 23, 20082008-06-23
On 23 Jun, 08:33, "aamer" <raqeeb...@yahoo.com> wrote:
> 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).
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
andrews@sdf.lonestar.org
Reply by TT_Man●June 23, 20082008-06-23
"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?
>
> Thanks and Regards
> Aamer