Multiplication – Random IT Utensils https://blog.adamfurmanek.pl IT, operating systems, maths, and more. Sat, 02 Jan 2021 18:45:25 +0000 en-US hourly 1 https://wordpress.org/?v=6.5.2 ILP Part 7 – Multiplication of negative numbers https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/ https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/#comments Sat, 03 Oct 2015 10:00:22 +0000 http://blog.adamfurmanek.pl/?p=661 Continue reading ILP Part 7 – Multiplication of negative numbers]]>

This is the seventh part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

We have already seen how to multiply variables in ILP. In part 5 we saw how to define minimum and absolute value. Last time we improved our multiplication algorithm. Today we are going to handle negative numbers.

General idea

First let’s summarize what we can do already:

  • We are able to decompose variable and extract its digits
  • We can multiply two binary digits by calculating their conjunction
  • We know how to multiply non-negative number by single binary digit using minimum function
  • We can multiply two non-negative numbers by decomposing latter argument, multiplying its digits by former argument and power of two, and summing the results
  • We know how to compare numbers and so we are able to deduce whether a number is negative (by comparing it with zero)

We would like to multiply possibly negative numbers. We will do that by multiplying their absolute values (so ignoring the sign) and then changing the sign if necessary.

First step – multiplying absolute values

We start with the following variables:

    \begin{gather*} a, b, x \in \mathbb{Z} \\ k = 2^n - 1 \\ n \in \mathbb{N} \\ \left|a\right|, \left|b\right|, \left|x\right| \le k \\ b_0, b_1, \ldots, b_{n-1} \in \{0, 1\} \end{gather*}

We have arguments (a,b), result (x), upper bound (k), and digits of b. We first define:

    \begin{gather*} a_+ = \left|a\right| \\ b_+ = \left|b\right| \\ x_+ = a \cdot b \end{gather*}

Here we multiply variables by using already described algorithms.

Second step – calculating the sign

Next, we calculate the sign:

    \begin{gather*} a_s = a \stackrel{?}{\ge} 0 \\ b_s = b \stackrel{?}{\ge} 0 \\ s = a_s \stackrel{?}{=} b_s \end{gather*}

s will be one only when a_s and b_s have the same sign (so they are both negative or both positive). When the arguments have different signs, s will be equal to zero.

Final step – changing the sign of the result

Now we are going to set the sign of the result. We multiply the result of multiplication of absolute values by the sign:

    \[ x_s = \min(x_+, s \cdot k) \]

When the sign s is equal to one the x_s will be equal to x_+. Otherwise, it will be equal to zero.
Now we are going to set the final result using this formula:

    \[ x = \left(x_s - \frac{x_+}{2}\right) \cdot 2 \]

When the result should be non-negative, the sign s will be equal to one, so the x_s will be equal to x_+, and we will get \left(x_+ - \frac{x_+}{2}\right) \cdot 2 = \frac{x_+}{2}\cdot 2 = x_+. However, when the result should be negative, the sign will be zero, the x_s will be equal to zero, and we will get \left(0 - \frac{x_+}{2}\right) \cdot 2 = -\frac{x_+}{2} \cdot 2 = -x_+.

Division poses multiple difficulties. First, it may introduce representation errors since we need to use fractions. Second, some solvers do not support non-integer values at all so they cannot multiply negative variables. There are ways to avoid division completely and we should use them if possible.

Changing the result sign with maximum and minimum

Instead of dividing we can use maximum and minimum. This formula is a basic extension of multiplication by a binary digit:

    \[ x = \min\left(x_+, s \cdot k\right) + \max\left(-x_+, -\left(1-s\right) \cdot k\right) \]

When the result should be positive then s is equal to one and first component of the sum is equal to x_+. Second part of the sum is equal to zero as we take maximum of some negative number and zero. Hence the whole sum is equal to x_+ which is as expected.

However, when s is equal to zero and the result should be negative, first part of the sum is equal to zero because we take minimum of x_+ and zero. Second part of the sum is equal to -x_+ because we take maximum of -x_+ and very small number.

