Introduction

The whole idea of this post is to encourage you, or myself, when I re-read my own content, to reframe your applicable discrete or continuous problems appropriately as piecewise problems, as explored previously in my... ramblings.

While I won't pretend this is a foolproof, sure, method of solving all your problems, or deriving your own formulas, equations or the like, I present this as an alternative point of view, and one which grants you insight into my own areas of interest and problems. Moreover, it requires a line of thinking that you may not be able to align with straight away, but hopefully you can take away something from this post that helps you with this specific issue.

I explore two examples in particular in this post, both of which are algorithmically relevant to some of the programming I do, but more importantly, are worked through in a similar or same way.

As a preliminary disclaimer, the results yielded from these processes are often not performant, and are generally impractical for computation. With that being said, it's absolutely worth thinking about at the least, as it can bolster your understanding of pre-existing formulas.

Piecewise rules/guide briefly

We'll make use of our notation for a piecewise object once again, in the context of a single-variable piecewise function: \(\phi(x)=\left\{\mu_i(x),\quad C_i\mid i\in I\right\}\) where \(\mu\) is an index set of real or complex value functions, \(C\) is an index set of conditions and \(I\) indexes our values. Note, \(\mu_i(x)\) is taken as the value of \(\mu(x)\) when \(C_i\) is true.

Notably, we can briefly list rules that apply the same in terms of our regular operations:

\[ \begin{align*} \left\{\mu_i(x)+c,\quad C_i\mid i\in I\right\} &= \left\{\mu_i(x),\quad C_i\mid i\in I\right\}+c \\ \left\{a\cdot\mu_i(x),\quad C_i\mid i\in I\right\} &= a\cdot\left\{\mu_i(x),\quad C_i\mid i\in I\right\} \\ \left\{f(x),\quad C_i\mid i\in I\right\} &= f(x) & \textrm{(iff the piecewise object defines all of the function)} \\ \left\{a_i,\quad g(x)=a_i\mid i\in I\right\} &= g(x) & \textrm{(iff the piecewise object defines all of the function)} \\ \end{align*}\]

The important thing to note here is that these rules are only strict when we define the function entirely; that is, we're not working with an anonymous piecewise object, wherein the latter two rules would in fact restrict the functions which would be yielded.

Instead, we should consider these as guidelines; the objects we work with in this post are in fact akin to APOs, and so there are an infinite number of functions we could use instead.

Likewise, relevant to this post is the nesting of piecewise objects; the Mathematica documentation here has some examples. We also consider going 'backwards' with respect to this. This has been something I've demonstrated in previous posts, and so reading through those will help you grasp the idea behind it better.

Your own problems and derivations

When you're taught a lot of maths and shown new concepts, it is absolutely daunting to even have to think about coming up with your own ideas, your own formulas, whatnot to do things. Even if your formula is not unique or new, the value that you get from attacking them yourself using a constructive strategy/method is incalcuable.

Part of this process is deconstructing existing problems, formulas, etc., playing around with them, and subsequently coming up with your own. This is regardless of the uniqueness of the problem or solution.

(This blog is no different.)

Array (un-)flattening

Flattening

\(2\)-dimensional arrays

Suppose that we have a 2 dimensional array of 'width' \(w\) and 'height' \(h\), and that we want to represent a coordinate, or position, within that array, \((x,y)\), as an integer.

In order to do this, we first visually map out our array in terms of how we might represent each position:

\[ \begin{bmatrix} 0 & 1 & 2 & \dots & w-1 \\ w & w+1 & w+2 & \dots & 2w-1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ (h-1)w & (h-1)w+1 & (h-1)w+2 & \dots & wh-1 \end{bmatrix}\]

And so in position \((0,0)\) we have the representation of \(0\), and likewise in \((w-1,h-1)\) we have representation \(wh-1\).

Suppose we represent this as a bivariate function (keeping in mind that there are obviously a lot of values to consider, we pick the ones that might be the most relevant when working with the piecewise object):

