计算所有值之和超过双精度限制的平均值的好解决方案是什么？

您可以取不超过限制的相同大小的数字子集的平均值的平均值。

将所有值除以设定的大小，然后求和

选项 1 是使用任意精度的库，这样您就没有上限。

其他选项（失去精度）是分组求和而不是一次全部求和，或者在求和之前除法。

除了使用已经建议的更好的方法外，您还可以使用 BigDecimal 进行计算。（请记住，它是不可变的）

恕我直言，解决问题的最可靠方法是

1. 对套装进行排序
2. 分成元素组，其总和不会溢出 - 因为它们是排序的，所以这是快速和简单的
3. 做每个组的总和 - 然后除以组大小
4. 做组的总和（可能递归调用相同的算法） - 请注意，如果组的大小不相等，则必须按其大小对它们进行加权

这种方法的一个好处是，如果你有大量的元素要求和，并且有大量的处理器/机器用来做数学运算，它就可以很好地扩展

双精度可以除以 2 的幂而不会损失精度。因此，如果您唯一的问题是总和的绝对大小，您可以在求和之前预先缩放您的数字。但是对于这种规模的数据集，您仍然有可能遇到将小数字添加到大数字中的情况，并且小数字最终将被大部分（或完全）忽略。

例如，当您将 2.2e-20 添加到 9.0e20 时，结果是 9.0e20，因为一旦调整了比例，以便将它们的数字相加，较小的数字为 0。双打只能容纳大约 17 位数字，您需要超过 40 位数字才能将这两个数字相加而不会丢失。

因此，根据您的数据集以及您可以承受的精度位数，您可能需要执行其他操作。将数据分解成几组会有所帮助，但保持精度的更好方法可能是确定粗略的平均值（您可能已经知道这个数字）。然后从粗略平均值中减去每个值，然后再求和。这样一来，你就等于与平均值的距离相加，所以你的总和永远不会变得非常大。

然后，您取平均值 delta，并将其添加到您的粗略总和中，以获得正确的平均值。跟踪最小和最大增量还将告诉您在求和过程中损失了多少精度。如果你有很多时间，需要一个非常准确的结果，你可以迭代。

我想问你的第一个问题是：

• 您事先知道值的数量吗？

如果没有，那么你别无选择，只能求和、计数、除以做平均值。如果精度不够高，无法处理这个问题，那么运气不好，你不能使用，你需要找到一个可以处理它的数据类型。DoubleDouble

另一方面，如果你事先知道值的数量，你可以看看你真正在做什么，并改变你做事的方式，但要保持整体结果。

存储在某个集合 A 中的 N 值的平均值如下：

A[0]   A[1]   A[2]   A[3]          A[N-1]   A[N]
---- + ---- + ---- + ---- + .... + ------ + ----
 N      N      N      N               N       N

要计算此结果的子集，您可以将计算拆分为大小相等的集合，因此您可以针对 3 值集执行此操作（假设值的数量可以被 3 整除，否则您需要不同的除数）

/ A[0]   A[1]   A[2] \   / A[3]   A[4]   A[5] \   //      A[N-1]   A[N] \
| ---- + ---- + ---- |   | ---- + ---- + ---- |   \\    + ------ + ---- |
\  3      3      3   /   \  3      3      3   /   //        3       3   /
 --------------------- +  --------------------  + \\      --------------
          N                        N                        N
         ---                      ---                      ---
          3                        3                        3

请注意，您需要大小相等的集合，否则与之前的所有集合相比，最后一个集合中的数字没有足够的值，将对最终结果产生更大的影响。

考虑数字 1-7 的顺序，如果选择集合大小为 3，则会得到以下结果：

/ 1   2   3 \   / 4   5   6 \   / 7 \ 
| - + - + - | + | - + - + - | + | - |
\ 3   3   3 /   \ 3   3   3 /   \ 3 /
 -----------     -----------     ---
      y               y           y

