24 bit math on 8 bit micros

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

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:

> 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

"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

Look here for ideas...... 
http://www.engineering.sdstate.edu/~fourneyr/S07/ee347L/labs/Lab04.pdf 

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

"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. 

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

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

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

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 !

"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.