\[ f(x,y)=\begin{cases} 0 & x=0 & y=0 \\ 1 & x=1 & y=0 \\ \vdots & \vdots & \vdots \\ w-1 & x=w-1 & y=0 \\ w & x=0 & y=1 \\ w+1 & x=1 & y=1 \\ \vdots & \vdots & \vdots \\ wh-1 & x=w-1 & y=h-1 \end{cases}\]

We can then take our \(x\) terms, and nest our piecewise function with respect to \(y\):

\[ f(x,y)=\begin{cases} \begin{cases} 0 & x=0 \\ 1 & x=1 \\ \vdots & \vdots \\ w-1 & x=w-1 \\ \end{cases} & y=0 \\ \begin{cases} w & x=0 \\ w+1 & x=1 \\ \vdots & \vdots \\ 2w-1 & x=w-1 \\ \end{cases} & y=1 \\ \vdots & \vdots \\ \begin{cases} (h-1)w & x=0 \\ (h-1)w+1 & x=1 \\ \vdots & \vdots \\ wh-1 & x=w-1 \\ \end{cases} & y=h-1 \\ \end{cases}\]

And simplifying a bit:

\[ \begin{align*} f(x,y) &=\begin{cases} \begin{cases} 0 & x=0 \\ 1 & x=1 \\ \vdots & \vdots \\ w-1 & x=w-1 \\ \end{cases} & y=0 \\ w+\begin{cases} 0 & x=0 \\ 1 & x=1 \\ \vdots & \vdots \\ w-1 & x=w-1 \\ \end{cases} & y=1 \\ \vdots & \vdots \\ (h-1)w+\begin{cases} 0 & x=0 \\ 1 & x=1 \\ \vdots & \vdots \\ w-1 & x=w-1 \\ \end{cases} & y=h-1 \\ \end{cases} \\ &=\begin{cases} 0 & x=0 \\ 1 & x=1 \\ \vdots & \vdots \\ w-1 & x=w-1 \\ \end{cases}+\begin{cases} 0 & y=0 \\ w & y=1 \\ \vdots & \vdots \\ (h-1)w & y=h-1 \\ \end{cases} \end{align*}\]

Factoring a \(w\) out of the latter term, we're left with the formula \(f(x,y)=x+wy\)

\(n\)-dimensional arrays

Consider that a \(3\) dimensional array can be considered to be an array of \(2\) dimensional arrays, and likewise more generally, an \(n\) dimensional array an array of \(n-1\) dimensional arrays.

For a 3 dimensional array, consider that we have a 'width', 'height' and 'length', rather than just the former two. Reasoning that our second term in the \(2\) dimensional formula was preceded by the width, we might consider that:

\[ f(x,y,z)=\begin{cases} f(x,y) & z=0 \\ wh+f(x,y) & z=1 \\ \vdots & \vdots \\ wh(l-1)+f(x,y) & z=l-1 \end{cases}\]

Which is simply \(f(x,y,z)=f(x,y)+whz=x+wy+whz\).

Inductively or through our piecewise method, we can show that for \(x_1,\dots,x_n\) and \(l_1,\dots,l_n\), that \(f(x_1,\dots,x_n)=f(x_1,\dots,x_n)+l_1l_2\dots l_{n-1}x_{n}\).

In other words, \(f(x_1,\dots,x_n)=\displaystyle\sum_{i=1}^{n}{x_i\prod_{j=1}^{i-1}{l_j}}\).

Unflattening

\(n\)-dimensional arrays

As you'll see, this process is slightly more long-winded. However, if you're more familiar with modular arithmetic, you might already have picked up how we could go about unflattening an array.

Let \(n=f(x_1,\dots,x_n)\). Then \(n\bmod l_1=x_1\). Likewise, \(\frac{n-x_1}{l_1}\bmod l_2=x_2\), and so on. We know this by observation; once we've obtained \(x_1\), we can subtract this from \(n\), our function, and since we know \(n-x_1\) is divisble by \(l_1\), we can divide by it. This way, we can repeat the process recursively until we've obtained \(x_1,\dots,x_n\).

