什么是有效的算法来逐位找到一个非常大的整数平方根？

Question

我需要编写程序来查找长度为数千位的数字的整数平方根.我不能使用Newton Raphson,因为我没有数据类型来存储和划分这么大的数字.我在C中使用长数组来存储数字.是否有任何算法可以通过迭代数字找到平方根？

编辑:

我不能像GMP一样使用外部库.

Answer 1

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