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

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

+- 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

RE: [Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 02-20-2015

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 !

RE: [Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 02-21-2015

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.

RE: [Question] How to proceed the multiplication with negative numbers ? - PabloDons - 02-21-2015

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

RE: [Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 02-22-2015

(02-21-2015, 07:22 PM)PabloDons Wrote: 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.

RE: [Question] How to proceed the multiplication with negative numbers ? - GISED_Link - 03-20-2015

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 :

Always multiply positive number (so you make it positive at the input), then correct the sign at the result
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 :

[Image: 127485exempledusigne.jpg]

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 :
[Image: 4409548bitmultiplicationavecextensiondesigne.jpg]

[Image: 4409548bitmultiplicationavecextensiondesigne.jpg]

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