[Question] How to proceed the multiplication with negative numbers ?

[GISED_Link]

Here we are !

Here is the 2 implementations of the signed multiplication. First method is the left one, the seconde the right one.

The 2 calculation methods : 

1. Always multiply positive number (so you make it positive at the input), then correct the sign at the result
   
2. Multiplie the input without any correction, then Extend the signe by adding a number wich depend of the inputs
   

For the first method (Work in positive) :

1. What will we do :

Code:

.  3            //the . (Dot) is only there for the formating
x -4
----
=-12

2. In binary (using the 2's complement)

Code:

. 00000011
x 11111100
-----------
= 11110100

3. We transform -4 in 4 ( (NOT -4) +1)

Code:

. 00000011          
x 00000100           //NOT(11111100)+1 = NOT(-4) +1
-----------
= 00001100           //Pre-result

4. We make the result negative ( (NOT Result) +1)

Code:

. 11110011         //NOT(00001100) = NOT(12)
+ 00000001         //+1
-----------
= 11110100

For the second method (Extend the sign) :

You have to add the Magical Number in the end of the multiplication (for unsigned number, set (force) this number at 0). This Magic number is there for a very stupid reason, related to the multiplication process itself. When you do an arithmetic operation of a 8 bit number with a 16 bit System (adder by example) and this number is negative, you have to Extend the sign !

Example of the problem:

Code:

add 1 to -1 :

. 0000'0000 1111'1111           //-1 in 8 bit number, the first 8 bit are set to 0 (no input...) (2's complement)
+ 0000'0000 0000'0001           //+ 1
---------------------
. 0000'0001 0000'0000           // We found 256 ! AND NOT 0 !

And when you do a multiplication, you do a lot of addition ... so the problem is bigger.

So, I will explain you what happens in the signed multiplication :



So we see that we can not only use the unsigned part, we have to add a "magic number" wich is the Blue part + Green part. I've found a combinatorial function to get the blue part and the green part. Once you have thoses parts, you only have to add Blue with Green and add the reuslt to the partial product of the unsigned part.

Blue part =

to hard to explain it for the moment...

Green part =

to hard to explain it for the moment...


This is the same multiplication but arranged correctly :


I volontary don't write the result of the 16 (or 17) first bit because we don't care (and it will be not correct because for a result on 32 bit we have to extend the sign of the input to 32 bit...)