5

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!

Community
  • 1
  • 1
roony
  • 155
  • 2
  • 8
  • Why don't you use `log`? –  Feb 20 '16 at 13:46
  • 1
    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. – Thomas Andrews Feb 20 '16 at 13:56
  • It should return false if the number is a square, and true if it not @ThomasAndrews – roony Feb 20 '16 at 13:59
  • 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. @roony – Thomas Andrews Feb 20 '16 at 14:10
  • 1
    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. – Thomas Andrews Feb 20 '16 at 14:13
  • double ad = Math.sqrt(4); if(ad==2) { System.out.println("true"); }else System.out.println("fasle"); – SmashCode Feb 20 '16 at 14:15
  • 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? – roony Feb 20 '16 at 14:15
  • 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. – Thomas Andrews Feb 20 '16 at 14:19
  • 1
    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);` – Thomas Andrews Feb 20 '16 at 15:14
  • 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. – duffymo Feb 20 '16 at 19:48

3 Answers3

6

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

chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • And what about Math.sqrt(n)? Shouldn't it be O(n) then? – Strahinja Jan 07 '18 at 22:18
  • 1
    `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. – chqrlie Jan 07 '18 at 23:35
1

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

Codor
  • 17,447
  • 9
  • 29
  • 56
  • 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) – roony Feb 20 '16 at 14:06
0

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.

SomeDude
  • 13,876
  • 5
  • 21
  • 44
  • And what is the worst? – roony Feb 20 '16 at 14:06
  • 1
    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. – chqrlie Feb 20 '16 at 14:22
  • @chqrlie 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 – SomeDude Feb 20 '16 at 14:41
  • @svasa: Sun's java, now Oracle's java does not use GNU Classpath. http://www.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. – chqrlie Feb 20 '16 at 15:12
  • so @chqrlie just to verify, your answers stand correctly even with this matter? Still a constant time for sqrt – roony Feb 20 '16 at 17:23
  • @roony: Yes, we all agree your solution is correct and has complexity **O(1)**. – chqrlie Feb 20 '16 at 17:48
  • @chqrlie. Good to know this. Could you tell me how can I find source code for fsqrt opcode? – SomeDude Feb 20 '16 at 22:05
  • @svasa: `fsqrt` is a machine instruction. You can download a complete reference (1500 pages) for the X86 instructions at http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf – chqrlie Feb 21 '16 at 00:07
  • @chqrlie there you go. – SomeDude Feb 21 '16 at 14:16