检查 BigInteger 是否为完美正方形的复杂性

Question

在我写的程序中，我使用了下面的方法来检查一个数是否是完全平方数。

// Checks whether x is a perfect square
public static boolean issqr(BigInteger x){
    a=x.sqrt();
    return x.equals(a.multiply(a));
}

在上面的代码中，使用了 BigInteger class 中的以下方法：-

BigInteger multiply(BigInteger num) : Returns 这个和 num 的乘积。
boolean equals(object obj) : 检查 this 和 obj 之间是否相等。
BigInteger sqrt() : Returns this 的平方根的整数部分。

我相信 Java 中的 sqrt() 方法使用了牛顿法，它可以模拟二进制搜索算法。上面的 issqr(BigInteger x) 方法必须和 BigInteger class 中的 sqrt() 方法具有相同的复杂度。但是，在比较 issqr(BigInteger x) 方法中不同 x 值的运行时间时，看起来运行时间反而呈指数增长。

二分查找算法具有指数运行时间复杂度的原因是什么？它与内存和 BigInteger 数据类型的不变性有什么关系吗？有没有更有效的算法来检查一个数字是否是一个完美的平方？提前谢谢你。

Answer 1

TL;DR - 很复杂！

根据 Emil Jeřábek 在 https://cstheory.stackexchange.com/a/9709

中的说法

The square root of an N-digit number can be computed in time O(M(n)) using e.g. Newton’s iteration, where M(N) is the time needed to multiply two N-digit integers. The current best bound on M(n) is N logN 2^O(logN) using Fürer’s algorithm.

因此完整检查的理论复杂度为 O(M(N)) + O(M(N/2))，减少为 O(M(N))。

在实践中，我们需要看看BigInteger是如何实现的。根据 Java11 源代码中的注释

"The implementation [of MutableBigInteger.sqrt()] is based on the material in Henry S. Warren, Jr., Hacker's Delight (2nd ed.) (Addison Wesley, 2013), 279-282.

根据源代码，Java11BigInteger.multiply(BigInteger)实现使用：

一个简单的 "grade school" 小数算法，
Karatsuba algorithm，中间数，或
"optimal" 3-way Toom-Cook 算法，适用于非常大的数字。

后者在 特征 2 和 0 中的单变量和多元多项式的最优 Toom-Cook 乘法中进行了描述。 Marco BODRATO 着；在 C.Carlet 和 B.Sunar 编辑中，"WAIFI'07 proceedings".

我无法访问参考资料来检查他们分别对 3-way Toom-Cook 或 Warren 算法的复杂性的看法。但是，维基百科说 N 位数的 Karatsuba 乘法具有 Θ(N**log2(3)) 的渐近界限。

基于此，我们可以说使用 BigInteger 检查 N 位数字是否是完全平方数可能是 O(N**log2(3)) = = O(N**~1.585) 或更好.

检查 BigInteger 是否为完美正方形的复杂性

Complexity of checking whether a BigInteger is a perfect square

java

biginteger