Non-overflowing avg calculation with integer arithmetic

Question

I have multiple long values and I want to calculate their average value using integer arithmetic, without precision loss and using java rounding rules for division, i.e. when N is 10 and sum is +/- 29, then 29/10 == 2 and -29/10 == -2, not -3.

The code should handle situations when the sum of all elements overflows the type.

The resulting type should be the same as the elements' type, not double.

It is ok to return bad result if N exceeds the maximum supported value for the element type

The code should not use a bigger type to store the sum, because there can be no bigger type, when elements are of type long in java or intmax_t in c++. Using double can lead to precision loss; arbitrary precision integers like BigInteger are too slow for this task.

I found a solution that best suits me: How can I compute the average of a large array of integers without running into overflow?. In short: they divide each element before summing and therefore avoid the overflow.

As the first replier said, I adapted it for negative values. There was a divisor overflow check: y >= N - b, I replaced it with the type overflow check: when the sign of the remainder sum changes, I increment or decrement the current avg. For some reason, it works even when the sign changes not because of an overflow.

There's also Precise and safe calculation method for the average of large integer arrays, but I found it later and I didn't have time to check. On first glance, they don't check the cumulated_remainder overflow in case of many elements.

I chose to use 8-bit integers for the test implementation, because they're easier to count mentally. Also, it is possible to check all value combinations in short arrays in reasonable time.

In some places I use the addition assignment operator += instead of assignment to avoid unnecessary casts.

avg_slow() is using BigInteger to produce the expected results for comparison.

static byte avg(final byte[] vals) {
    final int n = vals.length;
    byte avg = 0, remsum = 0, remrem = 0;
    for (int i = 0; i < n; i++) {
        final byte val = vals[i];
        avg += val / n;
        final byte oldremsum = remsum;
        byte rem = 0;
        rem += val % n;
        remsum += rem;

        if (oldremsum < 0) {
            if (remsum >= 0 && rem < 0) {
                avg--;
                remsum += n;
            }
        } else if (oldremsum > 0 && remsum < 0 && rem > 0) {
            avg++;
            remsum -= n;
        }
    }
    avg += remsum / n;
    remrem += remsum % n;
    if (avg < 0 && remrem > 0) {
        avg++;
    } else if (avg > 0 && remrem < 0) {
        avg--;
    }
    return avg;
}

static void calcAndCompare(final byte[] vals) {
    final byte avgex = avg_slow(vals);
    final byte avgact = avg(vals);
    if (avgact != avgex) {
        System.out.println("ex:" + avgex + " act:" + avgact + " " + Arrays.toString(vals));
        System.exit(1);
    }
}

static void test129() {
    final byte[] vals = new byte[129];
    Arrays.fill(vals, (byte) -128);
    calcAndCompare(vals);
}

static void test100() {
    final byte[] vals = new byte[120];
    vals[0] = -1;
    vals[1] = 100;
    calcAndCompare(vals);
}

static void testMaxN() {
    byte b = 1;
    while ((b <<= 1) > 0);
    b--;
    final byte[] vals = new byte[(int)(b > Short.MAX_VALUE ? Short.MAX_VALUE : b)];

    Arrays.fill(vals, b);
    calcAndCompare(vals);

    b++;

    Arrays.fill(vals, b);
    calcAndCompare(vals);
}

static void test67() {

    byte b = 1;
    while ((b <<= 1) > 0);
    b--;

    final byte[] vals = new byte[67];

    Arrays.fill(vals, (byte) -110);
    calcAndCompare(vals);

    Arrays.fill(vals, (byte) 110);
    calcAndCompare(vals);

    double d = b;
    d++;
    for (int i = 0; i < vals.length; i++) {
        vals[i] = (byte) ((Math.random() * 2 * d) - d);
    }
    calcAndCompare(vals);
}

static void testAllCombinations(final int depth, final byte... vals) {
    if (depth == vals.length) {
        calcAndCompare(vals);
        return;
    }
    for (byte b1 = Byte.MIN_VALUE;; b1++) {
        vals[depth] = b1;
        testAllCombinations(depth + 1, vals);
        if (b1 == Byte.MAX_VALUE) {
            break;
        }
    }
}

public static void main(final String[] args) {

    test100();
    testMaxN();
    test129();

    test67();

    testAllCombinations(0, new byte[2]);
    testAllCombinations(0, new byte[3]);
}

static byte avg_slow(final byte[] vals) {
    if (false) {
        return avg(vals);
    }
    final int n = vals.length;
    BigInteger sum = BigInteger.ZERO;
    for (int i = 0; i < n; i++) {
        final byte val = vals[i];
        sum = sum.add(BigInteger.valueOf(val));
    }
    byte res = 0;
    res += sum.divide(BigInteger.valueOf(n)).longValue();
    return res;
}

Answer 1

This is Java, not C. You don't have to declare all the variables at the start of the method. There are 20 lines between the declaration of remrem and the first use. Keeping variables to the smallest scope possible aids readability.

Also, it's not obligatory to declare variables to be equal to the "default" value. Observe:

    byte ... remrem = 0;
    ...
    remrem += remsum % n;

and

        byte rem = 0;
        rem += val % n;

Both of those could be simplified to a simple initialisation to the desired value and made final.

---

Arguably an extension of minimising scope is avoiding unnecessary variables.

    for (int i = 0; i < n; i++) {
        final byte val = vals[i];

could perfectly well be

 for (byte val : vals) {

since i is not used elsewhere.

---

        if (oldremsum < 0) {
            if (remsum >= 0 && rem < 0) {
                avg--;
                remsum += n;
            }
        } else if (oldremsum > 0 && remsum < 0 && rem > 0) {
            avg++;
            remsum -= n;
        }

I understand (for the most part) why this is written as it is, but the asymmetry slowed me down slightly. (The bit I still don't understand is why one half uses >= and the other half uses <). Would it be preferable to make the test symmetric using basic properties of twos-complement numbers?

    if ((oldremsum ^ remsum) < 0 && (oldremsum ^ rem) >= 0) {
        // Sign of remsum has changed when adding a number of the same sign,
        // so there has been overflow.
        if (rem < 0) {
            avg--;
            remsum += n;
        }
        else {
            avg++;
            remsum -= n;
        }
    }