ptshen

We can use conventional mathematical functions as a programming language. This section was inspired by a YouTube video covering Willian's Formula (a function that calculates the $n$ -th prime), as well as another video covering the basics of mathematical programming. Most mathematical programming is not practical, but it's interesting to see how programs can be designed using pure mathematical syntax. In mathematical programming, design choices are made to control the flow of data, which reminds me of digital circuits and gating in neural network architectures. Simple perceptron networks that attempt to simulate logical operators require mathematical expressions.

Useful Identities and Functions

Sign function:

\operatorname{sgn}(x) = \frac{|x|}{x}, \quad x \neq 0

Differentiable Sign Function (Approximation). We approximate the non-differentiable sign function using a sigmoid:

\operatorname{sgn}(x) \approx 2\sigma(kx) - 1, \quad \text{where } \sigma(x) = \frac{1}{1 + e^{-x}}.

As $k \to \infty$ , this approximation converges pointwise to $\operatorname{sgn}(x)$ .

Maximum of two numbers:

\max(a,b) = \frac{a+b}{2} + \frac{|a-b|}{2}

Minimum of two numbers:

\min(a,b) = \frac{a+b}{2} - \frac{|a-b|}{2}

Integer indicator function (returns $1$ if $n$ is an integer, $0$ otherwise):

\mathbf{1}_{\mathbb{Z}}(n) = \left\lfloor \cos^2(\pi n) \right\rfloor

Logical operations (assume $f$ and $g$ are functions that return $1$ if true and $0$ if false):

Negation (NOT):

\lnot f = 1 - f

Logical OR:

f \lor g = \operatorname{sgn}(f+g)

Logical AND:

f \land g = f \cdot g

Logical XOR:

f \oplus g = |f-g|

DeMorgan's Law:

1-\operatorname{sgn}\!\left(\sum_{j=1}^{n}\mathbf{1}_{j}\right) = \prod_{j=1}^{n}(1-\mathbf{1}_{j})

Converting Conditional Functions into Mathematical Expressions

Consider a function defined piecewise by a condition:

f(x) = \begin{cases} a, & x > 10, \\ b, & 5 \le x < 10, \\ c, & x < 5. \end{cases}

We can express this as a single-line mathematical expression using indicator functions:

f(x) = a \, \mathbf{1}_{\{x>10\}} + b \, \mathbf{1}_{\{5 \le x < 10\}} + c \, \mathbf{1}_{\{x < 5\}}.

This works because the conditions in a piecewise function are mutually exclusive (or "one-hot"): exactly one condition is satisfied at a time. For example, $x$ cannot simultaneously satisfy both $x > 10$ and $5 \le x < 10$ . The indicator function $\mathbf{1}_{\{\cdot\}}$ equals 1 when the condition is true and 0 otherwise, allowing us to sum all terms while only the active condition contributes to the function's value.

In practice, you will need to construct your own indicator functions using a concoction of conventional mathematical functions. The following exercises will ask you to construct basic indicator functions e.g. equality, less than, etc.

Exercises

I recommend using Desmos to construct your functions, which makes it easier to check your work. Also, the solution to these exercises look complicated not because they are complicated, but because math can be a horrible programming language!

Write a mathematical function that checks equality between two numbers (returns $1$ if true, $0$ otherwise).
Write mathematical functions for strict and non-strict inequalities ( $<$ and $\leq$ ), returning $1$ if true and $0$ otherwise.
Write functions that compute the maximum and minimum of two numbers $a$ and $b$ .
Write a function that calculates the number of factors of a given integer $n$ .
Write a function that computes $n \bmod k$ without using the modulus operator.
Write a function that counts the number of $1$ s in the binary representation of an integer $n$ .
Write a function that rounds an integer $n$ down to the nearest power of 2.
Write a function that computes the XOR of two integers $a$ and $b$ .
Write a function that computes the number of ways the integers 1, 2, 5 can sum to integer $n$ (inspired by LeetCode: Coin Change II).

Solutions

Equality check (returns $1$ if $a=b$ , $0$ otherwise):

f_{\mathrm{eq}}(a,b) = 1 - \left( \operatorname{sgn}(a-b) \right)^2

Strict less-than (returns $1$ if $a < b$ , $0$ otherwise):

f_{\mathrm{slt}}(a,b) = \frac{\operatorname{sgn}(b-a)+1}{2} \cdot \left(1 - f_{\mathrm{eq}}(a,b)\right)

Less-than-or-equal-to (returns $1$ if $a \le b$ , $0$ otherwise):