这给了：

     2   5   7/3
     - + - + ---
     y   y    y

如果所有集合的 y 都是 3，则得到以下结果：

     2   5   7/3
     - + - + ---
     3   3    3

这给了：

2*3   5*3    7
--- + --- + ---
 9     9     9

即：

6   15   7
- + -- + -
9    9   9

总计：

28
-- ~ 3,1111111111111111111111.........1111111.........
 9

1-7的平均值是4。显然这是行不通的。请注意，如果您使用数字 1、2、3、4、5、6、7、0、0（注意末尾的两个零）进行上述练习，那么您将得到上述结果。

换句话说，如果无法将值的数量拆分为大小相等的集合，则最后一个集合将被计数，就好像它具有与它之前的所有集合相同的值数，但它将用零填充所有缺失值。

因此，您需要相同大小的套装。如果您的原始输入集由质数个值组成，那就太幸运了。

不过，我在这里担心的是精度的损失。我不完全确定在这种情况下是否会为您提供足够好的精度，如果它最初无法容纳全部值的总和。Double

查看累积移动平均线部分

所以我就不重复太多了，让我声明一下，我假设数字列表是正态分布的，你可以在溢出之前对许多数字求和。该技术仍然适用于非正常发行版，但有些东西将无法满足我在下面描述的期望。

--

总结一个子系列，跟踪你吃了多少个数字，直到你接近溢出，然后取平均值。这将给你一个平均 a0，并计数 n0。重复上述步骤，直到用完列表。现在你应该有很多ai，ni。

每个 ai 和 ni 都应该相对接近，但列表的最后一口可能除外。您可以通过在列表末尾附近咬合不足来缓解这种情况。

你可以组合这些 ai， ni 的任何子集，方法是选择子集中的任何 ni（称之为 np）并将子集中的所有 ni 除以该值。要合并的子集的最大大小是 n 的大致恒定值。

ni/np 应接近 1。现在求和 ni/np * ai 并乘以 np/（sum ni），跟踪总和 ni。如果您需要重复该过程，这将为您提供新的 ni、ai 组合。

如果需要重复（即 ai、ni 对的数量远大于典型的 ni），请尝试保持相对 n 大小不变，方法是先将所有平均值合并在一个 n 水平上，然后在下一个水平上合并，依此类推。

对完整数据集的一小部分进行随机抽样通常会产生一个“足够好”的解决方案。显然，您必须根据系统要求自己做出此决定。样本量可能非常小，但仍然能获得相当好的答案。这可以通过计算越来越多的随机选择样本的平均值来自适应计算 - 平均值将在某个区间内收敛。

采样不仅解决了双重溢出问题，而且速度要快得多。不适用于所有问题，但肯定对许多问题有用。

我发布了一个问题的答案，后来意识到我的答案更适合这个问题而不是那个问题。我在下面复制了它。不过我注意到，我的回答类似于Bozho和Anon的组合_^。秒。

由于另一个问题被标记为与语言无关，因此我选择了 C# 作为我包含的代码示例。它相对易用性和易于遵循的语法，以及它包含的几个促进此例程的功能（BCL 中的 DivRem 函数，以及对迭代器函数的支持），以及我自己对它的熟悉程度，使它成为这个问题的不错选择。由于这里的 OP 对 Java 解决方案感兴趣，但我的 Java 不够流利，无法有效地编写它，如果有人可以将这段代码的翻译添加到 Java 中可能会很好。

---

这里的一些数学解决方案非常好。这是一个简单的技术解决方案。

使用较大的数据类型。这分为两种可能性：

1. 使用高精度浮点库。遇到需要平均 10 亿个数字的人可能有资源购买 128 位（或更长）的浮点库，或者有脑力来编写 128 位（或更长）的浮点库。

   我理解这里的缺点。它肯定比使用内部类型慢。如果值的数量增长得太高，您仍然可能会上溢/下溢。雅达雅达。

