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.
Most languages have
mod operators, sometimes
% for integers and
fmod for floats.
Passing all calculations through
mod will help maintain
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
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
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
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
once, read/understand never.
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
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
This concept is very similar to converting polar coordinates to
rectangular (as we did by using complex numbers to represent angles
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.
The author does not allow comments to this entry