检查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类的以下方法：-

• [BigInteger乘法（BigInteger num）：返回此和num的乘积。
• boolean equals（object obj）：检查此对象与obj之间是否相等。
• BigInteger sqrt（）：返回其平方根的整数部分。

我相信Java中的sqrt（）方法使用牛顿方法，该方法将对二进制搜索算法进行建模。上面的issqr（BigInteger x）方法必须具有与BigInteger类中的sqrt（）方法相同的复杂度。但是，在issqr（BigInteger x）方法中比较x的不同值的运行时间时，运行时间似乎呈指数增长。

二进制搜索算法具有指数运行时间复杂度的原因是什么？它与内存和BigInteger数据类型的不变性有关吗？有没有更有效的算法来检查数字是否为完美平方？预先谢谢你。

Answer 1

TL; DR-很复杂！

---

[根据https://cstheory.stackexchange.com/a/9709中的EmilJeřábek

N位数字的平方根可以在时间O(M(n))中使用以下公式计算：牛顿的迭代，其中M(N)是两个N位整数相乘所需的时间。 M(n)上的当前最佳界限是使用N logN 2^O(logN)的Fürer’s algorithm。

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

---

实际上，我们需要研究如何实现BigInteger。根据Java 11源代码中的注释

“ [MutableBigInteger.sqrt()]的实现基于小亨利·沃伦的材料，[哈克的喜悦（第二版）（Addison Wesley，2013年，第279-282页。

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

• 用于小数的天真的“小学”算法，
• Karatsuba algorithm，用于中间数字，或
• 用于真正大数的“最佳”三向Toom-Cook算法。

后者在]由Marco BODRATO撰写；在C.Carlet和B.Sunar编辑中，“ WAIFI'07诉讼”。我无权访问这些参考文献，以检查它们分别对三向Toom-Cook或Warren算法的复杂性说了什么。但是，维基百科说，N位数字的唐津乘运算的渐近界为Θ(N**log2(3))。

基于此，我们可以说使用BigInteger检查N位数字是否是一个完美的平方是

可能

为O(N**log2(3)) ==O(N**~1.585)或更好。