Arithmetic – 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 3 – Division, remainder, exponentiation, roots https://blog.adamfurmanek.pl/2015/09/05/ilp-part-3/ https://blog.adamfurmanek.pl/2015/09/05/ilp-part-3/#comments Sat, 05 Sep 2015 10:00:32 +0000 http://blog.adamfurmanek.pl/?p=231 Continue reading ILP Part 3 – Division, remainder, exponentiation, roots]]>

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.

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.

]]> https://blog.adamfurmanek.pl/2015/09/05/ilp-part-3/feed/ 2 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