Re: Signed multiplication

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,
Konrad

       Message was sent through the cbm-hackers mailing list