CODEWITHSUNDEEP
javabiginteger
Haran
Haran

Reputation: 103

Complexity of checking whether a BigInteger is a perfect square

In the program I am writing, I have used the following method to check whether a number is a perfect square or not.

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

In the above code, the following methods from the BigInteger class are used :-

I believe that the sqrt() method in Java uses Newton's method, which would model a binary search algorithm. The issqr(BigInteger x) method above must have the same complexity as the sqrt() method in BigInteger class. However, on comparing the run times for different values of x in the issqr(BigInteger x) method, it looks as though the run time is growing exponentially instead.

What is the reason for a binary search algorithm to have exponential run time complexity? Does it have anything to do with memory and the immutability of BigInteger datatype? Is there a more efficient algorithm to check if a number is a perfect square? Thank you in advance.

Upvotes: 0

Views: 396

Answers (1)

Stephen C
Stephen C

Reputation: 719259

TL;DR - it is complicated!

According to Emil Jeřábek in 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.

So the theoretical complexity of the complete check would be O(M(N)) + O(M(N/2)) which reduces to O(M(N)).

In practice, we need to look at how BigInteger is implemented. According to comments in the Java 11 source code

"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.

According to the source code, Java 11 BigInteger.multiply(BigInteger) implementation uses:

  • a naive "grade school" algorithm for small numbers,
  • the Karatsuba algorithm, for intermediate numbers, or
  • an "optimal" 3-way Toom-Cook algorithm for really large numbers.

The latter is described in Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. by Marco BODRATO; In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings".

I don't have access to the references to check what they say about the complexity of 3-way Toom-Cook or Warren's algorithm respectively. However, Wikipedia says that Karatsuba multiplication for N-digit numbers has an asymptotic bound of Θ(N**log2(3)).

Based on that, we can say that checking if an N-digit number is a perfect square using BigInteger is likely to be O(N**log2(3)) == O(N**~1.585) or better.

Upvotes: 4

Related Questions