在 C 中计算极大数的平方根

Question

这个问题已经有答案了:

How is the square root function implemented? [closed] (15 个回答)

已关闭 5 年前。

我正在解决一些学校奥林匹克竞赛的任务，但我被一个问题困住了。我找到了该任务的解决方案，但我的解决方案需要平方根。我的代码对于前 12 个输入工作正常，但随后给出了错误的答案。我猜想这是由于输入量非常大，可能大到 10^400000。所以我想知道是否有办法计算C中这些极大输入的平方根的整数部分。代码如下:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int main(){
    long long n;
    scanf("%lld", &n);
    long long ans;
    ans = sqrtl(n-1);
    long long result;
    result = ans+1-llabs(n-ans*ans-(ans+1));
    printf("%lld\n", result);
    return 0;
}

Answer 1

简而言之，您可以通过二分法滚动长平方根算法，如下所示:

• 选择长数字表示(无符号整数数组)；

• 实现长加法和减法(非常简单，除了进位)；

• 实现减半(也需要注意进位)；

• 实现长比较(类似于减法)。

[请注意，加法允许您实现加倍和四倍，减半也会产生除以四的结果。]

然后设置d= 1并重复将d加倍，直到d² > N。 (每次将 d 加倍，d² 就会增加四倍。)

接下来，设置a= 0以使不变式

a² ≤ N < (a + d)²

成立，并在保持不变的情况下重复将d减半。这是通过以下方式实现的:

d= d/2; 如果N ≥ (a + d)²，则设置a= a + d；否则保持 a 不变。

最后，您将缩小范围

a² ≤ N < (a + 1)²

这样a就是整数平方根。

评估条件

N < (a + d)² = a² + 2ad + d²,

或

N - a² < 2ad + d²,

只需跟踪术语 N - a²、2ad 和 d² 并在修改 d 时更新它们就足够了 或 a。这只需要前面提到的原始操作。