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.

Table of Contents

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.