Changing the result sign with subtraction

We can calculate the final result even easier using subtraction:

    \[ x = x_+ \cdot s - x_+ \cdot \left(1 - s\right) \]

If the result should be non-negative then s is equal to one so the formula simplifies to x_+ \cdot 1 - x_+ \cdot 0 = x_+. However, when result should be non-postive and s is equal to zero then we obtain x_+ \cdot 0 - x_+ \cdot 1 = -x_+.

This is simple and elegant, and it doesn’t introduce unnecessary floating point issues.

Summary

We are now able to multiply any integer variables for which we know upper and lower bound. In the next part we will use this operation to calculate greatest common divisor (GCD).

]]> https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/feed/ 1 ILP Part 6 – Faster multiplication https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/ https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/#comments Sat, 26 Sep 2015 10:00:51 +0000 http://blog.adamfurmanek.pl/?p=621 Continue reading ILP Part 6 – Faster multiplication]]>

This is the sixth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Last time we saw how to define minimum in ILP. We also know how to multiply variables using long multiplication algorithm. Our algorithms work, however, they are slow. Today we are going to utilize \min function to speed up multiplication.

General idea

We know how to multiply variables. Basically, we decompose both arguments and extract digits. Next, we multiply every pair of digits using conjuction, and multiply the result by power of two (which is constant).
As we said in part 2, this requires O\left(n^2\right) temporary variables because we need to store every conjunction in some temporary variable. However, when we perform long multiplication on a piece of paper we do not multiply every two digits but we multiply digit b_i by whole argument a (using notation from part 2). We can do the same in ILP.

Improvement

We know that we cannot multiply variables just like that because we need to use only linear constraints so once again we are going to use some trick. We have the following variables:

    \begin{gather*} n \in \mathbb{N} \\ k = 2^{n} - 1 \\ a,b,x \in \mathbb{Z_+} \cup \{0\} \\ \left|a\right|, \left|b\right|, \left|x\right| \le k\\ b_0 + 2\cdot b_1 + 4\cdot b_2 + \cdots + 2^{n-1}\cdot b_{n-1} = b\\ b_0, b_1, \ldots, b_{n-1} \in \{0, 1\} \end{gather*}

We have arguments (a, b), result (x), decomposition (b_1, \ldots, b_n), and the maximum possible value (k). Now we are going to multiply every digit b_i by argument a using \min function.

Let’s consider the value of a \cdot b_i. When b_i is zero then the whole value is zero (because it is a \cdot 0). When b_i is one the result is equal to a. We also know that a \le k which implies a \cdot b_i \le k. This is in fact equivalent to \min\left(a, b_i \cdot k\right). When b_i is zero we get \min\left(a, 0 \cdot k\right) = \min(a, 0) = 0. When b_i is one we obtain \min\left(a, 1 \cdot k\right) = \min(a, k) and because a \le k we get \min(a, k) = a. We also need to remember that k is a constant value so we are allowed to calculate b_i \cdot k.

Final formula

Now we can define the final formula:

    \begin{gather*} a \cdot \overline{b_{n-1}b_{n-2}\ldots b_2b_1b_0} = \sum_{i=0}^{n-1} 2^i \cdot \left( \min\left(a, b_i \cdot k\right) \right) \end{gather*}

We simply multiply every digit by a and then by the power of two.

Summary

We are now able to calculate multiplication using only O(n) temporary variables which is a great improvement. In the next part we are going to see how to multiply negative values using today’s algorithm and absolute value function defined in previous part.

]]> https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/feed/ 1 ILP Part 2 – Multiplication https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/ https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/#comments Sat, 29 Aug 2015 10:00:35 +0000 http://blog.adamfurmanek.pl/?p=131 Continue reading ILP Part 2 – Multiplication]]>

This is the second part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Previously we defined Boolean algebra operators using ILP. Today we are going to implement multiplication using the tools we defined last time.

Basics

