Worst case time complexity of Math.sqrt in java

Question

We have a test exercise where you need to find out whether a given N number is a square of another number or no, with the smallest time complexity.

I wrote:

public static boolean what2(int n) {
    double newN = (double)n;
    double x = Math.sqrt(newN);
    int y = (int)x;
    if (y * y == n)
        return false;
    else
        return true;
}

I looked online and specifically on SO to try and find the complexity of sqrt but couldn't find it. This SO post is for C# and says its O(1), and this Java post says its O(1) but could potentially iterate over all doubles.

I'm trying to understand the worst time complexity of this method. All other operations are O(1) so this is the only factor. Would appreciate any feedback!

Theologize

Why don't you use log? – Bikaner

Not sure if it is obvious to you, but this function doesn't answer the question asked - it only answers is a number is a square. – Yuyuan

It should return false if the number is a square, and true if it not @ThomasAndrews – Theologize

But that is not what "a given N is a power of another number" means, roony. You also need to know of N is a cube, or fifth power, or any other power. @Theologize – Yuyuan

It certainly can't be done in less than O(log N) time, because every bit is relevant, so you have to read every one of the log N bits. – Yuyuan

double ad = Math.sqrt(4); if(ad==2) { System.out.println("true"); }else System.out.println("fasle"); – Bunting

You are correct, I used the wrong word. I only need to check if its power of 2 (square). o(logN) is good. Is this the worst case complexity of sqrt? – Theologize

I don't know. The Java square root does not work with arbitrary-sized integers. You'd really need an algorithm that acts on BigInteger class for it to have a useful representation of the general question. – Yuyuan

Also, note that int y=(int) x; doesn't round, so if the error of the square root function returns 202.999999999, you are are going to test the wrong value. You need to either use an actual rounding function, or use (int)(x+0.5); – Yuyuan

The algorithm used to calculate square roots converges quadratically. You get two digits of accuracy for each iteration, so you need at least 9 iterations for 18 significant digits in double precision. – Sympathy

Answer 1

Using the floating point conversion is OK because java's int type is 32 bits and java's double type is the IEEE 64 bit format that can represent all values of 32 bit integers exactly.

If you were to implement your function for long, you would need to be more careful because many large long values are not represented exactly as doubles, so taking the square root and converting it to an integer type might not yield the actual square root.

All operations in your implementation execute in constant time, so the complexity of your solution is indeed O(1).

Trulatrull

And what about Math.sqrt(n)? Shouldn't it be O(n) then? – Fleischer

Math.sqrt(n) is implemented with a method that is much more efficient than O(n). In comparison to the rest of the code, especially with the interpreter overhead, it can be assumed to execute in constant time. – Trulatrull

Answer 2

If I understood the question correctly, the Java instruction can be converted by just-in-time-compilation to use the native fsqrt instruction (however I don't know whether this is actually the case), which, according to this table, uses a bounded number of processor cycles, which means that the complexity would be O(1).

Implausibility

Unfortunately we are not allowed to use anything beyond 'standard' methods, so only Math goes and standard serach methods. Actually most people did it with binary search but it seems abit foolish to me, and I would expect sqrt to implement binary search(if not something better) – Theologize

Answer 3

java's Math.sqrt actually delegates sqrt to StrictMath.java source code one of its implementations can be found here, by looking at sqrt function, it looks like the complexity is constant time. Look at while(r != 0) loop inside.

Kiele

And what is the worst? – Theologize

Looking at the actual code, which is not used by Oracle's java anyway, the complexity of Math.sqrt is O(1). It loops 52 times: that's not Log(N), that's constant time, much less efficient than using the floating point opcode, but still constant time. – Trulatrull

@Trulatrull Thanks. Yes the while ( r != 0 ) when initialized with 0x0020000000000000L loops aroud in 52 which is constant time. Also could you tell me why Oracle's java doesn't use this? I am looking at Math.java that belongs to java.lang and sqrt in there calls StrictMath.sqrt – Kiele

@svasa: Sun's java, now Oracle's java does not use GNU Classpath. gnu.org/software/classpath is a free portable re-implementation of the java core libraries. I'm positive the genuine java runtime uses the fsqrt opcode to implement Math.sqrt, also constant time, but much quicker. – Trulatrull

so @Trulatrull just to verify, your answers stand correctly even with this matter? Still a constant time for sqrt – Theologize

@roony: Yes, we all agree your solution is correct and has complexity O(1). – Trulatrull

@chqrlie. Good to know this. Could you tell me how can I find source code for fsqrt opcode? – Kiele

@svasa: fsqrt is a machine instruction. You can download a complete reference (1500 pages) for the X86 instructions at intel.com/content/dam/www/public/us/en/documents/manuals/… – Trulatrull

@Trulatrull there you go. – Kiele