Hi ! Dnia 5 listopada 2009 19:11 Ullrich von Bassewitz <firstname.lastname@example.org> 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 listReceived on 2009-11-10 20:00:04
Archive generated by hypermail 2.2.0.