In ILP we are not able to multiply variables because we need to stick to linear constraints. It is also not clear how can we utilize only addition to calculate a multiplication. However, by reducing the size of domain we will be able to do that.

Decomposition

First, we need to use some hack: we need to limit the maximum possible value of a variable. Let’s assume that we want to do the following:

    \begin{gather*} n \in \mathbb{N_+} \\ a,b,x \in \mathbb{Z_+} \cup \{0\} \\ x = a \cdot b \\ \left|a\right|, \left|b\right|, \left|x\right| \le 2^{n} - 1 \end{gather*}

So we say that our variables are not greater than n-th power of two. For now we also stick to non-negative values, we will generalize the operator later.
Now we are able to decompose value and retrieve digits:

    \begin{gather*} a_0 + 2\cdot a_1 + 4\cdot a_2 + \cdots + 2^{n-1}\cdot a_{n-1} = a\\ a_0, a_1, \ldots, a_{n-1} \in \{0, 1\} \end{gather*}

We basically represent the variable a in binary notation. Every a_i is a binary variable for consecutive power of two. This representation is well defined for every non-negative number so there is no ambiguity here.

Reduced size – problem?

Representing the variable in binary notation looks like a great hack. Indeed, we have just thrown out infinite number of possible values. But in fact it is not a problem. We need to remember that we are going to solve the problem using solver which will probably perform operations using double values which are already limited. We are only introducing a bit lower limit but in real world it doesn’t bother us. It is not likely that we will need to perform calculations on infinite values.

Long multiplication

Now we are able to perform multiplication. We are going to do that the same way as we were taught at school (you remember that, don’t you?). We will multiply every single pair of digits and sum the results. First let’s define variables and decomposition:

    \begin{gather*} a,b,x \in \mathbb{Z_+} \cup \{0\}\\ n \in \mathbb{N_+} \\ \forall_{i=0}^{n-1} a_i, b_i \in \{0, 1\} \\ \sum_{i=0}^{n-1} 2^i a_i = a\\ \sum_{i=0}^{n-1} 2^i b_i = b \end{gather*}

We also introduce the following notation:

    \[ \overline{a_{n-1}a_{n-2} \ldots a_2a_1a_0} = a \]

The line means that the variables are particular digits and should be read as a whole.
No let’s present the multiplication formula:

    \begin{gather*} \overline{ a_{n-1}a_{n-2}\ldots a_2a_1a_0} \cdot \overline{b_{n-1}b_{n-2}\ldots b_2b_1b_0} = \sum_{i=0}^{n-1} 2^i \cdot \left( \sum_{j=0}^{n-1} 2^j \cdot \left(a_j \wedge b_i\right) \right) \end{gather*}

It looks a bit odd, however, it is in fact really easy. We are taking every pair of digits and multiplying them using conjunction (defined in previous part), we also handle powers of two. Let’s see an example: we multiply a=3 and b=4, each treated as a 4 bit number (n=4).
First let’s decompose the values:

    \begin{gather*} a = 3 = a_0 \cdot 1 + a_1 \cdot 2 + a_2 \cdot 4 + a_3 \cdot 8 \\ b = 4 = b_0 \cdot 1 + b_1 \cdot 2 + b_2 \cdot 4 + b_3 \cdot 8 \end{gather*}

We get: a_0 = 1, a_1 = 1, a_2 = 0, a_3 = 0, b_0 = 0, b_1 = 0, b_2 = 1, b_3 = 0. Now we perform the long multiplication:

    \[ \begin{array}{lccccccc} & & & & a_3 & a_2 & a_1 & a_0 \\ \cdot & & & & b_3 & b_2 & b_1 & b_0 \\ \hline \\ & & & & a_3 b_0 & a_2 b_0 & a_1 b_0 & a_0 b_0 \\ & & & a_3 b_1 & a_2 b_1 & a_1 b_1 & a_0 b_1 & \\ & & a_3 b_2 & a_2 b_2 & a_1 b_2 & a_0 b_2 & & \\ {+} & a_3 b_3 & a_2 b_3 & a_1 b_3 & a_0 b_3 & & & \\ \hline \end{array} \]

