Multiplication and division

[bin]

ScreenTest has been optimized to be instantaneous, but it's very slow to replace Math. VM with my own Math. VM in drawing the roof. I think the problem should be multiplication and division, but I've found a lot of knowledge about multiplication and division on the internet. It involves masking displacement operations. Besides, are there any other better ways to make multiplication and division work faster?

[cadet1620]

One quick thing that you can do in Math.divide is to move the recursive calling into another function that does not need to waste time checking for negative arguments

function int divide(int x, int y) {
    var q;
    let q = Math._div(Math.abs(x), Math.abs(y));

    if ((x < 0) = (y < 0)) {    // sign(x) == sign(y)
        return q;
    } else {
        return -q;
    }
}

_div(int x, int y) is the normal recursive divide function.

For Mult(), since you are testing the bits in order, you do not need to call a function to get the 2^n bits. Set mask to 1 and do mask = mask + mask to get the next mask value.

[bin]

thank you very much, mark
In accordance with your method to re realize the division and multiplication is really faster.

[Sai krishna]

Hi, I am trying to understand how the multiplication algorithm works. I quite understood how it is working for positive numbers. It is told in the course material that the algorithm works also for the negative numbers in 2's complement.
I verified it and it magically turned out to be true if we consider only the last 16 bits of the product. Although this is not a course on algorithms, I wonder how is this multiplication working out even for negative numbers. I can't figure it out or understand the reason or prove that the algorithm is valid for negative numbers also.
I beg to please explain or provide a hint on why it is working for negative numbers. If you are kind enough please provide any proof or link to any source on the web that explains why it works.

[WBahn]

Sai krishna wrote

Hi, I am trying to understand how the multiplication algorithm works. I quite understood how it is working for positive numbers. It is told in the course material that the algorithm works also for the negative numbers in 2's complement.
I verified it and it magically turned out to be true if we consider only the last 16 bits of the product. Although this is not a course on algorithms, I wonder how is this multiplication working out even for negative numbers. I can't figure it out or understand the reason or prove that the algorithm is valid for negative numbers also.
I beg to please explain or provide a hint on why it is working for negative numbers. If you are kind enough please provide any proof or link to any source on the web that explains why it works.

The key is how two's complement is structured.

Let's consider 4-bit numbers. If they are straight binary (i.e., unsigned) then they represent the values 0 though 15. If we multiply two numbers that exceed that, we get overflow and the result wraps around because we only keep the last four bits.

So 7*3 = 21 but we get 5 because the binary for 21 is 10101 and we get 0101.

Mathematically, what we get is (A*B) mod 16, or the remainder after dividing the "true" result by 16 (which is 2^4 or 2^(number of bits))

When we use two's complement, negative numbers are represented by the bit patterns for large positive numbers using the relationship

-X = (2^n) - X

So for our 4-bit numbers, if I want to represent -3 I use the same pattern that I would normally use for 16-3 or 13.

So now let's say that I want to multiply 2 and -3 together. I'm using the patterns

0010 * 1101

which, in the unsigned world, is the same as multiplying 2 and 13, which yields 26 and when I keep the remainder after dividing that by 16 leaves me with 10 (bit pattern 1010). If I interpret this as a negative two's complement number it is -6, which is the correct result.

Why does this work.

Let's consider multiplying a positive number and a negative number together. We'll use A and B but we'll force these to be positive values, so our case would be the following:

(A)*(-B)

Using the relationship above for 2's comp, we can write this as

(A)*( (2^n) - B ) = [(A)*(2^n)] - A*B

Regardless of what A is, the term in square brackets vanishes when we keep the remainder after dividing by 2^n because it is evenly divisible by 2^n.

[(A)*(2^n)] - A*B mod 2^n = -A*B mod 2^n

What about multiplying two negative numbers together?

(-A)*(-B)
( (2^n) - A )*( (2^n) - B ) mod 2^n
[2^(2n)] - [(A)*(2^n)] - [(B)*(2^n)] + A*B mod 2^n
A*B mod 2^n

Thus, as long as the "true" result is representable within out n bits, the algorithm that multiplies two unsigned integers together will also work on two's complement integers.

[Sai krishna]

Beautiful proof.
Thank you a lot for that.