\(2\)-dimensional arrays

The above process is achievable using piecewise techniques also, but still requires some knoweldge of modular arithmetic. For the sake of tedious working, we'll stick with 2 dimensional arrays.

Suppose we have a function \(g:\mathbb{R}\to\mathbb{R}^2\) that describes unflttening a 2 dimensional array. Suppose that we already know the 'width' \(w\) and we input a variable \(n\), then referring to the visualisation as before we have:

\[ g(n)=\begin{cases} (0,0) & n=0\\ (1,0) & n=1\\ \vdots & \vdots \\ (w-1,0) & n=w-1 \\ (0,1) & n=w \\ (1,1) & n=w+1 \\ \vdots & \vdots \\ (w-1,h-1) & n=wh-1 \end{cases}\]

We can split our piecewise up by tuple component:

\[ g(n)=\left(\begin{cases} 0 & n=0\\ 1 & n=1\\ \vdots & \vdots \\ w-1 & n=w-1 \\ 0 & n=w \\ 1 & n=w+1 \\ \vdots & \vdots \\ w-1 & n=wh-1 \end{cases},\begin{cases} 0 & n=0\\ 0 & n=1\\ \vdots & \vdots \\ 0 & n=w-1 \\ 1 & n=w \\ 1 & n=w+1 \\ \vdots & \vdots \\ h-1 & n=wh-1 \end{cases}\right)\]

Notice that if we take the conditions of \(x\) coordinate of the tuple and take them \(\bmod w\), then the right hand side of our conditions exactly match our values.

With our \(y\) coordinate of the tuple, if we divide by \(w\) and take the floor of it, we likewise achieve the same conditions as values. See:

\[ g(n)=\left(\begin{cases} 0 & n\equiv 0 \pmod w\\ 1 & n\equiv 1 \pmod w\\ \vdots & \vdots \\ w-1 & n\equiv w-1 \pmod w\\ 0 & n\equiv 0 \pmod w \\ 1 & n\equiv 1 \pmod w\\ \vdots & \vdots \\ w-1 & n\equiv w-1 \pmod w \end{cases},\begin{cases} 0 & \left\lfloor\frac{n}{w}\right\rfloor=0\\ 0 & \left\lfloor\frac{n}{w}\right\rfloor=0\\ \vdots & \vdots \\ 0 & \left\lfloor\frac{n}{w}\right\rfloor=0 \\ 1 & \left\lfloor\frac{n}{w}\right\rfloor=1 \\ 1 & \left\lfloor\frac{n}{w}\right\rfloor=1 \\ \vdots & \vdots \\ h-1 & \left\lfloor\frac{n}{w}\right\rfloor=h-1 \end{cases}\right)\]

And so therefore we have the function \(g(n)=\left(n\bmod w, \left\lfloor\frac{n}{w}\right\rfloor\right)\).

Base conversion

Something that often pops up in especially computer science is the idea of number bases, or positional numeral systems. Such topics often begin with an idea of how these work, in comparison to the widely-used decimal system, and then how to convert between these, and do arithmetic with them.

What often fails to be conveyed is the intuition or derivation of such conversions, especially when going to and from decimal, or base \(10\). It is here where we might be able to derive our own such formulas to understand the algorithms handed to us.

We begin by letting our intuition guide us. Suppose we represent a decimal number in standard form, and we opt to represent a number in any other base by its digits specifically; we'll stick to non-negative integers.

Converting from binary to decimal with \(2\) digits

We start small! To get an intiuition for how we approach this problem overall, we lay out our respective values in piecewise form via a function which takes in 2 digits, and outputs a decimal:

\[ F(d_1,d_2)=\begin{cases} 0 & d_1 = 0 & d_2 = 0 \\ 1 & d_1 = 0 & d_2 = 1 \\ 2 & d_1 = 1 & d_2 = 0 \\ 3 & d_1 = 1 & d_3 = 1 \end{cases}\]

Let's do the same as before; we factor our piecewise by nesting using the variable \(d_2\):

