# Re: Signed multiplication

Date: Tue, 10 Nov 2009 20:09:04 +0100
Message-ID: <76cb9e420911101109t82d4c29na039d7b5c7c4e9da@mail.gmail.com>
```Hi !

Dnia 5 listopada 2009 19:11 Ullrich von Bassewitz <uz@musoftware.de> napisał(a):
> For a 16x16=>16 multiplication, the standard shift-and-add algorithm works for
> both, signed and unsigned integers.
> Given
>
>         \$FFFE * \$0002 = \$1FFFC
>
> if you take just the lower 16 bits of the result, it is correct for a signed
> multiplication:
>
>         \$FFFE * \$0002 = \$FFFC (high 16 bits dropped)
>            -2 *     2 =    -4
>
> What I need is a multiplication that gets a correct value for the high 16 bit
> (the result should be \$FFFFFFFC instead of \$1FFFC). Currently, I'm using an
> unsigned 16x16=>32 multiplication with the absolute values of the operands,
> and adjust the sign of the result. The question is, if there is a faster
> method than this.

If both multiplicand and multiplier are positive - no adjustment is needed.
If either of them is negative - you need to subtract the positive
operand from the higher word of the multiplication result.
If they are negative - subtract both of them.

Let's say, modulus for both operands is MOD, so for the result it
would be MOD*MOD.
If we are multiplying the two negative numbers, in 2's complement they
would be expressed as -MUL1=MOD-MUL1 and -MUL2=MOD-MUL2.
Result would be MUL1*MUL2, but (MOD-MUL1)*(MOD-MUL2) = MOD*MOD -
MOD*MUL1 - MOD*MUL2 + MUL1*MUL2.

MOD*MOD = 0 (modulo MOD*MOD), so we just need to sustract MOD*MUL1 and
MOD*MUL2 from the result.

[ Do the math for MUL1 * -MUL2 or -MUL1 * MUL2 yourself  ]

Example:
\$7FFF * \$7FFF = \$3FFF0001 (OK)
But -\$7FFF * -\$7FFF = \$8001 * \$8001 = \$40010001 (unsigned multiplication result)
\$40010001 - \$80010000 - \$8001000 = \$3FFF0001 - OK now (actually you do
not need to care about the lower word during this subtraction - since
MOD is \$10000 - i.e. \$4001-\$8001-\$8001=\$3FFF)

This will not save many cycles though... You would not need to convert
to the absolute values, but the adjustment takes some time as well

Regards,