Calculate average of a huge long array

Question

I'm trying to calculate the average of many (more than 200) long (primitive type) values stored in an array. Usually you add all the numbers and divide it by the number of the values. But this is not possible in this case since there is no primitive datatype in Java capable of holding such a large number, isn't it? Will java.math.BigInteger help here?

Answer 1

Yes it will help you. An BigInteger can be as big as you want. Till there is not enough RAM.

With BigInteger bigInt = BigInteger.valueOf(long); you can convert the Long to an BigInteger.

And an BigInteger is immutable. So if you divide it like this bigInt = bigInt.divide(BigInteger.valueOf(200)); You have to reassign it.

A more precise option would be the method BigInteger.divideAndRemainder().

Answer 2

Kai has a very good answer, but I'll just throw out there that if you know the exact number of values you are trying to average (and you do, since you said it was an array), then you can divide each value by N before adding them all up. Then you would never exceed the limit of long.

Example: the limit of long is roughly 9.22e18, so let's do an average near that limit:

    long[] arr = {Math.round(5e18), Math.round(9e18)};
    double avg = 0.0d;
    int size = arr.length;
    for (int i = 0; i < size; i++) {
        long l = arr[i];
        double tmp = l/(double)size;
        avg += tmp;
    }

(The Math.round() calls are needed since exponential notation numbers are doubles in Java.)

Answer 3

If you know that the sum of all the long values in your array/list will never exceed the Long.MAX_VALUE value, you can use the following to calculate the average:

// For long type array
long[] array = ...;
double average = LongStream.of(array).average().getAsDouble();

// For long type list
List<Long> list = ...;
double average = list.stream().mapToLong(n -> n).average().getAsDouble();

But if you're unsure about the sum of your list, and that it can even exceed the maximum limit that long primitive provides, then use the following method to calculate the average:

// For long type array
long[] array = ...;
BigInteger sum = LongStream.of(array).mapToObj(BigInteger::valueOf).reduce((x, y) -> x.add(y)).get();
BigDecimal average = new BigDecimal(sum).divide(BigDecimal.valueOf(array.length));

// For long type list
List<Long> list = ...;
BigInteger sum = list.stream().map(BigInteger::valueOf).reduce((x, y) -> x.add(y)).get();
BigDecimal average = new BigDecimal(sum).divide(BigDecimal.valueOf(list.size()));

This technique works from Java 8 and following imports are required:

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.stream.LongStream;

Answer 4

• An average of a long is unlikely to be a long, so you need to decide for a type to keep your result. BigDecimal (not a BigInteger though) could be a good choice. You will probably need to define the accuracy of your result as well.

• Use a smarter algorithm to compute averages on massive collections. I do not have a definitive choice for you, but you could try something like this:

  1. initialise the value for your result as BigDecimal zero;
  2. compute a sum of next M elements and divide it by N where N is the total number of elements and M<N. The choice of M depends on the scale of your values and the accuracy your want to achive -- the larger the better, but think of your original problem;
  3. add this value to the result and go back to step 2 until all elements are used up