COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Multiplying two int32 numbers

• Follow

```When evaluating the expression Z = X * Y where X and Y is SINT32 you
can do it like this:

X0 = bitand(bitshift(x,-24),255);
X1 = bitand(bitshift(x,-16),255);
X2 = bitand(bitshift(x,-8),255);
X3 = bitand(y,255);

Y0 = bitand(bitshift(y,-24),255);
Y1 = bitand(bitshift(y,-16),255);
Y2 = bitand(bitshift(y,-8),255);
Y3 = bitand(y,255);

S0 = 2^24;
S1 = 2^16;
S2 = 2^8;
S3 = 2^0;

Z = (2^48)*X0*Y0 + (2^32)*X1*Y1 + (2^16)*X2*Y2 + X3*Y3 + (2^40)*X0*Y1
+ (2^40)*X1*Y0 + (2^32)*X0*Y2 + (2^32)*X2*Y0 + (2^24)*X0*Y3 +
(2^24)*X3*Y0 + (2^24)*X1*Y2 + (2^24)*X2*Y1 + (2^16)*X1*Y3 +
(2^16)*X3*Y1 + (2^8)*X2*Y3 + (2^8)*X3*Y2

Does this approach/method have a name ??

I would like to google for it and learn more, but I need to know what
I am looking for.

Thank you.
```
 0
Reply John 2/7/2011 8:52:04 PM

```On 2/7/2011 12:52 PM, John McDermick wrote:
> When evaluating the expression Z = X * Y where X and Y is SINT32 you
> can do it like this:
>
> X0 = bitand(bitshift(x,-24),255);
> X1 = bitand(bitshift(x,-16),255);
> X2 = bitand(bitshift(x,-8),255);
> X3 = bitand(y,255);
>
> Y0 = bitand(bitshift(y,-24),255);
> Y1 = bitand(bitshift(y,-16),255);
> Y2 = bitand(bitshift(y,-8),255);
> Y3 = bitand(y,255);
>
> S0 = 2^24;
> S1 = 2^16;
> S2 = 2^8;
> S3 = 2^0;
>
> Z = (2^48)*X0*Y0 + (2^32)*X1*Y1 + (2^16)*X2*Y2 + X3*Y3 + (2^40)*X0*Y1
> + (2^40)*X1*Y0 + (2^32)*X0*Y2 + (2^32)*X2*Y0 + (2^24)*X0*Y3 +
> (2^24)*X3*Y0 + (2^24)*X1*Y2 + (2^24)*X2*Y1 + (2^16)*X1*Y3 +
> (2^16)*X3*Y1 + (2^8)*X2*Y3 + (2^8)*X3*Y2
>
>
>
> Does this approach/method have a name ??
>
> I would like to google for it and learn more, but I need to know what
> I am looking for.
>
> Thank you.

Crossproducts.

--
Rob Gaddi, Highland Technology
Email address is currently out of order
```
 0
Reply Rob 2/7/2011 8:55:03 PM

```Rob Gaddi  <rgaddi@technologyhighland.com> wrote:

>On 2/7/2011 12:52 PM, John McDermick wrote:

>> Does this approach/method have a name ??

>Crossproducts.

I would say "partial products".

S.
```
 0
Reply spope33 2/7/2011 10:22:42 PM

```John McDermick <johnthedspguy@gmail.com> wrote:
> When evaluating the expression Z = X * Y where X and Y is SINT32 you
> can do it like this:

> X0 = bitand(bitshift(x,-24),255);
> X1 = bitand(bitshift(x,-16),255);
> X2 = bitand(bitshift(x,-8),255);
> X3 = bitand(y,255);

> Y0 = bitand(bitshift(y,-24),255);
> Y1 = bitand(bitshift(y,-16),255);
> Y2 = bitand(bitshift(y,-8),255);
> Y3 = bitand(y,255);

> S0 = 2^24;
> S1 = 2^16;
> S2 = 2^8;
> S3 = 2^0;

> Z = (2^48)*X0*Y0 + (2^32)*X1*Y1 + (2^16)*X2*Y2 + X3*Y3 + (2^40)*X0*Y1
> + (2^40)*X1*Y0 + (2^32)*X0*Y2 + (2^32)*X2*Y0 + (2^24)*X0*Y3 +
> (2^24)*X3*Y0 + (2^24)*X1*Y2 + (2^24)*X2*Y1 + (2^16)*X1*Y3 +
> (2^16)*X3*Y1 + (2^8)*X2*Y3 + (2^8)*X3*Y2

> Does this approach/method have a name ??

Note that this is fine for unsigned data, but you need a correction
for signed data.  Google for "booth multiplication" or "booth recoding"
for some of the details on doing signed binary multiplication.

Otherwise, it is the way the partial products would be combined
in base 256 multiplication.

-- glen
```
 0
