Invert Arnold's Cat map - negative array indexes

Question

I'm trying to implement Arnold's Cat map for N*N images using the following formula

            for (int i = 0; i < N; i++) {  
                for (int j = 0; j < N; j++) {  
                  desMatrix[(i + j) % N][(i + 2 * j) % N] = srcMatrix[i][j];  
                }  
            }

To invert the process I do:

            for (int i = 0; i < N; i++) {  
                for (int j = 0; j < N; j++) {  
                  srcMatrix[(j-i) % N][(2*i-j) % N] = destMatrix[i][j];  
                }  
            }

Is the implementation correct?

It seems to me that for certain values of j and i I might get negative indexes from (j-i) and (2*i-j); how should I handle those cases, since matrix indexes are only positive?

Answer 1

In general, when a modulo (%) operation needs to work on negative indexes, you can simply add the modulo argument as many times as it's needed. Since

x % N  == ( x + a*N ) % N

for all natural a's, and in this case you have i and j constrained in [0, N), then you can write (N + i - j) and ensure that even if i is 0 and j is N-1 (or even N for that matter), the result will always be non-negative. By the same token, (2*N + i - 2*j) or equivalently (i + 2*(N-j)) is always non-negative.

In this case, though, this is not necessary. To invert your map, you would repeat the forward step reversing the assignments. Since the matrix has unary determinant and is area-preserving, you're assured that you'll get all your points eventually (i.e. covering M(i+1) will yield a covering of M(i)).

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        newMatrix[i][j] = desMatrix[(i + j) % N][(i + 2 * j) % N];
    }
}

At this point newMatrix and srcMatrix ought to be identical.

^{(Actually, you're already running the reverse transformation as your forward one. The one I set up to reverse yours is the one commonly used form for the forward transformation).}