Using the previously found values we obtain:

    \[ \begin{array}{lccccccc} & & & & 0 & 0 & 1 & 1 \\ \cdot & & & & 0 & 1 & 0 & 0 \\ \hline \\ & & & & 0 \cdot 0 & 0 \cdot 0 & 1 \cdot 0 & 1 \cdot 0 \\ & & & 0 \cdot 0 & 0 \cdot 0 & 1 \cdot 0 & 1 \cdot 0 & \\ & & 0 \cdot 1 & 0 \cdot 1 & 1 \cdot 1 & 1 \cdot 1 & & \\ {+} & 0 \cdot 0 & 0 \cdot 0 & 1 \cdot 0 & 1 \cdot 0 & & & \\ \hline & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{array} \]

The result is equal to 12, which comes from 0 \cdot 1 + 0 \cdot 2 + 1\cdot 4 + 1 \cdot 8 + 0 \cdot 16 + 0 \cdot 32 + 0 \cdot 64. We could write our result using the following expression:

    \begin{gather*} a \cdot b = \\ a_0 \cdot b_0 + 2 \cdot a_1 \cdot b_0 + 4 \cdot a_2 \cdot b_0 + 8 \cdot a_3 \cdot b_0 + \\ + 2 \cdot \left( a_0 \cdot b_1 + 2 \cdot a_1 \cdot b_1 + 4 \cdot a_2 \cdot b_1 + 8 \cdot a_3 \cdot b_1 \right) + \\ + 4 \cdot \left( a_0 \cdot b_2 + 2 \cdot a_1 \cdot b_2 + 4 \cdot a_2 \cdot b_2 + 8 \cdot a_3 \cdot b_2 \right) + \\ + 8 \cdot \left( a_0 \cdot b_3 + 2 \cdot a_1 \cdot b_3 + 4 \cdot a_2 \cdot b_3 + 8 \cdot a_3 \cdot b_3 \right) \end{gather*}

Which in our example is equal to:

    \begin{gather*} 3 \cdot 4 = \\ 1 \cdot 0 + 2 \cdot 1 \cdot 0 + 4 \cdot 0 \cdot 0 + 8 \cdot 0 \cdot 0 + \\ + 2 \cdot \left( 1 \cdot 0 + 2 \cdot 1 \cdot 0 + 4 \cdot 0 \cdot 0 + 8 \cdot 0 \cdot 0 \right) + \\ + 4 \cdot \left( 1 \cdot 1 + 2 \cdot 1 \cdot 1 + 4 \cdot 0 \cdot 1 + 8 \cdot 0 \cdot 1 \right) + \\ + 8 \cdot \left( 1 \cdot 0 + 2 \cdot 1 \cdot 0 + 4 \cdot 0 \cdot 0 + 8 \cdot 0 \cdot 0 \right) = \\ 0 + 2 \cdot 0 + 4 \cdot \left( 1 + 2 \right) + 8 \cdot 0 = \\ 0 + 0 + 4 \cdot 3 + 0 = 12 \end{gather*}

Since we cannot multiply two variables (because we would get a non-linear constraint), we need to represent every multiplication of two digits (two binary variables) as their conjunction.

Performance

As we can see, presented approach is rather slow. Imagine that we are going to multiply two integers with 30 digits each. This requires over 900 temporary variables (we need to calculate conjunction for every pair of integers). In fact we need O(n^2) temporary variables to perform multiplication. When we come to calculating \max function we will see that we can do better using only O(n) variables.

Summary

To sum up, our algorithm comes as follows: we first find the unsigned magnitude representations of multiplicand and the multiplier, next we calculate conjunction of every digit of the multiplicand and every digit of the multiplier, and finally we form the result by summing the digits multiplied by correct weights.

In the next part we are going to define other common operators: division, remainder. We will also calculate powers and roots.

]]> https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/feed/ 3