为什么不同的求和算法不匹配？

Question

假设我想得到从 M 到 N 的所有平方和。我用谷歌搜索了一下，发现了这个公式：

(1^2 + 2^2 + 3^2 + ... + N^2) = (N * (N + 1) * (2N + 1)) / 6

所以我写了这段代码：

static void Main(string[] args)
{
    const int from = 10;
    const int to = 50000;
    Console.WriteLine(SumSquares(from, to));
    Console.WriteLine(SumSquares2(from, to));
}

static long SumSquares(int m, int n)
{
    checked
    {
        long x = m - 1;
        long y = n;
        return (((y*(y + 1)*(2*y + 1)) - (x*(x + 1)*(2*x + 1)))/6);
    }
}

static long SumSquares2(int m, int n)
{
    long sum = 0;

    for (int i = m; i <= n; ++i)
    {
        sum += i * i;
    }
    return sum;
}

它在 40k 之前工作正常，但是当 N 变为 50k 时它失败了。 50k 的输出：

41667916674715
25948336371355
Press any key to continue . . .

我认为是溢出什么的，所以我添加了checked关键字并尝试将long更改为double，但我得到了相同的结果。怎么解释呢？如何在没有循环的情况下获得正确的结果？

Answer 1

很可能您遇到的是 integer overflow，因为 long 的范围有限。可能您已禁用整数溢出异常，因此不会抛出异常。如果我没记错的话，可以在 Visual Studio 的项目属性中禁用和启用整数溢出异常。

Answer 2

当您对结果使用 long 时，您仍在对运算符使用 int。我会将 M 和 N 定义为 long 甚至 BigInteger，结果也是如此。如果你不这样做，你可能仍在做 int 算术，即使你的结果是 long 类型。

我试过你的代码，得到了你得到的结果。但后来我将每个 int 都更改为 long 并让两个数字匹配，直到 N 为 1600000。

使用 BigInteger，我达到 160000000 并且仍然工作正常（m=10 和 n=160000000 的结果是 13653333461333333359999715，两种方式）。

要使用 BigInteger，您需要将对 System.Numerics dll 的引用添加到您的项目中，并且您需要在包含该库的代码顶部有一个语句。

using System.Numerics;

namespace ConsoleFiddle
{
  class Program
  {
    static void Main(string[] args)
    {
        BigInteger from = 10;
        BigInteger to = 160000000;
        Console.WriteLine(SumSquares(from, to));
        Console.WriteLine(SumSquares2(from, to));
        Console.ReadKey();
    }
    static BigInteger SumSquares(BigInteger m, BigInteger n)
    {
        checked
        {
            BigInteger x = m - 1;
            BigInteger y = n;
            return (((y * (y + 1) * (2 * y + 1)) - (x * (x + 1) * (2 * x + 1))) / 6);
        }
    }
    static BigInteger SumSquares2(BigInteger m, BigInteger n)
    {
      checked
      {
        BigInteger sum = 0;
        for (BigInteger i = m; i <= n; ++i)
        {
            sum += i * i;
        }
        return sum;
      }
    }

对于 4000000000000000000 (4 x 10^18) 的 M，以及 4000000000100000000 的 N。此代码仍然有效，并使用第一种方法 (16000000160400000004003333333383333333350000000) 立即给出结果。使用第二种方法需要一点时间（1 亿次循环迭代）但给出相同的结果。

Answer 3

你的第二种方法溢出了，因为你在循环中使用了 int。将其更改为 long 如下（并添加 checked）：

static long SumSquares2(int m, int n)
{
    checked
    {
        long sum = 0;

        for (long i = m; i <= n; ++i)
        {
            sum += i*i;
        }
        return sum;
    }
}

出了问题的是 i*i 在内部被计算为 int 数据类型，即使结果被转换为 long 数据类型（即变量 sum), 所以它溢出了。

为什么不同的求和算法不匹配？

Why do different algorithms of summing not match?

.net

c#

algorithm

math

integer-arithmetic