c - 逐位查找非常大数字的整数平方根的有效算法是什么？

Question

我需要编写程序来找到一个数以千计数字长的整数平方根。我不能使用 Newton Raphson，因为我没有数据类型来存储和划分如此大的数字。我在 C 中使用一个长数组来存储数字。是否有任何算法可以通过迭代数字来找到平方根？

编辑：

我不能使用像 GMP 这样的外部库。

Answer 1

如果你能输入目标数字，那么你必须有办法存储至少一个如此大的数字。对于 Newton-Raphson，您只需要能够将数字减半和相加。想一个不使用除法将数字减半的方法。

ETA：更正：通过加倍和减法可以避免除法。

Answer 2

您的“bignum”实现似乎有很多非常不切实际的限制。我可能会建议二进制搜索？在每次迭代中，找到“中途”值mid = (hi + lo) / 2，并将搜索空间修剪为[hi, mid]或[mid, lo]取决于这些值的平方。

不如 NR 等快。但应该通过仔细处理平方范围值来收敛......

Answer 3

您可以实施长除法来计算学校教授的平方根。您可以为基数 10 实现此方法，结果从左到右逐位计算。一旦计算出整数部分，您就可以停止。