如何处理整数平方根法中的大输入？

Question

我需要实现一种求整数平方根的方法。

我的平台是Solidity语言，只支持整型运算，输入大小为256位(uint256)。

典型的解决方案是二进制搜索，我很容易实现。

问题是我的方法仅限于小于2^129的输入。

这是我的方法（在Python中实现）：

def sqrt(x):
    assert(x < 0x200000000000000000000000000000000);
    lo = 0;
    hi = x;
    while (True):
        mid = (lo+hi)//2;
        if (mid == lo or mid**2 == x):
            return mid;
        elif (mid**2 < x):
            lo = mid;
        else: # (mid**2 > x)
            hi = mid;

请注意，我将其发布在 Python 而不是 Solidity，因为这里的大多数用户不熟悉 Solidity，所以我认为 Python 是一个不错的选择，以便允许其他人轻松地对我的方法应用更改。

尽管如此，我通常对算法解决方案感兴趣。

Answer 1

这是在 Java，而不是 Python，纯粹是因为我已经有了这个。代码很简单，可以转换，因为所有变量都是整数，所以都是整数运算。

/**
 * Finds the integer square root of a positive number.
 * Crandall and Pomerance algorithm 9.2.11 (Newton-Raphson).
 *
 * @param num int Number to find root of.
 * @return int Integer square root of given number.
 */
public static int iSqrt(int num) {
    if (0 == num) {
        // Avoid zero divide crash
        return 0;
    }
    int x = (num / 2) + 1;
    int y = (x + (num / x)) / 2;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / 2;
    } // end while
    return x;
} // end iSqrt(int)

与您已有的非常相似，但我认为稍微简单一些。

如何处理整数平方根法中的大输入？

How to handle a large input in an integer square-root method?

algorithm

binary-search

fixed-point

square-root