提问人：Vita 提问时间：8/5/2023 最后编辑：UkFLSUIVita 更新时间：8/10/2023 访问量：146
而循环停止处理大数 C#
while loop stop working with big numbers c#
问：
我的 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;
}
答：
7赞
Olivier Jacot-Descombes
8/5/2023
#1
(-1)^k如果是偶数，如果是奇数。现在，我们有.即，每当是偶数时，则为奇数，反之亦然。
或者，换句话说，是如果偶数和如果是奇数。+1k-1kk = i + 1ik(-1)^(i+1)-1i+1i
您可以通过查看除法的余数 2 来测试 an 是否为偶数。C# 的模运算符 % 产生此余数。int
static double SumSequenceElements(int n)
{
int i = 1;
double sum = 0;
while (i <= n)
{
double power = i % 2 == 0 ? -1 : +1;
sum += power / (i * (i + 1));
i++;
}
return sum;
}
通过避免内部循环，计算复杂度从 O（n^2） 降低到 O（n），即从二次降低到线性。A在我的PC上做了一个小基准测试。当 n = 100 万时，我的两个方法（上面和下面）都需要 2 毫秒才能运行，您的方法在我的 PC 上大约需要 16 分钟。这正是 1/2 一百万的预期速度增加，对应于内循环运行外循环 1 次迭代的平均次数。
顺便说一句，是三元条件运算符。?:
由于这个 +/-1 幂的符号在每次迭代时都在 + 和 - 之间切换。你也可以写：
static double SumSequenceElements(int n)
{
int i = 1;
double power = 1; // Since we start with i = 1
double sum = 0;
while (i <= n)
{
sum += power / (i * (i + 1));
power *= -1; // Change the sign of power
i++;
}
return sum;
}
这与你所做的计算相同，但不是使用每次都开始的嵌套循环，而是在外部循环中连续计算它。power = 1
power *= -1使用 Compound 赋值来计算 。power = power * -1
更新：数值误差的来源
作为计算的一部分，我们计算 . 是一个范围为 ~ -2 十亿到 +2 十亿。当 i 为 >= 46340（即 ~sqrt（2^31））时，我们得到一个算术溢出。i * (i + 1)iint
有两种方法可以修复此错误：
- 声明为 .适用于 n < ~ 3 十亿 ~ sqrt（2^63）。
ilong - 而是计算。请注意，我们添加 而不是 .这将从算术切换到 Max（double） = ~1.7 × 10^308 的算术。
i * (i + 1.0)1.01intdouble
我们可以做的另一项改进是反转循环。将小数与大得多的数字相加会导致浮点数的精度损失。因此，我们应该从添加小分数开始。
通过使用，我们不受 2 十亿限制的限制，而不是 ~3 十亿限制的限制。我的终极解决方案还使用反向循环来提高精度：long1.0ni * (i + 1)
static double SumSequenceElements(long n)
{
long i = n;
double power = i % 2 == 0 ? -1 : +1;
double sum = 0;
while (i >= 1) {
sum += power / (i * (i + 1.0));
power *= -1; // Change the sign of power
i--;
}
return sum;
}
这个版本比前向循环要快一些，因为循环条件测试与常量值，而前向循环则与变量测试它。i1n
测试 n = 10,000,000,000。结果：~21.8 秒内为 0.38629436111989063。
评论
0赞
Vita
8/5/2023
谢谢你，你的决定很好。不幸的是，我有大约 5 个类似的任务，并且有不同的幂数，而不仅仅是变化符号 +-。我还被告知要用 while 语句来提升权力。从上面的评论中，我得到了内部循环不起作用，所以也许我会把它放在外面，Idk，但无论如何谢谢你）
0赞
Vita
8/5/2023
对不起，出于好奇，我尝试了您的解决方案，但它也不适用于我的数字......
0赞
Olivier Jacot-Descombes
8/5/2023
你的内循环确实有效。问题是，它将在每个外部循环中平均循环 n/2 次。与外循环一起，这给出了 n * n/2 次重复。因此，对于 1,000,000,000，您将获得 500,000,000,000 次迭代。
0赞
Olivier Jacot-Descombes
8/5/2023
我的第二个解决方案使用 while 循环来计算功率。为此，它重用了已经存在的外循环。但是，有更有效的方法可以用更少的迭代来计算循环中的幂：实现基于整数的幂函数 pow（int， int） 的最有效方法。顺便说一句：我的方法需要 2 毫秒，n = 100 万，你的方法在我的 PC 上需要 16 分钟
1赞
Olivier Jacot-Descombes
8/7/2023
我找到了错误的根源。这是由于大数的算术溢出。在我的回答中查看我的更新。
1赞
Iron filings
8/5/2023
#2
Olivier 的回答非常好，我建议使用它，但看到这个我很好奇，发现了一个恒定的时间近似值，详见下文。
首先，分数 1/i（i+1）（请原谅我缺少 LaTeX）等于 1/i + 1/（i+1） - 2/（i+1）。这可以通过部分馏分分解来确定，并通过重新组合馏分来确认。然后，总和变为：
1/1 + 1/2 - 1/2 - 1/3 + 1/3 + ... + （-1）^（n+1）*（1/（n+1）） - 2H_n - 1. 第一位望远镜，除了第一项和最后一项外，其他所有都取消了： 1 + （-1）^（n+1）*（1/（n+1）） - 2H_n - 1，进一步简化为： （-1）^（n+1）*（1/（n+1）） - 2H_n.
在这一点上，n次谐波数的近似值（这里有一些）可以应用于所需的任何精度和在恒定时间内获得的总和。
2赞
Luuk
8/7/2023
#3
“我不明白为什么，这是一台机器，无论数字如何，它都应该很快”
在检查循环需要多少时间时，您可以将代码更改为：
static double SumSequenceElements(int n)
{
int i = 1;
double sum = 0;
DateTime d = DateTime.Now;
while (i <= n)
{
if (i % 100000 == 0) {
Console.WriteLine($"{(DateTime.Now-d).TotalSeconds:N5}: {i}");
d=DateTime.Now;
}
int j = 0; //.......(rest of code unchanged)
它产生了如下输出：
10,66730: 100000
31,94547: 200000
53,36376: 300000
您可以看到，每一步都需要更多的时间。可以得出的一个简单的结论是，当 的值越来越大时，需要更多时间。while (j<i+1){ ... }i
请随时对此进行更多调试，以扩展您对此的了解。😉
评论