while 循环停止处理大数 C#

Question

我的 while 循环在 10_000 上工作正常，但在 100_000 上加载需要时间，并且在 10_000_000 上不起作用。

我不明白为什么，它是一台机器，无论数字多少，它都应该很快。所以我认为我的代码中有一个错误，但对我来说，一切看起来都很好。

实施这个

Console.WriteLine(SumSequenceElements(10_000_000));

static double SumSequenceElements(int n)
{
   int i = 1;
   double sum = 0;
   while (i <= n)
   {
      int j = 0;
      double power = 1;
      while (j < i + 1)
      {
         power *= -1;
         j++;
      }

      sum += power / (i * (i + 1));
      i++;
   }

   return sum;
}

Answer 1

(-1)^k是+1ifk是偶数和-1ifk是奇数。现在，我们有k = i + 1. 即，只要i是偶数，则k是奇数，反之亦然。\n或者，换句话说，(-1)^(i+1)是-1ifi偶数，+1ifi是奇数。

\n

您可以通过查看除以 2 的余数来测试 an 是否int为偶数。C# 的模运算符%会生成该余数。

\n

static double SumSequenceElements(int n)\n{\n   int i = 1;\n   double sum = 0;\n   while (i <= n)\n   {\n      double power = i % 2 == 0 ? -1 : +1;\n      sum += power / (i * (i + 1));\n      i++;\n   }\n\n   return sum;\n}\n

\n

通过避免内循环，计算复杂度从O(n^2)降低到O(n)，即从二次降低到线性。A 在我的电脑上做了一个小基准测试。当 n = 100 万时，我的两种方法（上面和下面）都需要 2 毫秒才能运行，你的方法在我的 PC 上大约需要 16 分钟。这正是预期的 1/2 百万的速度提升，对应于外循环 1 次迭代的内循环运行的平均次数。

\n

顺便说一句，?:是三元条件运算符。

\n

由于该 +/-1 幂的符号在每次迭代时都会在 + 和 - 之间切换。你也可以写：

\n

static double SumSequenceElements(int n)\n{\n   int i = 1;\n   double power = 1; // Since we start with i = 1\n   double sum = 0;\n   while (i <= n)\n   {\n      sum += power / (i * (i + 1));\n      power *= -1; // Change the sign of power\n      i++;\n   }\n\n   return sum;\n}\n

\n

这与您执行的计算相同，但power = 1我们不是使用每次都开始的嵌套循环，而是在外循环中连续计算它。

\n

power *= -1使用复合赋值来计算power = power * -1。

\n\n

更新：数值错误的来源

\n

作为计算的一部分，我们计算i * (i + 1)。i范围int为 ~ -20 亿到 +20 亿。当 i >= 46340（即 ~sqrt(2^31)）时，我们会出现算术溢出。

\n

有两种可能性可以修复该错误：

\n

\n
1. 声明i为long. 适用于 n < ~ 30 亿 ~ sqrt(2^63)。
\n
2. 而是计算一下i * (i + 1.0)。请注意，我们添加1.0而不是1. 这将从int算术切换到double算术 Max(double) = ~1.7 \xc3\x97 10^308。
\n

\n

我们可以做的另一个改进是反转循环。将小数添加到大得多的数会导致浮点数精度损失。因此，我们应该从添加小分数开始。

\n

通过使用longand1.0我们不受 20 亿的限制n，也不受 30 亿的限制i * (i + 1)。我的最终解决方案还使用反向循环来提高精度：

\n

static double SumSequenceElements(int n)\n{\n   int i = 1;\n   double sum = 0;\n   while (i <= n)\n   {\n      double power = i % 2 == 0 ? -1 : +1;\n      sum += power / (i * (i + 1));\n      i++;\n   }\n\n   return sum;\n}\n

\n

该版本比前向循环要快一些，因为循环条件i针对常量值进行测试1，而前向循环则针对变量进行测试n。

\n

测试 n = 10,000,000,000。结果：约 21.8 秒内 0.38629436111989063。

\n