Mean method implementation

[vkhodygo]

This discussion is a collection of notes regarding different algorithms of compensated summation and corresponding functions that calculate mean values.
The naive approach that is to add all elements of the input array together (we assume that one of the compensated summation algorithms is employed here ) and divide them by their total number. This is the fastest way to do so, however, it might lead to a potential overflow. Whereas it is highly unlikely for someone to have such ginormous outputs, it is not completely impossible.

The very first solution is to scale the data in advance. This:

1. Degrades performance even more due to creation of a temporary array and the scaling procedure itself¹;
2. Potentially leads to loss of precision¹, however, current tests can't reproduce this issue.

Another option is to sort input values by their magnitudes using . One should keep in mind this procedure is even more resource costly than the one described above. Regardless of that, if data contains both positive and negative values, sorting it should help with the overflow issue². Nevertheless, any data of the same sign still suffers from that. Still, this reduces error accumulation in both cases³.

Finally, it is possible to combine both scaling and sorting, but that require further investigation.

The resulting chain of execution should be similar to the following code snipper:

    static double auxMean(double[] values){
        double retVal;
        retVal = meanFast(values); // might return Inf
        if (Double.isInfinite(retVal)) {
            retVal = meanScaled(values); // scale first
            if (Double.isInfinite(retVal)) {
                retVal = meanSorted(values); // sort
                if (Double.isInfinite(retVal)) {
                    retVal = meanSortedScaled(values); // scale & sort
                }
            }
        }
        return retVal;
    

The best solution at the moment to stick to the conventional KBK summation scheme and deal with potential ill-conditioned data later.

Footnotes

1. No exact estimates. ↩ ↩²

2. Find references. ↩

3. Find references. ↩