## Working with wrap-around

Sometimes we need to work with numbers that wrap-around, such as angles or indexes into a circular array. There are some tricks for dealing with these cases.

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] + 1Using mod we can remove all of the special cases:

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
`fmod`

s. It depends on your application.

### Trackbacks

The author does not allow comments to this entry

## Comments

Display comments as Linear | Threaded