MathArrays.distance1(int[], int[]) returns negative distances for in-contract input

[ser10us]

MathArrays.distance1(int[], int[]) is documented to return "the L₁ distance between the two points", but its body performs three separate unchecked int operations, so it can return a negative value — and does so for a one-element array of two in-range ints.

Affected: org.hipparchus:hipparchus-core:4.0.3 (current release) and earlier. org.hipparchus.util.MathArrays.

The defect

public static int distance1(int[] p1, int[] p2)
    throws MathIllegalArgumentException {
    checkEqualLength(p1, p2);
    int sum = 0;
    for (int i = 0; i < p1.length; i++) {
        sum += FastMath.abs(p1[i] - p2[I]);
    }
    return sum;
}

There are three independent int hazards in that loop:

1. p1[i] - p2[i] can overflow — the difference of two ints is not an int in general.
2. FastMath.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE, which is negative. So when the subtraction lands exactly on MIN_VALUE, abs propagates a negative term rather than correcting it.
3. sum += can overflow independently of both, for coordinate values that are individually unremarkable.

Only the third requires anything unusual of the input; the first two fire at a single element.

Observed behaviour

[1] minimal case: ONE dimension, two in-range ints

{2147483647} vs {-1}    got=-2147483648   true=2147483648    NEGATIVE DISTANCE
{-2147483648} vs {1}    got=2147483647    true=2147483649    SILENTLY WRONG

[2] ordinary coordinate magnitudes (1e9), few dimensions

3 coords of 1e9 vs zeros    got=-1294967296   true=3000000000   NEGATIVE DISTANCE
4 coords of 1e9 vs zeros    got=-294967296    true=4000000000   NEGATIVE DISTANCE
10 coords of 1e9 vs zeros   got=1410065408    true=10000000000  SILENTLY WRONG

[3] small coordinate values, long vector (accumulator overflow)

n=100000, coords 1000 vs zeros    got=100000000     true=100000000    ok
n=2200000, coords 1000 vs zeros   got=-2094967296   true=2200000000   NEGATIVE DISTANCE

[4] control: ordinary inputs are exact

{1,2,3} vs {4,5,6}              got=9             true=9              ok
n=100000, coords 10 vs zeros    got=1000000       true=1000000        ok

Why this is a defect rather than an int-domain limitation

Non-negativity is a defining property of a distance: d(x, y) ≥ 0 for all x, y. The method's own javadoc promises "the L₁ distance", and a caller has no way to distinguish a wrong answer from a right one — the return type gives no room for an error value, and nothing is thrown.

The inputs are also unremarkable. The method's only documented precondition is that the two arrays have equal length (checkEqualLength), and every input above satisfies it. 1e9 is an ordinary int magnitude — timestamps, identifiers, fixed-point quantities — and case [1] needs only Integer.MAX_VALUE and -1 in a single-element array. Block [4] confirms the method is exact for ordinary inputs, so this is not "int arrays have limited range": it is that some in-range inputs produce a silently wrong, sometimes negative, answer.

Case [3] is worth separate note because it needs nothing large at all: 2.2 million coordinates of value 1000 is an ordinary feature vector, and the accumulator wraps.

Suggested fix

Compute in long — the difference of two ints and its absolute value are both exactly representable as a long, so no intermediate can overflow — and then narrow with a check:

public static int distance1(int[] p1, int[] p2)
    throws MathIllegalArgumentException {
    checkEqualLength(p1, p2);
    long sum = 0;
    for (int i = 0; i < p1.length; i++) {
        sum += Math.abs((long) p1[i] - (long) p2[i]);
    }
    return Math.toIntExact(sum);   // or throw MathIllegalArgumentException
}

Math.toIntExact preserves the existing signature and turns a silent wrong answer into a thrown exception. If a widening is preferable, a long-returning overload alongside the existing method would let callers opt in without breaking source compatibility.

The double[] overload immediately above is unaffected, since it accumulates in double.

Note

The same code is present in the retired commons-math3 3.6.1 (org.apache.commons.math3.util.MathArrays). Reporting it here since Hipparchus is the maintained descendant.

import org.hipparchus.util.MathArrays;
import java.math.BigInteger;
import java.util.Arrays;

/**
 * Reproduction against org.hipparchus:hipparchus-core:4.0.3 from Maven Central.
 *
 * Every array below is a legal int[]; the only documented precondition on
 * distance1(int[], int[]) is that the two lengths are equal.
 */
public class ReproD1 {

    static void t(String label, int[] a, int[] b) {
        BigInteger truth = BigInteger.ZERO;
        for (int i = 0; i < a.length; i++) {
            truth = truth.add(BigInteger.valueOf(Math.abs((long) a[i] - (long) b[i])));
        }
        int got = MathArrays.distance1(a, b);
        String verdict = BigInteger.valueOf(got).equals(truth) ? "ok"
                       : (got < 0 ? "*** NEGATIVE DISTANCE ***" : "*** SILENTLY WRONG ***");
        System.out.printf("  %-38s got=%-13d true=%-14s %s%n", label, got, truth, verdict);
    }

    static int[] filled(int n, int v) { int[] a = new int[n]; Arrays.fill(a, v); return a; }

    public static void main(String[] args) {
        System.out.println("[1] minimal case: ONE dimension, two in-range ints");
        t("{2147483647} vs {-1}", new int[]{Integer.MAX_VALUE}, new int[]{-1});
        t("{-2147483648} vs {1}", new int[]{Integer.MIN_VALUE}, new int[]{1});

        System.out.println("\n[2] ordinary coordinate magnitudes (1e9), few dimensions");
        t("3 coords of 1e9 vs zeros", filled(3, 1_000_000_000), new int[3]);
        t("4 coords of 1e9 vs zeros", filled(4, 1_000_000_000), new int[4]);
        t("10 coords of 1e9 vs zeros", filled(10, 1_000_000_000), new int[10]);

        System.out.println("\n[3] small coordinate values, long vector (accumulator overflow)");
        t("n=100000, coords 1000 vs zeros", filled(100_000, 1000), new int[100_000]);
        t("n=2200000, coords 1000 vs zeros", filled(2_200_000, 1000), new int[2_200_000]);

        System.out.println("\n[4] control: ordinary inputs are exact");
        t("{1,2,3} vs {4,5,6}", new int[]{1,2,3}, new int[]{4,5,6});
        t("n=100000, coords 10 vs zeros", filled(100_000, 10), new int[100_000]);
    }
}