f_{\mathrm{leq}}(a,b) = \frac{\operatorname{sgn}(b-a)+1}{2} + \frac{1}{2} f_{\mathrm{eq}}(a,b)

Maximum of two numbers:

\max(a,b) = a \cdot \left\lceil \frac{\operatorname{sgn}(a-b)+1}{2} \right\rceil + b \cdot \left\lceil \frac{\operatorname{sgn}(b-a)+1}{2} \right\rceil \cdot \left(1 - f_{\mathrm{eq}}(a,b)\right)

Minimum of two numbers:

\min(a,b) = a \cdot \left\lceil \frac{\operatorname{sgn}(b-a)+1}{2} \right\rceil + b \cdot \left\lceil \frac{\operatorname{sgn}(a-b)+1}{2} \right\rceil \cdot \left(1 - f_{\mathrm{eq}}(a,b)\right)

Number of factors of $n$ :

\sum_{j=1}^{n} \left\lfloor \cos^2\!\left( \pi \cdot \frac{n}{j} \right) \right\rfloor

$n \bmod k$ without using mod:

n - k \cdot \left\lfloor \frac{n}{k} \right\rfloor

Number of ones in the binary representation of $n$ :

\sum_{j=1}^{\lfloor \log_2 n \rfloor + 1} \left( 1 - f_{\mathrm{eq}} \!\left( 0,\; \operatorname{mod}(n,2^j) - \operatorname{mod}(n,2^{j-1}) \right) \right)

Round integer down to nearest power of 2:

Let $c = \lfloor \log_2(n) \rfloor + 1$ . Then:

\sum_{j=1}^{c} 2^{c-j} \cdot \Biggl( 1 - \operatorname{sgn} \Biggl( \sum_{l=1}^{j-1} f_{\mathrm{eq}} \Bigl( 1, \ \operatorname{mod} \Bigl( \Bigl\lfloor \frac{n}{2^{c-l}} \Bigr\rfloor, 2 \Bigr) \Bigr) \Biggr) \Biggr)

The expression above works using bit manipulation, but a simpler expression is:

2^{\lfloor \log_2(n) \rfloor}

XOR function on two integers $a$ and $b$ :

\begin{align*} c_{1} &= \lfloor \log_{2}(a) \rfloor + 1, \\ c_{2} &= \lfloor \log_{2}(b) \rfloor + 1, \\ f_{XOR}(a,b) &= \sum_{j=0}^{\min(c_{1},c_{2})-1} 2^{j} \left| \operatorname{mod}\!\left(\left\lfloor \frac{a}{2^{j}} \right\rfloor, 2\right) - \operatorname{mod}\!\left(\left\lfloor \frac{b}{2^{j}} \right\rfloor, 2\right) \right| \\ &\quad + \sum_{j=\min(c_{1},c_{2})}^{\max(c_{1},c_{2})-1} 2^{j} \left[ f_{slt}(a,b) \cdot f_{eq}\!\left(1, \operatorname{mod}\!\left(\left\lfloor \frac{b}{2^{j}} \right\rfloor, 2\right)\right) + f_{slt}(b,a) \cdot f_{eq}\!\left(1, \operatorname{mod}\!\left(\left\lfloor \frac{a}{2^{j}} \right\rfloor, 2\right)\right) \right] \end{align*}

Coin Change II:

\sum_{i=0}^{n} \sum_{j=0}^{n} \sum_{k=0}^{n-j} f_{\mathrm{eq}}\!\left(j+k,\,n-i\right) \, f_{\mathrm{eq}}\!\left(0,\,\operatorname{mod}\!\left(j,2\right)\right) \, f_{\mathrm{eq}}\!\left(0,\,\operatorname{mod}\!\left(k,5\right)\right)

Limitations of Mathematical Programming

One annoying problem in mathematical programming is that math does not have a concept of mutable variable in the sense that as we pass a value through a function, we do not have a variable that updates through computation. As a result, our programs were verbose and hard to understand to the reader.

On the other hand, programming offers mutable variables. Consider the following program:

foo = 0
for i in range(100):
    foo = foo + 1

In this example, the variable foo is a mutable variable, since its value changes as the program is executed. In addition, we are able to reference the new value after assignment from a previous iteration. This would have been extremely useful in the solutions (for example, the question that asks to round an integer down to the nearest power of 2), since the condition used in the solution repeatedly checks if the first $j$ bits contain a 1, when an array can reduce this check into a lookup.