+- Forums - Open Redstone Engineers (https://forum.openredstone.org)
+-- Forum: ORE General (https://forum.openredstone.org/forum-39.html)
+--- Forum: Projects & Inventions (https://forum.openredstone.org/forum-19.html)
+---- Forum: In Progress (https://forum.openredstone.org/forum-20.html)
+---- Thread: [Question] How to proceed the multiplication with negative numbers ? (/thread-5835.html)
Pages:
1
2
[Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 02-18-2015
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
RE: [Question] How to proceed the multiplication with negative numbers ? - PabloDons - 02-18-2015
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
RE: [Question] How to proceed the multiplication with negative numbers ? - Legofreak - 02-18-2015
I believe multiplying the 2's compliment might be division. I'm probably wrong though.
RE: [Question] How to proceed the multiplication with negative numbers ? - PabloDons - 02-18-2015
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
RE: [Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 02-19-2015
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
----
=-122. In binary (using the 2's complement)
Code:
. 00000011
x 11111100
-----------
= 111101003. We transform -4 in 4 ( (NOT -4) +1)
Code:
. 00000011
x 00000100
-----------
= 000011004. We make the result negative ( (NOT Result) +1)
Code:
. 00000011
x 00000100
-----------
= 11110100And 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
RE: [Question] How to proceed the multiplication with negative numbers ? - Magic :^) - 02-19-2015
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.
RE: [Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 02-19-2015
(02-19-2015, 02:49 AM)The Magical Gentleman Wrote: 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)
(02-19-2015, 02:49 AM)The Magical Gentleman Wrote: 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...
RE: [Question] How to proceed the multiplication with negative numbers ? - Magic :^) - 02-19-2015
(02-19-2015, 04:09 PM)GISED_Link Wrote:(02-19-2015, 02:49 AM)The Magical Gentleman Wrote: 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.
RE: [Question] How to proceed the multiplication with negative numbers ? - greatgamer34 - 02-20-2015
The most common way is obviously xor the sign.
welp.. thats all i got xD
RE: [Question] How to proceed the multiplication with negative numbers ? - TSO - 02-20-2015
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)