Saturday, May 23, 2015

Translating an arbitrary integer into a circular array index

A circular array is an array which is connected at the edges, that is, it has no beginning or end and traversing the array will eventually get you back to where you started. Of course in practice a normal array is used and the given index is mapped into a valid array index. This is usually done using modulo operations (the remainder after dividing the index by the array length). But what if you need to also allow negative indexes?

Let's say you have an array of length 5 and you want to use it as a circular array.

01234

If you start at index 2 and move 1 to the right then you end up in index 3. But if you move 3 to the right you end up in index 0. On the other hand if you move 3 to the left then you end up in index 4. Here are some other examples of this translation:

Starting indexAdd to itResultantTranslated index
2+133
2-122
4+150
0-1-14
2+340
2-3-14
2+794
2-7-50
2+15172
2-15-132

We need a general formula to map arbitrary resultant integers into corresponding indexes. The modulo operator will not map negative numbers correctly:

6 % 5 = 1
5 % 5 = 0
4 % 5 = 4
3 % 5 = 3
2 % 5 = 2
1 % 5 = 1
0 % 5 = 0
-1 % 5 = -1
-2 % 5 = -2
-3 % 5 = -3
-4 % 5 = -4
-5 % 5 = 0
-6 % 5 = -1

This is because if the whole number division of a negative number N divided by a positive number P is D, then the remainder would be the number X such that D*P + X = N holds. For example, 4/5 = 0 remainder 4, because 0*5 + 4 = 4. Another example, -4/5 = 0 remainder -4 because 0*5 + -4 = -4.

Now in order to get a mapping from arbitrary resultant integers to corresponding indexes in a circular array we need to use the following formula:

Given a resultant R and a length of array L, the corresponding index is
(R%L + L)%L