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

### Multiplying two int32 numbers

• Email
• 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 am looking for.

Thank you.
```
 0

See related articles to this posting

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

--
Email address is currently out of order
```
 0

```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

```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

```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 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

```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