\[ F(d_1,d_2)=\begin{cases} \begin{cases} 0 & d_1 = 0 \\ 2 & d_1 = 1 \end{cases} & d_2 = 0 \\ \begin{cases} 1 & d_1 = 0 \\ 3 & d_1 = 1 \end{cases} & d_2 = 1 \\ \end{cases}\]

We proceed to simplify:

\[ F(d_1,d_2)=\begin{cases} 2\begin{cases} 0 & d_1 = 0 \\ 1 & d_1 = 1 \end{cases} & d_2 = 0 \\ 1+2\begin{cases} 0 & d_1 = 0 \\ 1 & d_1 = 1 \end{cases} & d_2 = 1 \\ \end{cases}=2\begin{cases} 0 & d_1 = 0 \\ 1 & d_1 = 1 \end{cases}+\begin{cases} 0 & d_2 = 0 \\ 1 & d_2 = 1 \end{cases}\]

This yields the formula \(F(d_1,d_2)=2d_1+d_2\). (And at this point, you would be right to suspect that we have powers of two here!)

Convert from a base to decimal

Now that we've trialled converting a 2 digit binary number to decimal, let us consider any number of digits in any base. Suppose that we're given a number \(N\) in base \(b\), with digits \(a_1,a_2,\dots,a_n\). We can create a function such that:

\[ F(a_1,a_2,\dots,a_n)=\begin{cases} 0 & a_1 = 0 & a_2 = 0 & \cdots & a_{n-1}=0 & a_n = 0 \\ 1 & a_1 = 0 & a_2 = 0 & \cdots & a_{n-1}=0 & a_n = 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ b-1 & a_1 = 0 & a_2 = 0 & \cdots & a_{n-1}=0 & a_n=b-1 \\ b & a_1 = 0 & a_2 = 0 & \cdots & a_{n-1}=1 & a_n=0 \\ b+1 & a_1 = 0 & a_2 = 0 & \cdots & a_{n-1}=1 & a_n=1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 2b-1 & a_1 = 0 & a_2 = 0 & \cdots & a_{n-1}=1 & a_n=b-1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ b^n-1 & a_1=b-1 & a_2=b-1 & \cdots & a_{n-1}=b-1 & a_n=b-1 \end{cases}\]

Woah. That's a lot of numbers. Take the time now to convince you that these numbers are correct by playing around with some other bases. On an intuitive level, this makes sense, but formulating it is what we're doing here!

Let us, once again, factor our piecewise object. We make sure to focus on \(a_n\), noting that no other variables change, and that we preserve order of \(a_1,a_2,\dots,a_{n-1}\) with respect to \(a_n\). Given the absolute monstrosity that arises from this, we won't write the resulting object here, but we get the following recurrence relation:

\[ F(a_1,a_2,\dots,a_n)=b\cdot F(a_1,a_2,\dots,a_{n-1})+a_n \\ F(a)=a\]

Solving this yields the following formula:

\[ F(a_1,a_2,\dots,a_n)=\sum_{m=1}^{n}{a_mb^{n-m}}\]

How many digits do I need?

Consider from our above derivation that for a base \(b\) and \(n\) digits we had a maximum value of \(b^n-1\).

Suppose that we're given an integer \(m\), and we need to find the smallest \(n\) such that \(m\leq b^n-1\). We can rearrange for \(n\) giving us \(n\geq \log_b(m+1)\). Therefore, the smallest integer \(n\) that satisfies this inequality is \(n=\left\lceil\log_b(m+1)\right\rceil\).

Converting to binary from decimal with \(2\) digits

In the same vein as before, we construct our function with 2 digits:

\[ f(n)=\begin{cases} (0,0) & n=0 \\ (0,1) & n=1 \\ (1,0) & n=2 \\ (1,1) & n=3 \end{cases}\]

Splitting the piecewise element-wise (with respect to the tuple):

\[ f(n)=\left(\begin{cases} 0 & n=0 \\ 0 & n=1 \\ 1 & n=2 \\ 1 & n=3 \end{cases},\begin{cases} 0 & n=0 \\ 1 & n=1 \\ 0 & n=2 \\ 1 & n=3 \end{cases},\right)\]

