The beauty of mixed-radix bases

Numbers. They turn out to be pretty crucial, and everyone is familiar with the decimal number system, or base 10¹. 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².

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³, 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!

1. Yes, I am well aware that every base is base 10 :) ↩
2. See parseInt/toString in Java, JavaScript, C#; strtol in C; etc. ↩
3. 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. ↩