Friday, February 8, 2008

Bouncing arithmetic

A common visualization of modular arithmetic consists of considering a variable x that monotonically increases mod n: when x is about to reach n, it wraps around to the starting value 0. For instance, the values of x mod 5 are:

0,1,2,3,4,0,1,2,3,4,0,1,2,3,4...

What about a variation where x does not wrap around to 0 but instead it bounces and begin decreasing towards 0?

0,1,2,3,4,3,2,1,0,1,2,3,4...

The period of this sequence is 2(n−1). In order to model this "bouncing arithmetic", we need to distinguish between increasing values and decreasing values; we do so by subscripting a + or − symbol, respectively:

0+,1+,2+,3+,4+,3,2,1.

Note that 0+ = 0 and (n−1)+ = (n−1). It is entirely trivial to lay out the foundations of bouncing arithmetic by mapping them to a suitable representation in modular arithmetic:

(a = b bounce n) := (a = b mod 2(n-1)),
a+ := a bounce n,
a := −a bounce n.

The last two statements introduce the subscripting +− notation. It is easy to verify that these definitions are accurate: for instance, 3 bounce 5 is (the equivalence class of) −3 bounce 5, which is −3 = 5 mod 8, just as it should be (3 goes right after 4). Having learned the nice equivalence between −a and a, we can dispense with the subscripting notation altogether and simply use +a and −a.

No comments:

Post a Comment