计算所有值之和超过双精度限制的平均值的好方法是什么?

你可以 calculate the mean iteratively . 此算法简单、快速,您只需处理一次每个值,并且变量永远不会大于集合中的最大值,因此不会出现溢出。

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

圈内 avg 始终是迄今为止处理的所有值的平均值。换句话说,如果所有值都是有限的,就不应该出现溢出。

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

• 你事先知道值的数目吗?

如果没有,那你就别无选择,只能求和,数,除,求平均数。如果 Double 没有足够的精度来处理这个,那么运气不好,你就不能用 双重的 ,您需要找到一个可以处理它的数据类型。

另一方面,如果你 做 事先知道值的数目,你可以看看你真正在做什么,然后改变 怎样 你做到了,但要保持整体结果。

存储在某些集合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做上面的练习(注意后面的两个零),那么你会得到上面的结果。

换言之,如果无法将值的数目拆分为大小相等的集合,则最后一个集合将被计算为与前面所有集合具有相同数目的值,但对于所有缺少的值,将用零填充。

所以, 你需要同样大小的套装 . 如果原始输入集由质数个值组成,那就太倒霉了。

不过,我担心的是精确度的下降。我不太确定 双重的 在这种情况下,如果一开始它不能保存所有值的总和,那么它将提供足够高的精度。

imho,解决问题最有力的方法是

1. 整理你的布景
2. 分成一组元素,这些元素的总和不会溢出-因为它们是排序的,所以这是快速而简单的
3. 在每组中求和-然后除以组的大小
4. 组和的和(可能递归调用相同的算法)的和-注意如果组的大小不一样,就必须按它们的大小加权

这种方法的一个优点是,如果有大量的元素要求和,并且有大量的处理器/机器要用来计算,那么它可以很好地扩展

除了使用已经建议的更好的方法之外,您还可以使用 BigDecimal 做你的计算。(记住它是不可变的)

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

假设一个double有一个范围~=+/-10^308,并且你正在求10^9的值的和,你的问题中建议的表观范围是10^299的顺序值。

这似乎有点,嗯,不太可能…

如果你的价值观真的 是 那么大,那么对于一个普通的双精度,你只有17个有效的小数位数,所以在你考虑取平均值之前,你将扔掉大约280个数字的信息。

我也会注意到(因为没有人知道)对于任何一组数字 X :

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

对于任意常数 c .

在这个特殊的问题中,设置 c = min(X) 可以 大大降低了求和过程中溢出的风险。

我可以谦虚地说问题陈述不完整吗…?

将所有值除以设置的大小,然后求和

一个双精度可以被2的幂除而不损失精度。所以如果你唯一的问题是求和的绝对大小,你可以在求和之前预先缩放你的数字。但有了这样大的数据集,仍然有可能遇到这样的情况:将小数字添加到大数字中,而小数字最终将大部分(或完全)被忽略。

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

所以,根据你的数据集和你能承受的精度数字,你可能需要做其他的事情。将数据分解成集合会有帮助,但保持精度的更好方法可能是确定一个粗略的平均值(您可能已经知道这个数字)。然后在求和之前,从粗平均值中减去每个值。这样你就把距离和平均值相加,所以你的总和永远不会太大。

然后取平均增量,把它加到粗和中,得到正确的平均值。跟踪min delta和max delta也会告诉您在求和过程中丢失了多少精度。如果你有很多时间并且需要一个非常精确的结果,你可以迭代。

您可以取不超过限制的等号子集的平均值。

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

其他选项(失去精度)是分组求和,而不是一次全部求和,或者在求和之前进行除法。

所以我不会重复这么多,让我声明,我假设数字列表是正态分布的,在溢出之前,你可以对许多数字求和。这种技术仍然适用于非正常发行版,但有些东西不能满足我下面描述的期望。

——

总结一个子系列,记录你吃了多少,直到你接近溢出,然后取平均值。这将给你一个平均0,并计数n0。重复一遍,直到你把清单排完。现在你应该有很多人工智能了,尼。

每一个ai和ni应该是相对接近的,除了列表的最后一个部分。你可以通过在列表末尾咬一口来缓解这种情况。

您可以通过选择子集中的任何ni(称为np)并将该子集中的所有ni除以该值来组合这些ai、ni的任何子集。要合并的子集的最大大小是n的大致恒定值。

ni/np应接近1。现在求和ni/np*ai并乘以np/(和ni),跟踪求和ni。这给你一个新的ni,ai组合,如果你需要重复这个过程。

如果需要重复(即ai、n i对的数量比典型ni大得多),请尝试通过将一个n级的所有平均值组合在一起,然后在下一个n级组合,以保持相对n大小不变,依此类推。

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

然后,假设双精度表示为“值加指数”,其中指数是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 summation 以提高精度。kahan求和避免了非常大和非常小的数字求和时精度的损失。

我张贴 an answer 到 a question 从这个问题衍生出来,后来意识到我的答案更适合这个问题而不是那个问题。我在下面复制了它。但我注意到,我的回答类似于 Bozho's 和 Anon _^. 's .

由于另一个问题被标记为语言不可知,我选择了c作为我包含的代码示例。它的相对易用性和易于遵循的语法,以及它包含的一些促进这个例程的特性(bcl中的divrem函数和对迭代器函数的支持),以及我自己对它的熟悉,使它成为解决这个问题的一个很好的选择。因为这里的OP对Java解决方案感兴趣,但我不是Java流利,足以有效地编写它,如果有人可以将此代码的翻译添加到Java,可能会很好。

这里有些数学解很好。这里有一个简单的技术解决方案。

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

1. 使用高精度浮点库。一个平均需要10亿个数字的人可能有足够的资源来购买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;
    }
}

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();
    }
}

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

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

考虑一下:

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;
}

实际上,这很好地简化为(马丁内斯已经提供了):

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

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

查看该部分 cummulative moving 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计算而稍微降低性能,但它保证了运行时的稳定性。

(n) _一 +n _二 +…+n _K /k=(n) _一 +n _二 /k+(n) _三 +n _四 )+(n) _K-1 +n _K )/如果k是偶数

(n) _一 +n _二 +…+n _K /k= n _一 /k+(n) _二 +n _三 )+(n) _小精灵 +n _K )/如果k是奇数

为什么这么多复杂的长答案。这是目前为止最简单的求平均值的方法,不需要知道有多少元素或大小等。

长整数i=0; 双平均值=0; while(仍有元素) { 平均值=平均值*(i/i+1)+x[i]/(i+1); I++; } 平均收益率;