Notice that the first digit is similar to our unflattening as before; if we divide each condition by \(2\) and then take the floor, we match our values. Likewise with the latter digit, we take the conditions \(\bmod 2\) and the same thing happens.

An important observation here, also, is if we take the first digit \(\bmod 2\) then we have the same thing (this'll be important below). Likewise, \(n=\left\lfloor\frac{n}{2^0}\right\rfloor\) in our case.

We therefore have: \(f(n)=\left(\left\lfloor\frac{n}{2}\right\rfloor,n\bmod 2\right)\).

Convert to a base from decimal

As you're probably familiar with by now, we can start off just the same as previous examples, with our appropriate values and condition and base \(b\):

\[ F(n)=\begin{cases} (0,0,\dots,0,0,0) & n=0 \\ (0,0,\dots,0,0,1) & n=1 \\ \vdots & \vdots \\ (0,0,\dots,0,0,b-1) & n=b-1 \\ (0,0,\dots,0,1,0) & n=b \\ (0,0,\dots,0,1,1) & n=b+1 \\ \vdots & \vdots \\ (0,0,\dots,1,0,0) & n=b^2 \\ \vdots & \vdots \\ (b-1,b-1,\dots,b-1,b-1,b-1) & n=b^N-1 \end{cases}\]

How large are our tuples? The simple answer is these are \(N\)-tuples, where \(N\) is given by \(\left\lceil\log_b(n+1)\right\rceil\); rather, the number of digits in our resultant base \(b\) number.

Splitting by digit again:

\[ F(n)=\left(\begin{cases} 0 & n=0 \\ 0 & n=1 \\ \vdots & \vdots \\ 0 & n=b-1 \\ 0 & n=b \\ 0 & n=b+1 \\ \vdots & \vdots \\ 0 & n=b^2 \\ \vdots & \vdots \\ b-1 & n=b^N-1 \end{cases},\begin{cases} 0 & n=0 \\ 0 & n=1 \\ \vdots & \vdots \\ 0 & n=b-1 \\ 0 & n=b \\ 0 & n=b+1 \\ \vdots & \vdots \\ 0 & n=b^2 \\ \vdots & \vdots \\ b-1 & n=b^N-1 \end{cases},\dots,\begin{cases} 0 & n=0 \\ 0 & n=1 \\ \vdots & \vdots \\ 0 & n=b-1 \\ 1 & n=b \\ 1 & n=b+1 \\ \vdots & \vdots \\ 0 & n=b^2 \\ \vdots & \vdots \\ b-1 & n=b^N-1 \end{cases},\begin{cases} 0 & n=0 \\ 1 & n=1 \\ \vdots & \vdots \\ b-1 & n=b-1 \\ 0 & n=b \\ 1 & n=b+1 \\ \vdots & \vdots \\ 0 & n=b^2 \\ \vdots & \vdots \\ b-1 & n=b^N-1 \end{cases}\right)\]

If you carefully draw out these values a bit more, you'll find the recurring patterns that appear in each one. In any case, we can do the same thing with our conditions as before, and formulate this as:

\[ F(n)=\left(\left\lfloor\frac{n}{b^{N-1}}\right\rfloor\bmod b,\left\lfloor\frac{n}{b^{N-2}}\right\rfloor\bmod b,\dots,\left\lfloor\frac{n}{b^{1}}\right\rfloor\bmod b,\left\lfloor\frac{n}{b^{0}}\right\rfloor\bmod b\right)\]

Since there are so many values, it can be incredibly difficult to accurately verify. But since we have a structure in which we can express these values systematically, it will become very obvious if you've miscalculated somewhere!

Conclusion

Despite the apparent complexity of the problems demonstrated in this post, this post is intended to show you how you might go about thinking and rephrasing them in terms of piecewise objects, and then following through. Even though the post, as always, fails to demonstrate it, there was a non-insignifcant amount of time put into thinking about these problems, framing them, and then getting a result.