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;
}
remsum >= 0
\$\endgroup\$avg
andremsum
can unambiguously describe the avg in case of very bigN
\$\endgroup\$