Previously, we talked about writing programming functions in "math notation". We discussed simple functions such as $\text{min}(x, y)$, and $\text{eq}(x, y)$. Now let's take a look at writing a function to reverse the digits of a number.

Before showing you the function that we came up with to reverse a number, we have to define two functions. First, $\text{len}_b(x)$, which gives the number of digits in $x$ when written in base $b$. $$ \text{len}_b(x) = \big\lceil \log_b(x + 1) \big\rceil $$ Then, we have $\text{at}_b(x, i)$, which gives the digit at index $i$ of $x$ when written in base $b$. This is zero-indexed and $i=0$ refers to the least significant digit. For example $\text{at}_{10}(123, 0) = 3$. $$ \text{at}_b(x, i) = \left\lfloor \frac{\lvert x \rvert}{b^i} \right\rfloor \text{ mod } b $$ Here, $\text{mod}$ is an operator, not the equivalence class. Now, here's our definition of reverse, $$ \text{rev}_b(x) = \sum_{i = 0}^{\text{len}_b(x) - 1} \text{at}_b(x, i) \cdot b^{\text{len}_b(x) - i - 1} $$ Let's break this down. The $\Sigma$ can be described as a "loop". We loop through all of the valid indices $i$ of the digits in $x$. For each index $i$, we take the digit in $x$ at that index and "place" it in a new number at a new index $\text{len}_b(x) - i - 1$. Notice, this new index is exactly the index of this digit in the reversed number.

What's even cooler is that we can translate our definition of $\text{rev}$ back into code. Here's a snippet using Python,

Let's test it out here to verify that it it works:

Awesome! The first expression shows that $12345$ reversed when written in base $10$ comes out to $54321$, which is what we expected! Then we see that $\text{rev}(37001_8, 8) = 10073_8$, as expected. Finally we see that $\text{rev}(\text{deadbeef}_{16}, 16) = \text{feebdaed}_{16}$.

Even though this is over 10 times slower than the naive string-reversal approach, it's still pretty cool that this can be done using only binary operations.

Next, we'll talk about sorting the digits of an integer.