Reply glen 2/7/2011 11:11:16 PM

```On Mon, 7 Feb 2011 12:52:04 -0800 (PST), John McDermick
<johnthedspguy@gmail.com> wrote:

>When evaluating the expression Z = X * Y where X and Y is SINT32 you
>can do it like this:
>
>X0 = bitand(bitshift(x,-24),255);
>X1 = bitand(bitshift(x,-16),255);
>X2 = bitand(bitshift(x,-8),255);
>X3 = bitand(y,255);
>
>Y0 = bitand(bitshift(y,-24),255);
>Y1 = bitand(bitshift(y,-16),255);
>Y2 = bitand(bitshift(y,-8),255);
>Y3 = bitand(y,255);
>
>S0 = 2^24;
>S1 = 2^16;
>S2 = 2^8;
>S3 = 2^0;
>
>Z = (2^48)*X0*Y0 + (2^32)*X1*Y1 + (2^16)*X2*Y2 + X3*Y3 + (2^40)*X0*Y1
>+ (2^40)*X1*Y0 + (2^32)*X0*Y2 + (2^32)*X2*Y0 + (2^24)*X0*Y3 +
>(2^24)*X3*Y0 + (2^24)*X1*Y2 + (2^24)*X2*Y1 + (2^16)*X1*Y3 +
>(2^16)*X3*Y1 + (2^8)*X2*Y3 + (2^8)*X3*Y2
>
>
>
>Does this approach/method have a name ??
>
>I would like to google for it and learn more, but I need to know what
>I am looking for.
>
>Thank you.

That is the definition of unsigned multiplication in base 256 ie. how
partial products are generated and combined if you only have 8 bit
multiplier (and much wider adders of course).
You can also look at it in a slightly different way:

X = 256^3 * X0 + 256^2 * X1 + 256 * X2 + X3
Y = 256^3 * Y0 + 256^2 * Y1 + 256 * Y2 + Y3

so X*Y = 256^6 * X0 * Y0 ...

(btw you have a typo in X3)
--
Muzaffer Kal

DSPIA INC.
ASIC/FPGA Design Services

http://www.dspia.com
```
 0
Reply Muzaffer 2/8/2011 5:50:26 AM

```On 07/02/2011 21:52, John McDermick wrote:
> When evaluating the expression Z = X * Y where X and Y is SINT32 you
> can do it like this:
>
> X0 = bitand(bitshift(x,-24),255);
> X1 = bitand(bitshift(x,-16),255);
> X2 = bitand(bitshift(x,-8),255);
> X3 = bitand(y,255);
>
> Y0 = bitand(bitshift(y,-24),255);
> Y1 = bitand(bitshift(y,-16),255);
> Y2 = bitand(bitshift(y,-8),255);
> Y3 = bitand(y,255);
>
> S0 = 2^24;
> S1 = 2^16;
> S2 = 2^8;
> S3 = 2^0;
>
> Z = (2^48)*X0*Y0 + (2^32)*X1*Y1 + (2^16)*X2*Y2 + X3*Y3 + (2^40)*X0*Y1
> + (2^40)*X1*Y0 + (2^32)*X0*Y2 + (2^32)*X2*Y0 + (2^24)*X0*Y3 +
> (2^24)*X3*Y0 + (2^24)*X1*Y2 + (2^24)*X2*Y1 + (2^16)*X1*Y3 +
> (2^16)*X3*Y1 + (2^8)*X2*Y3 + (2^8)*X3*Y2
>
>
>
> Does this approach/method have a name ??
>
> I would like to google for it and learn more, but I need to know what
> I am looking for.
>
> Thank you.

At primary school we called this "long multiplication", though the
layout and ordering was slightly different.

And just like at school, it is easiest if you handle the sign separately
so that the multiplication is done with unsigned numbers.

```
 0
Reply David 2/8/2011 9:59:38 AM

5 Replies
221 Views

(page loaded in 0.099 seconds)

Similiar Articles:

7/28/2012 8:51:26 PM