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.

Table of Contents

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.