平均功能无溢出异常 [英] Average function without overflow exception

问题描述

.NET Framework 3.5.
我正在尝试计算一些相当大的数字的平均值.
例如:

.NET Framework 3.5.
I'm trying to calculate the average of some pretty large numbers.
For instance:

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var items = new long[]
                        {
                            long.MaxValue - 100, 
                            long.MaxValue - 200, 
                            long.MaxValue - 300
                        };
        try
        {
            var avg = items.Average();
            Console.WriteLine(avg);
        }
        catch (OverflowException ex)
        {
            Console.WriteLine("can't calculate that!");
        }
        Console.ReadLine();
    }
}

很明显，数学结果是9223372036854754775607(long.MaxValue - 200)，但是我在那里遇到了一个异常.这是因为.NET Reflector检查的(在我的机器上)Average扩展方法的实现是:

Obviously, the mathematical result is 9223372036854775607 (long.MaxValue - 200), but I get an exception there. This is because the implementation (on my machine) to the Average extension method, as inspected by .NET Reflector is:

public static double Average(this IEnumerable<long> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    long num = 0L;
    long num2 = 0L;
    foreach (long num3 in source)
    {
        num += num3;
        num2 += 1L;
    }
    if (num2 <= 0L)
    {
        throw Error.NoElements();
    }
    return (((double) num) / ((double) num2));
}

我知道我可以使用BigInt库(是的，我知道它是已包含在.NET Framework 4.0中，但我只能绑定到3.5).

I know I can use a BigInt library (yes, I know that it is included in .NET Framework 4.0, but I'm tied to 3.5).

但是我仍然想知道是否有一个非常简单的实现，无需外部库就可以计算整数的平均值.您碰巧知道这样的实现吗?

But I still wonder if there's a pretty straight forward implementation of calculating the average of integers without an external library. Do you happen to know about such implementation?

谢谢！

更新:

前面的三个大整数示例仅是说明溢出问题的示例.问题是要计算任何个数字集的平均值，这些总数之和可能会超过类型的最大值.对不起，这种混乱.我还更改了问题的标题，以免造成其他混乱.

The previous example, of three large integers, was just an example to illustrate the overflow issue. The question is about calculating an average of any set of numbers which might sum to a large number that exceeds the type's max value. Sorry about this confusion. I also changed the question's title to avoid additional confusion.

谢谢！！

推荐答案

此答案用于建议分别存储商和余数(模数).该解决方案的空间效率较低，代码复杂度更高.

为了准确计算平均值，您必须跟踪总数.除非您愿意牺牲准确性，否则无法解决此问题.您可以尝试以奇特的方式存储总数，但是如果算法正确，最终您必须对其进行跟踪.

In order to accurately compute the average, you must keep track of the total. There is no way around this, unless you're willing to sacrifice accuracy. You can try to store the total in fancy ways, but ultimately you must be tracking it if the algorithm is correct.

对于单遍算法，这很容易证明.假设在处理完这些项目后算法的整个状态下，您无法重构所有前面所有项目的总和.但是，等等，我们可以模拟算法，然后接收一系列0项，直到完成序列.然后，我们可以将结果乘以计数并得到总数.矛盾.因此，单遍算法必须在某种意义上跟踪总数.

For single-pass algorithms, this is easy to prove. Suppose you can't reconstruct the total of all preceding items, given the algorithm's entire state after processing those items. But wait, we can simulate the algorithm then receiving a series of 0 items until we finish off the sequence. Then we can multiply the result by the count and get the total. Contradiction. Therefore a single-pass algorithm must be tracking the total in some sense.

因此，最简单的正确算法只是将各项相加并除以计数.您要做的就是选择一个具有足够空间来存储总数的整数类型.使用BigInteger不会有任何问题，因此我建议使用.

Therefore the simplest correct algorithm will just sum up the items and divide by the count. All you have to do is pick an integer type with enough space to store the total. Using a BigInteger guarantees no issues, so I suggest using that.

var total = BigInteger.Zero
var count = 0
for i in values
    count += 1
    total += i
return total / (double)count //warning: possible loss of accuracy, maybe return a Rational instead?

这篇关于平均功能无溢出异常的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！