# The beauty of mixed-radix bases

On the relationship between mixed-radix bases and array indexing

Numbers. They turn out to be pretty crucial, and everyone is familiar with
the decimal number system, or
base 10^{1}.
Programmers, of course, also tend to use decimal numbers, but binary and
hexadecimal also see frequent use (bases 2 and 16, respectively).
Occasionally one even comes across octal (base 8).

Programming languages generally support writing numbers in several of the
above, sometimes following the C convention of using a `0`

prefix for octal
numbers and `0x`

for hexadecimal numbers. Also common are functions to
convert integers to and from different bases, usually represented as a text
string^{2}.

There are a number of problems with using text strings to represent a
number. For instance, such functions are usually restricted to bases
*2 … 36* because only `[0-9a-z]`

are available as digits.
They are also quite annoying to manipulate, and fairly fragile (what if the
string doesn't follow the expected syntax?). Another representation would
be as a vector of integers, each element corresponding to one digit: there
is no need to represent the digits by characters, so you have no upper bound
on what base to support (other than restrictions on the integer type
itself).

Languages in the APL family (at least APL, J, K) tend to take this approach,
and in addition they also extend the “*base*” parameter to support
*vectors*. That is, instead of using the same base for every position (the
way decimal, binary etc work), we supply a vector with one base for each
position. This might seem really weird at first, but is how a mixed-radix
base works.

Why would we ever want different positions to take on different bases? One
everyday example would be representing time as days, hours, minutes and
seconds: there are 60 seconds to a minute, and 60 minutes to an hour, but of
course there are *24* hours to a day. Thus, our radix is `∞ 24 60 60`

.

The rest of this article will explore a (hopefully) surprising and interesting use of these conversion functions, making an argument along the way in favour of zero-indexing for arrays, and finally provide a practical example of this in the J programming language.

We will return to mixed-radix bases in a moment, but first I want to briefly
introduce the other party of this story: the array. In particular I want to
introduce you to *rectangular arrays*, multidimensional arrays that
conceptually can be thought of as a rectangle (or cuboid, or …), where each
axis has a given length. Together, the length along each axis (from highest
dimension to lowest) gives us the *shape* of the array, and the length of
the shape is its *rank* (or number of dimensions). Arrays of rank 1 are
typically called *vectors*.

Arrays of higher dimensions (such as matrices) can be stored in a lot of
different ways. The by far most common approach today is row-major order,
in which you read out the matrix in the order that you would read English
text: left-to-right, then top-to-bottom. Elements adjacent in a row are
stored adjacent in memory, but elements adjacent in a column are stored far
apart (one matrix-width apart, in fact). The complementary approach,
favouring columns, would be column-major order, notably seen in
Fortran. There are other interesting approaches
too^{3},
but we will focus on only
row-major order, which is what you see in C.

Another common example of a matrix in row-major order would be framebuffers
for a screen. In fact, a framebuffer is essentially a rank-3 array: its
shape would be `height width depth`

, where depth is the number of channels
(often 3 or 4, for red, green, blue, and possibly alpha).

Anyone who has ever worked with 2D graphics has probably written an
expression of the form *y⋅width + x* or *(y⋅width + x)⋅depth + channel* to
manipulate a particular pixel at some particular coordinate.

Let us take a moment and think about what we are doing here: we are indexing
a rectangular array. Consider the example with colour depth, whose shape is
`height width depth`

: we are indexing it at coordinate *(y, x, channel)*,
yielding the expression *(y⋅width + x)⋅depth + channel*. This is,
inherently, treating the number *(y, x, channel)* as a base-```
height width
depth
```

number, converting it to a single integer.

Which is to say, indexing a multidimensional array is essentially radix conversion. This isn't restricted to two or three dimensions, of course, but works for any multidimensional array laid out in row-major order.

We can look at this from a slightly different angle too: nested loops in an imperative language. Consider nested loops as shown below.

```
for (int i = 0; i < I; i++) {
for (int j = 0; j < J; j++) {
for (int k = 0; k < K; k++) {
...
}
}
}
```

(Of course, one common use of such nested loops is to iterate along the axes of a rectangular array… so you might already see where this is heading.)

This isn't too bad in the case above with only three loops, but it is easy to see why this wouldn't look nice with more deeply-nested loops. Sometimes one doesn't even know the depth ahead of time; the number of nested loops needed might only be known at runtime. While it is possible to solve this recursively, it quickly gets very ugly.

So, what can we do instead? Well, in the above case the total number of
iterations will be *I⋅J⋅K*, so could we maybe collapse the loops into a
single one, looping from *0* to *I⋅J⋅K*? The answer is yes, and to extract
the individual *i,j,k* values we… perform a base conversion! In this case
we're going in the other direction, from a single compound number to its
representation in base `I J K`

.

(As an aside, this also makes a bit of an argument in favour of indexing
arrays from 0 rather than 1: a decimal number's digits takes on values
*0 … 9*, and we have shown how rectangular array indexing
behave very similarly to mixed-radix numbers, so it follows fairly naturally
to have array indices be indexed from 0 as well. It just makes the
mathematical relationships more elegant.)

Finally, I want to show an example of making use of
base-conversion-as-array-indexing in practice, from the source that first
taught me about this relationship. This is a definition in J from Ben
Gorte, generalising the built-in `I.`

to higher dimensions. J has a
fairly… unconventional syntax, but I will focus on explaining the semantics
of what is going on here.

```
Idot =: $ #: I.@:,
```

First, we need to know what `I.`

does in the first place. It is quite
simple: given a boolean vector (booleans in J are represented by 0 and 1 for
*false* and *true*, respectively), return the indices of all the 1's in
ascending order. Thus, `I. 0 1 1 0 0 1 0 0`

produces `1 2 5`

(the elements
being zero-indexed, starting from the left).

One useful way of generalising this to higher dimensions would be to produce
a list of vectors, each vector giving the coordinate for a 1.
Unfortunately, for a variety of reasons this isn't how `I.`

generalises, so
we will have to implement it ourself. This is what `Idot`

, defined above,
is for.

Next, I will go through how this works step-by-step. The definition of
`Idot`

hinges on the fact that we already have `I.`

that works adequately
for vectors, so we want to make use of this and do some pre- and
post-processing to get the appropriate coordinates-of-ones as the result of
`Idot`

.

For preprocessing, we need to somehow turn the input array into a vector.
We do this by *ravelling* the array, essentially reading out its elements in
row-major order (the way it is laid out in memory). In practice, since the
data as it is in memory *is* already laid out properly, we only really need
to change the metadata. In C terms we essentially cast to `int *`

. After
this, we can apply `I.`

and get the indices of the ones in the ravelled
array.

Finally we need to postprocess the indices and turn them into vector
coordinates. This is of course a base conversion, making use of the
connection between array indexing and base conversion: we use antibase
(`#:`

) to expand each scalar into a vector, the radix of the conversion
being the shape (`$`

) of the original array. And thus, we have the result
we wanted!

Below is a REPL transcript of how this works out for a concrete example.

```
NB. index vector: increasing integers assembled into shape 2 3 4
i. 2 3 4
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
NB. pick out only the values 5 and 18, define this boolean array as `array`
] array =. 5 18 e.~ i. 2 3 4
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 0 0 0
, array NB. ravel array
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
I. , array NB. indices of 1's in ravelled array
5 18
$ array NB. shape of array
2 3 4
($ array) #: I. , array NB. use shape as radix in a base conversion
0 1 1
1 1 2
($ #: I.@,) array NB. same thing, expressed tacitly
0 1 1
1 1 2
```

The main takeaway of this article is that base conversion can crop up in the most surprising of places. I happened to find the connection to rectangular arrays particularly elegant and surprising, and so decided to focus on it. If you can think of other interesting, surprising uses of radix conversion (both of constant and mixed radix), I would love to hear about them!

- Yes, I am well aware that every base is base 10 :) ↩
- See
`parseInt`

/`toString`

in Java, JavaScript, C#;`strtol`

in C; etc. ↩ - One interesting approach is to store the elements as you would enumerate them along antidiagonals (top-right to bottom-left), starting with the top-left element, then the two elements neighbouring it, and so on. This approach makes it a bit more involved to index a particular element, but one benefit is that it is possible to (lazily) store arrays that are infinite along one or several axes. ↩