Using Modulus Arithmetic to Navigate a Circular List

I have to go thru my notes every so often to find the formula for navigating backwards, so I’ll post this stuff here in case anyone else finds it useful.

Modulus math is very handy for dealing with circular functions like time. In fact, I use this to blow the minds of kids (I’m always trying to pique their interest in math and other technical stuff).

I’ll say something like “When is 11 + 2 = 1”? They will insist it cannot be and I tell them they see that very computation on a regular basis. After I have them telling me there is ABSOLUTELY NO WAY 11+2 EQUALS 1, I ask them what they get when they add 2 hours to 11:00. 1 O’CLOCK!!

Anyway, when writing software it is really useful to use modulus math to solve these little problems. To get 1:00 in software, I’d write

x = (11 + 2) % 12

x will contain 1

If you aren’t familiar with the C % operator (a.k.a the mod operator in Pascal), in essence it returns the remainder.  A / B (assuming A and B are ints) returns the quotient. A % B returns the remainder.

int(11 / 2) is 5
  and
11 % 2 is 1

In fact, long ago when I wrote COBOL code, if I needed to do a MOD operation it was actually part of the DIVIDE statement:

DIVIDE  < literal-1 / data-item-1 >   INTO  < literal-2 / data-item-2 >
             GIVING  data-item-3... REMAINDER data-item-4...

Besides doing time calculations, I find modulus math very handy for treating an array as a circular list.

Most recently I implemented a simple LCD menu using the array:

const int listLen = 5;
char * list[listLen] = {"A","B","C","D","E"};

int i = 0;

When the program starts, it prints the first string in the list. It then waits for either an up or down button to be pressed:

// C like psuedo code
while (!done) {
    lcd_out(list[i]);
    if (!keyAvail()) {}
    key = getKey();
    if (key == keyUp)
        // compute new i where we go forward in the list
        i = i + 1;
    else if (key == keyDown)
        // compute new i where we go backward in the list
        i = i - 1;
    }

This works OK until we get to the end of the list. We need to wrap around when the user presses the up or down key.

Formula 1: Going forward from the last element to the first
i = (i + 1) % listLen

If i is 4, pointing to the last element in the array, formula 1 will add 1, giving 5. Then 5 % 5 is computed which is 0. We are now pointing back to the beginning of the list.

To go the other way:

Forumla 2: going backwards from the first element to the last
i = (i + (listLen-1)) % listLen

If i is currently 0, we add 4 (listLen-1), and get 4. Then 4 % 5 is 4, so we are correctly point to the last element in the list.

Formula 1 is easy to remember. Formula 2 I can never seem to make stick and have to look it up every time.

Here is the entire program in C like psuedo-code:

while (!done) {
    lcd_out(list[i]);
    if (!keyAvail()) {}
    key = getKey();
    if (key == keyUp)
        // compute new i where we go forward in the list
        i = (i + 1) % listLen;
    else if (key == keyDown)
        // compute new i where we go backward in the list
        i = (i + (listLen - 1)) % listLen;
    }

and Pascal-like psuedo-code:

while (not done) do
    lcd_out(list[i]);
    if (not keyAvail) {}
    key = getKey;
    if key = keyUp then
        // compute new i where we go forward in the list
        i := (i + 1) mod listLen
    else if key = keyDown then
        // compute new i where we go backward in the list
        i := (i + (listLen - 1)) mod listLen;
Advertisements
This entry was posted in c-arduino, c-lazarus and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s