如何用整数平方根方法处理大量输入?

良好的振动

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

我的平台是Solidity语言,其中仅支持整数算术,并且iput大小为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是一个不错的选择,以便允许其他人轻松地对我的方法应用更改。

不过,我通常对算法解决方案感兴趣。

玫瑰

这是用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)

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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档