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

[GISED_Link]

Heeeeeeeeeello,

I have a little problem with my multiplication : I don't know how to do with the negative numbers. I'm trying to understand how to do that. If you have an idea, I'll appreciate a lot.

thx

[PabloDons]

negative * positive = negative

it is the exact same as multiplying two positive numbers, only thing is you XOR the negative signs of the numbers.
2*3=6
-2*3=-6
-2*-3=6

if you want to multiply using 2's complimented number, I'm not sure if it works. I will have to check

[Legofreak]

I believe multiplying the 2's compliment might be division. I'm probably wrong though.

[PabloDons]

just checked, it kinda works though. u have to exclude the most significant bits that are 0. like 00110 is gonna be 110 instead. else it won't be correct cuz 110(2's compliment of 2)*010=01100. that is only correct if you exclude the 0 on the left. I haven't yet tested two negative numbers though, I'll do that later

edit: checked with 2 negative numbers. that doesn't work unfortunately. 2's compliment doesn't seem to work in general on multiplication, but if you use signed numbers instead, you can just XOR the signs and you get the sign for the result. you will have to calculate 2's compliment outside the multiplier though

[GISED_Link]

I think I have found a stupid way to do that ...

-- The MSB of a 8 bits number is bit 7 ('cause the LSB is bit 0) --

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
-----------
= 00001100

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

Code:

. 00000011
x 00000100
-----------
= 11110100

And we found the correct answer. So I will add 3 full-adders and 3 XORs to my multiplier, one per input and one for the output. The first input of each XOR are the data bit, the second is the inversion bit. So the inversion bit of the input XORs are the bit 7 of each number. For the output, it's (A(7) XOR B(7)).

If someone has a better way to do that without those full adder, it would be cool.

This link has maybe the answer ...

https://books.google.ch/books?id=3kQoAwAAQBAJ&pg=PA74&lpg=PA74&dq=sophisticated+algorithms+for+multiplication+and+division+of+Two%27s+Complement+numbers.&source=bl&ots=sdhENBz1WL&sig=p_JK2BxO12c-05bAjJEZmx-E6L4&hl=fr&sa=X&ei=KDnlVIqaOcK-PNS3gbAG&ved=0CCIQ6AEwAA#v=onepage&q=sophisticated%20algorithms%20for%20multiplication%20and%20division%20of%20Two's%20Complement%20numbers.&f=false

[Magic :^)]

You could use sign magnitude encoding?

sign magnitude encoding is just using the msb as a sign bit, and the rest of the bits are the same. Positive or not.
sign magnitude does mean that you have 1 less number though, as 10000000 == 00000000

the bonus is that all you need is a 7 bit multiplier and just xor the two msbs.

EDIT: ah, i realise that this method was already suggested xD

maybe you could use modified binary counters instead of full adders for 2's comp conversion? It may be faster. you just need +1 and an inverted input after all.

[GISED_Link]

You could use sign magnitude encoding?

sign magnitude encoding is just using the msb as a sign bit, and the rest of the bits are the same. Positive or not.
sign magnitude does mean that you have 1 less number though, as 10000000 == 00000000

the bonus is that all you need is a 7 bit multiplier and just xor the two msbs.

EDIT: ah, i realise that this method was already suggested xD

This multiplier will be a part of my ALU ... So it's not possible to use that (I d'ont want to change all my architecture)

maybe you could use modified binary counters instead of full adders for 2's comp conversion? It may be faster. you just need +1 and an inverted input after all.

I think I haven't understood...

[Magic :^)]

maybe you could use modified binary counters instead of full adders for 2's comp conversion? It may be faster. you just need +1 and an inverted input after all.

I think I haven't understood...

gah sorry, it doesn't really matter since you're using this in an ALU anyway.
I suggested the counters because I thought there may be a counting algorithm that is faster than a normal adder.

[greatgamer34]

The most common way is obviously xor the sign.

welp.. thats all i got xD

[TSO]

Too bad I wasn't here for this thread. IIRC, to multiply in two's compliment, you had to sign extend the numbers involved. (Give me a moment while I check that)

Okay, I'm back.
Use booth's algorithm if you can understand it.
Otherwise, sign extend both the n-bit multiplicands to 2n-1 bits, multiply normally, and then cut off the front at the 2n-1 bit of the product and all partial products. (Warning, your multiplier will be really big)

[GISED_Link]

thx for the links. I will think about those algorythms

I've created a Excel files for simulate the multiplication. I've always the correct result but I've have to found an variable offset value... wich is really hard to find the equation.

I join my excel file. If you have time to play with it... Please notice that there are 2 sheets !

[GISED_Link]

WOUAAAAAAAAAAAAAAAAAH ! It's done !

I've finally found the magic variable offset variable ! I'll implement my research as soon as possible.

Just notice that the previous attached file has a bug, so I give you the correct one.

[PabloDons]

all I see is 1's and 0's. mind commenting a little? like explain what is happening in file?

[GISED_Link]

all I see is 1's and 0's. mind commenting a little? like explain what is happening in file?

It is my devlopement file... So I haven't take time to do something understandable for everybody. The only way to understand something is to look into the boxes formulas. For the moment I will implement it in redstone, then I will take time to link this file to the implement designe.

[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...)