How to Handle Negative Numbers in Modular Arithmetic for Correct Array Indexing?

Modular Arithmetic and Negative Indices

Standard modulo operations (%) on negative integers can produce unexpected results when used for array indexing. The remainder can be negative, leading to invalid index values. To ensure correct positive array indices, we need a modified modulo function.

A common solution is to use this formula:

<code>GetArrayIndex(i, arrayLength) = (i % arrayLength + arrayLength) % arrayLength</code>

This guarantees a positive index within the range [0, arrayLength - 1], irrespective of the input i's sign.

Custom Modulo Function

For cleaner code, a custom mod function is helpful:

public static int mod(int x, int m) {
    return (x % m + m) % m;
}

This function handles negative remainders by adding m to ensure a positive result.

Optimized Modulo Function

For improved efficiency (fewer modulo operations), consider this alternative:

public static int mod(int x, int m) {
    int r = x % m;
    return r < 0 ? r + m : r;
}

This version directly checks if the remainder r is negative, adding m only when necessary.

Examples

Using either custom mod function, we get the expected array index behavior:

GetArrayIndex(4, 3) == 1 GetArrayIndex(3, 3) == 0 GetArrayIndex(2, 3) == 2 GetArrayIndex(1, 3) == 1 GetArrayIndex(0, 3) == 0 GetArrayIndex(-1, 3) == 2 GetArrayIndex(-2, 3) == 1 GetArrayIndex(-3, 3) == 0 GetArrayIndex(-4, 3) == 2

The above is the detailed content of How to Handle Negative Numbers in Modular Arithmetic for Correct Array Indexing?. For more information, please follow other related articles on the PHP Chinese website!