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

In the first part we defined Boolean algebra operators using ILP. Last time we implemented multiplication. Today we are going to define another basic operators: division and remainder (modulo). We are also going to see how to calculate powers and roots with constant degree.

Table of Contents

Division

We already know how to multiply variables and now we will use this skill to divide numbers. We will perform integer division so the result of the operation will be an integer. Formally:

$\begin{gather*} a \in \mathbb{Z_+} \cup \{0\}\\ b \in \mathbb{Z_+}\\ x \in \mathbb{Z_+} \cup \{0\}\\ x = \left\lfloor\frac{a}{b}\right\rfloor \end{gather*}$

We want to divide $a$ by $b$ and take only integer part of the result. You probably remember from school that division can be seen as an inverted multiplication and we will use this intuition. The result is a maximum possible number that multiplied by $b$ is not greater that $a$ . Formally:

$\begin{gather*} x \cdot b \le a\\ \left(x+1\right) \cdot b \ge a + 1 \end{gather*}$

You might wonder why we need to add $1$ in the second inequality but this is required when we try to calculate $\left\lfloor\frac{1}{1}\right\rfloor$ .

Remainder

Previously we ignored the non-integer part of the division result, however, we might want to use this amount which is left over. In fact this is rather easy. First, let’s define the actual number we would like to calculate:

$\begin{gather*} a \in \mathbb{Z_+} \cup \{0\}\\ b \in \mathbb{Z_+}\\ x \in \mathbb{Z_+} \cup \{0\}\\ x \le b-1 \\ x \equiv a \mod b \end{gather*}$

We can obtain the result by dividing the numbers and then multiplying them back and subtracting. Since the division ignores the remainder, it will not be included in multiplication and we will be able to extract it using subtraction. See:

$x = a - \left(\frac{a}{b}\right)\cdot b$

Of course here we perform the integer division defined in previous section.

Power

In this section we will calculate the power of a number, however, we will only consider constant exponent. In one of the next posts we will see how to calculate powers using variable as an exponent, however, for now we will stick to constant value.
Let’s calculate:

$\begin{gather*} a \in \mathbb{Z_+} \cup \{0\}\\ b \in \mathbb{Z_+}, b \text{ is constant }\\ x = a^b \end{gather*}$

This can be seen as a multiplication performed $b$ times. For instance, to calculate $a^3$ we can calculate $a\cdot a\cdot a$ and this is the result. No magic this time.

Roots

Using similar concept as with division, we can calculate root of constant degree. Basically we are looking for a number which raised to the correct power is not greater than the radicand. So:

$\begin{gather*} a \in \mathbb{Z_+} \cup \{0\}\\ b \in \mathbb{Z_+}, b \text{ is constant }\\ x = \sqrt[b]{a} \end{gather*}$

The formula is as follows:

$\begin{gather*} x^b \le a\\ \left(x + 1 \right)^b \ge a + 1 \end{gather*}$

Power here is defined as in previous section.

Summary

Today we have seen how to calculate other basic mathematical operators. For now we are able to use Boolean algebra and perform basic computations. In the next part we will see how to compare numbers — we we will define relational operators. We will get back to powers using variable as an exponent in the next few posts, when we will know how to calculate $\max$ and $\min$ .