algorithm - 在 C 中计算 1000+ 位字的平方根

Question

假设我们有我们内存中的 1000 位字。我想知道是否有任何方法可以计算它的平方根(不一定准确，可以说没有浮点部分)。或者我们只有内存位置，后来指定了各种大小。

我假设我们的大数是一个数组(最重要的位在开头？)。平方根大约是原始数的一半。当尝试使用逐位算法时，有时 usnigned long long 不足以记住部分结果(减去 01 扩展数)。如何解决？获得大数的个位数怎么办？仅通过位掩码？

思考伪代码时卡在这个问题上。有什么想法吗？

Answer 1

你会如何手工完成？您如何用手将 1000 位数字除以 500 位数字？ (想想方法，显然会很费时间)。现在有了平方根，该方法与您“猜测”第一个数字，然后是第二个数字等等的除法非常相似，然后减去东西。只是对于平方根，您减去的东西略有不同(但不是那个不同，计算平方根的方法与除法非常相似，只是每个数字相加，除数变化)。

我不想告诉您确切的操作方法，因为这会破坏您自己发现它的全部乐趣。

诀窍是:与其考虑 x 的平方根，不如考虑找到一个满足 y*y = x 的数字 y。随着您改进 y，以最小的努力重新计算 x - y*y。