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

Today we are going to implement something simple — Factorial function. We will use tricks similar to the ones used in previous part.

Introduction

Factorial function is defined naturally for all non-negative integers. Basically, it is a product of all positive integers less than or equal to the argument of the function. Additionally, the factorial of zero is defined as one. We will define exactly the same using the following variables:

    \begin{gather*} n, x \in \mathbb {Z_+} \cup \{ 0 \} \\ n! = x = \prod_{i=1}^{n} i \\ \end{gather*}

If you try to calculate this function for some small values you will notice that the factorial function rises really fast. For instance, 10! = 3628800. This means that it is no use in considering really big arguments because we will not be able to represent them using casual int32 representation. For our purposes we will assume that n \le 12.

Actual formula

Since we know the upper bound for n we can easily implement the formula:

    \[ x = \prod_{i=0}^{11} \max \left(1,  n - i \right) \]

This works in the following way: because n \le 12, we need to multiply at most 12 numbers. In every loop iteration we subtract i from n and take the maximum of the difference and one. We do that because we don’t know the value of n and we cannot allow the result to be zeroed. Take a look at this example:

    \[ x = 5! = \max(1, 5 - 0) \cdot \max(1, 5 - 1) \cdot \max (1, 5 - 2) \cdot \ldots \cdot \max(1, 5-11) = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 \cdot 1 \ldots \cdot 1 = 120 \]

For every i greater or equal to n the maximum function returns 1 so we can be sure that the result is not zeroed. What’s more, we have 0! = 1 as we wanted before.

Summary

So far we have been using ILP to implement various operations using declarative approach. We have seen that even though ILP uses only trivial tools we are able to implement some fancy functions. We have also seen how to implement strictly imperative construct (if). In the next part we are going to implement another thing from imperative world: loop. Stay tuned.