David Owen’s blog

Oftentimes, calculation may proceed normally, and we only need to worry about wrap-around to maintain precision or preserve assumptions that make other operations easier to reason about.

Calculation

Most languages have mod operators, sometimes called % for integers and fmod for floats. Passing all calculations through mod will help maintain our assumptions.

Suppose we are using an array of size n to represent a ring-like structure, such that element 0 is immediately right of element n-1 in the same way that element 3 is immediately right of element 2. A routine to decrement 2 from an element and add 1 to each of the immediately left and right neighbors might look like this:

def disperse(a, i):
    n = len(a)

    if i == 0:
        left = n - 1
    else:
        left = i - 1

    if i == n-1:
        right = 0
    else:
        right = i + 1

    a[i]     = a[i]     - 2
    a[left]  = a[left]  + 1
    a[right] = a[right] + 1

def disperse(a, i):
    n = len(a)

    left  = (i - 1) % n
    right = (i + 1) % n

    a[i]     = a[i]     - 2
    a[left]  = a[left]  + 1
    a[right] = a[right] + 1

If you must deal with 1-based arrays, you can still use mod but must compensate for the +1 offset. Your operations should all follow a pattern similar to this:

mod(f(x - 1), n) + 1

So, decrement the value by 1 to make it 0-based, apply your operation, apply mod, then increment by 1 to make it 1-based again. Sometimes care must be taken in how your operation f is implemented. Here's an example of the overall method—the same disperse method from above, for 1-based arrays:

def disperse(a, i):
    n = len(a)

    # These can be simplified:
    left  = ((i-1 - 1) % n) + 1
    right = ((i-1 + 1) % n) + 1

    a[i]     = a[i]     - 2
    a[left]  = a[left]  + 1
    a[right] = a[right] + 1

Comparison

Life is not so easy when attempting to make comparisons between values in a modular system. Let's say you want to determine whether angle X is clockwise or counter-clockwise of angle A, whichever requires the least rotation. There are two basic approaches.

The first approach is to normalize, satisfy an assumption, then perform a test. We'll take fmod(X, 2π) and fmod(A, 2π) to normalize. The assumption that we'll satisfy is that X is counter-clockwise from A (increasing angle), and we'll satisfy that by a conditional operation. Lastly, we'll perform the appropriate check:

def is_counter_clockwise(A, X):
    # Normalize.
    A = fmod(A, 2*PI)
    X = fmod(X, 2*PI)

    # Satisfy assumption.
    if X < A:
        X = X + 2*PI

    # Perform the check.
    return X - A <= PI

Our assumption guarantees that we are looking at X as if it is counter-clockwise from A. We then check to see how much counter-clockwise it is. If it's less than π (180 degrees), we confirm that it's counter-clockwise. If it's more than π, we know that it's actually shorter to arrive at X from A by moving clockwise.

The second approach is to reason directly in the modular system. This is more direct (having fewer operations) but more difficult to get correct, especially if multiple modular comparisons are being made simultaneously (such as testing whether two circular sectors of a single circle overlap). In our simple example, things remain straight-forward:

def is_counter_clockwise(A, X):
    # Be more direct.
    d = fmod(X - A, 2*PI)

    # Handle cases.  Obvious, right?
    return d <= PI

This more direct version can be derived directly from the first version, by understanding how and where mod is applied. However, this code definitely falls in the category of write once, read/understand never.

Avoidance

A space-transform might allow you to perform calculations and comparisons in a space with no wrap-around. For example, angles could be transformed into rectangular coordinates and operated on as such. There are some surprising tools that can help with this approach.

# Assume A is an angle.
def rotate(A, X):
    return fmod(A + X, 2*PI)

# Assume A is already represented as a complex number.
def rotate(A, X):
    # Make some complex numbers.
    x = cos(X) + sin(X)*1j

    # Multiplication is rotation.
    return A * x

Other tools are line-equations and dot-products, as demonstrated in Bounds-checking with a circular sector.

Sometimes, the problematic variable can be removed entirely. For example, here's a plot of a standard predator/prey model, with the two populations plotted against time:

If we remove the time variable from consideration, we work in phase-space, and the data looks like this:

This concept is very similar to converting polar coordinates to rectangular (as we did by using complex numbers to represent angles for the rotate function above), except that it is accomplished by omitting an unneeded variable.

Even some data-structures can be transformed. For example, traversing to left and right neighbors is trivially easy in a doubly-linked circular list, replacing the array in the dispersion example:

def disperse(node):
    node.value       = node.value       - 2
    node.left.value  = node.left.value  + 1
    node.right.value = node.right.value + 1

Avoidance can be an especially good strategy if you can adjust your representations to match, and use it everywhere. Even with avoidance, though, there are some things to be wary of. For example, representing an angle as a complex number may lead to the vector no longer being normalized (length equal to 1) after several operations have been applied. Renormalizing, while possible, is extra work that may not be worth the effort of avoiding some simple fmods. It depends on your application.