2. 如果您的值是整数或可以轻松缩放为整数，请将总和保留在整数列表中。溢出时，只需添加另一个整数即可。这实质上是第一个选项的简化实现。下面是 C# 中的一个简单（未经测试）示例

class BigMeanSet{
    List<uint> list = new List<uint>();

    public double GetAverage(IEnumerable<uint> values){
        list.Clear();
        list.Add(0);

        uint count = 0;

        foreach(uint value in values){
            Add(0, value);
            count++;
        }

        return DivideBy(count);
    }

    void Add(int listIndex, uint value){
        if((list[listIndex] += value) < value){ // then overflow has ocurred
            if(list.Count == listIndex + 1)
                list.Add(0);
            Add(listIndex + 1, 1);
        }
    }

    double DivideBy(uint count){
        const double shift = 4.0 * 1024 * 1024 * 1024;

        double rtn       = 0;
        long   remainder = 0;

        for(int i = list.Count - 1; i >= 0; i--){
            rtn *= shift;
            remainder <<= 32;
            rtn += Math.DivRem(remainder + list[i], count, out remainder);
        }

        rtn += remainder / (double)count;

        return rtn;
    }
}

就像我说的，这是未经测试的——我没有真正想要平均的十亿个值——所以我可能犯了一两个错误，尤其是在 DivideBy 函数中，但它应该演示了一般的想法。

这应该提供与双精度一样高的精度，并且应该适用于任意数量的 32 位元素，最多 2³² - 1。如果需要更多元素，则需要扩展变量，函数的复杂性也会增加，但我会把它留给读者作为练习。countDivideBy

就效率而言，它应该与这里的任何其他技术一样快或更快，因为它只需要遍历列表一次，只执行一个除法运算（嗯，一组），并且大部分工作都是用整数完成的。不过，我没有优化它，而且我很确定，如果有必要，它仍然可以做得稍微快一点。放弃递归函数调用和列表索引将是一个好的开始。再次，对读者进行练习。该代码旨在易于理解。

如果现在有比我更有动力的人想要验证代码的正确性，并解决可能存在的任何问题，请成为我的客人。

---

我现在已经测试了这段代码，并做了一些小的更正（构造函数调用中缺少一对括号，函数的最终除法中缺少不正确的除数）。List<uint>DivideBy

我首先通过 1000 组随机长度（范围在 1 到 1000 之间）填充随机整数（范围在 0 到 2³² - 1 之间）来测试它。对于这些集合，我还可以通过对它们运行规范平均值来轻松快速地验证准确性。

然后，我用 100^* 大系列进行了测试，随机长度在 10⁵ 和 10⁹ 之间。这些序列的下限和上限也是随机选择的，经过约束，使序列适合 32 位整数的范围。对于任何序列，结果都可以很容易地验证为 。(lowerbound + upperbound) / 2

_{^{*好吧，这是一个小小的谎言。在成功运行大约 20 或 30 次后，我中止了大批量测试。在我的机器上运行长度为 109 的系列只需不到一分半钟，因此半小时左右的测试程序足以满足我的口味。}}

对于那些感兴趣的人，我的测试代码如下：

static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
    for(uint i = lowerbound; i <= upperbound; i++)
        yield return i;
}

static void Test(){
    Console.BufferHeight = 1200;
    Random rnd = new Random();

    for(int i = 0; i < 1000; i++){
        uint[] numbers = new uint[rnd.Next(1, 1000)];
        for(int j = 0; j < numbers.Length; j++)
            numbers[j] = (uint)rnd.Next();

        double sum = 0;
        foreach(uint n in numbers)
            sum += n;

        double avg = sum / numbers.Length;
        double ans = new BigMeanSet().GetAverage(numbers);

        Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }

    for(int i = 0; i < 100; i++){
        uint length     = (uint)rnd.Next(100000, 1000000001);
        uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
        uint upperbound = lowerbound + length;

        double avg = ((double)lowerbound + upperbound) / 2;
        double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));

        Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }
}

请澄清这些值的潜在范围。

假设双精度值的范围是 ~= +/-10^308，并且您要对 10^9 个值求和，则您的问题中建议的表观范围是 10^299 量级的值。

这似乎有点，嗯，不太可能......

如果你的值真的那么大，那么使用普通的双精度，你只有 17 个有效的十进制数字可以使用，所以在你考虑平均这些值之前，你会丢弃大约 280 位的信息。

我还要指出（因为没有其他人有）对于任何一组数字：X

mean(X) = sum(X[i] - c)  +  c
          -------------
                N

对于任意常数。c

在这个特定问题中，设置可能会大大降低求和过程中溢出的风险。c = min(X)

我可以谦虚地建议问题陈述不完整吗......？

首先，让自己熟悉价值观的内在表示。维基百科应该是一个很好的起点。double

然后，考虑双精度表示为“值加指数”，其中指数是 2 的幂。最大双精度值的极限是指数的上限，而不是值的极限！因此，您可以将所有大的输入数字除以足够大的 2 的幂。对于所有足够大的数字来说，这应该是安全的。您可以将结果与因子重新相乘，以检查乘法是否丢失了精度。

在这里，我们使用一种算法

public static double sum(double[] numbers) { 
  double eachSum, tempSum;
  double factor = Math.pow(2.0,30); // about as large as 10^9
  for (double each: numbers) {
    double temp = each / factor;
    if (t * factor != each) {
      eachSum += each;
    else {
      tempSum += temp;
    }
  }
  return (tempSum / numbers.length) * factor + (eachSum / numbers.length);
}

不要担心额外的除法和乘法。FPU 将优化它们，因为它们是用 2 的幂完成的（为了进行比较，想象一下在十进制数末尾添加和删除数字）。

 

PS：另外，您可能希望使用Kahan求和来提高精度。Kahan 求和避免了在对非常大和非常小的数字求和时精度损失。

您可以迭代计算均值。这个算法简单、快速，你只需要处理每个值一次，而且变量永远不会大于集合中的最大值，所以你不会得到溢出。

double mean(double[] ary) {
  double avg = 0;
  int t = 1;
  for (double x : ary) {
    avg += (x - avg) / t;
    ++t;
  }
  return avg;
}

循环内部始终是到目前为止处理的所有值的平均值。换句话说，如果所有值都是有限的，则不应出现溢出。avg

考虑一下：

avg(n1)         : n1                               = a1
avg(n1, n2)     : ((1/2)*n1)+((1/2)*n2)            = ((1/2)*a1)+((1/2)*n2) = a2
avg(n1, n2, n3) : ((1/3)*n1)+((1/3)*n2)+((1/3)*n3) = ((2/3)*a2)+((1/3)*n3) = a3

因此，对于任意大小的任何一组双精度值，您都可以这样做（这是在 C# 中，但我很确定它可以很容易地翻译成 Java）：

static double GetAverage(IEnumerable<double> values) {
    int i = 0;
    double avg = 0.0;
    foreach (double value in values) {
        avg = (((double)i / (double)(i + 1)) * avg) + ((1.0 / (double)(i + 1)) * value);
        i++;
    }

    return avg;
}

实际上，这很好地简化为（已经由 martinus 提供）：

static double GetAverage(IEnumerable<double> values) {
    int i = 1;
    double avg = 0.0;
    foreach (double value in values) {
        avg += (value - avg) / (i++);
    }

    return avg;
}

我写了一个快速测试来尝试这个函数，以对抗更传统的方法，即对值求和并除以计数（）。对于我的输入，我编写了这个快速函数来返回尽可能多的随机正双精度值：GetAverage_old

static IEnumerable<double> GetRandomDoubles(long numValues, double maxValue, int seed) {
    Random r = new Random(seed);
    for (long i = 0L; i < numValues; i++)
        yield return r.NextDouble() * maxValue;

    yield break;
}

以下是一些测试试验的结果：

long N = 100L;
double max = double.MaxValue * 0.01;

IEnumerable<double> doubles = GetRandomDoubles(N, max, 0);
double oldWay = GetAverage_old(doubles); // 1.00535024998431E+306
double newWay = GetAverage(doubles); // 1.00535024998431E+306

doubles = GetRandomDoubles(N, max, 1);
oldWay = GetAverage_old(doubles); // 8.75142021696299E+305
newWay = GetAverage(doubles); // 8.75142021696299E+305

doubles = GetRandomDoubles(N, max, 2);
oldWay = GetAverage_old(doubles); // 8.70772312848651E+305
newWay = GetAverage(doubles); // 8.70772312848651E+305

好的，但是对于 10^9 个值呢？

long N = 1000000000;
double max = 100.0; // we start small, to verify accuracy

IEnumerable<double> doubles = GetRandomDoubles(N, max, 0);
double oldWay = GetAverage_old(doubles); // 49.9994879713857
double newWay = GetAverage(doubles); // 49.9994879713868 -- pretty close

max = double.MaxValue * 0.001; // now let's try something enormous

doubles = GetRandomDoubles(N, max, 0);
oldWay = GetAverage_old(doubles); // Infinity
newWay = GetAverage(doubles); // 8.98837362725198E+305 -- no overflow

当然，该解决方案的可接受程度将取决于您的精度要求。但值得考虑。

为什么有这么多复杂的长答案。这是迄今为止找到运行平均值的最简单方法，而无需知道有多少个元素或大小等。

long int i = 0;
double average = 0;
while(there are still elements)
{
   average = average * (i / i+1) + X[i] / (i+1);
   i++;
}
return average;

为了保持逻辑简单，并使性能不是最好的，但可以接受，我建议您将 BigDecimal 与原始类型一起使用。 这个概念非常简单，你使用原始类型将值相加，每当值下溢或溢出时，你就将计算值移动到 BigDecimal，然后重置它以进行下一次总和计算。您应该注意的另一件事是，当您构造 BigDecimal 时，您应该始终使用 String 而不是 double。

BigDecimal average(double[] values){
    BigDecimal totalSum = BigDecimal.ZERO;
    double tempSum = 0.00;
    for (double value : values){
        if (isOutOfRange(tempSum, value)) {
            totalSum = sum(totalSum, tempSum);
            tempSum = 0.00;
        }
        tempSum += value;
    }
    totalSum = sum(totalSum, tempSum);
    BigDecimal count = new BigDecimal(values.length);
    return totalSum.divide(count);
}

BigDecimal sum(BigDecimal val1, double val2){
    BigDecimal val = new BigDecimal(String.valueOf(val2));
    return val1.add(val);
}

boolean isOutOfRange(double sum, double value){
    // because sum + value > max will be error if both sum and value are positive
    // so I adapt the equation to be value > max - sum 
    if(sum >= 0.00 && value > Double.MAX - sum){
        return true;
    }

    // because sum + value < min will be error if both sum and value are negative
    // so I adapt the equation to be value < min - sum
    if(sum < 0.00 && value < Double.MIN - sum){
        return true;
    }
    return false;
}

从这个概念来看，每当结果是下溢或溢出时，我们都会将该值保留到更大的变量中，由于 BigDecimal 计算，此解决方案可能会稍微降低性能，但它保证了运行时的稳定性。

已经提到过两种方法：

int i = 1;
for ( double x : arr ){
    mean = mean + (x-mean)/n;
    ++n;
}

如果 （x-mean）/n 部分变得太小，则可以使用

int i = 1;
for (double x : arr){
    mean = mean*((i-1)/i) + x/i;
    ++i; 
}

首先计算 （i-1）/i 会接近零，因此 x/i 应该是您唯一关心的问题。