How to find that a number is perfect square will efficient time complexity and without using sqrt() function ? asked 12 Nov '13, 01:49

There maybe more efficient ways, but this one is simplest. It exploits the property of perfect squares that they are sum of consecutive odd numbers from 1 to some odd number n 4 = 1 + 3
answered 12 Nov '13, 03:13
1
@rhlc92 your idea is nice however your solution runs in sqrt(n) time. A much more efficient way is to binary search on the range 1 to some maximum value until you arrive at a value. Please look at the link i have given above.
(12 Nov '13, 03:25)
@kcahdog I completely agree with you. First thing i wrote was that its not an efficient way. Its something that strikes intuitively.
(12 Nov '13, 19:46)

I think this discussion will solve your question. answered 12 Nov '13, 03:01
Using Newton's method is certain a good candidate to solve this problem due to its fast convergence, but it requires division and usually multiplications, divisions and floating point representations should be avoided. Also I'm not convinced that by avoiding the floating point computation that method will converge.
(12 Nov '13, 03:48)

@rhlc92: Your solution is very creative but still is not the fastest. One idea is to compute the integer square root of the number and if it is "exact" then we have a perfect square, otherwise we don't. This can be done by guessing the digits of the binary representation of the square root, starting with the most important digit.
Short explanation: Assuming that root is a guess for the square root, the algorithm tries to a guess another digit for the binary representation (in decreasing order) such that (root + 2^i)^2 doesn't exceed x. Computing the difference between the two numbers we have: newreminder = x  root^2  root * 2^(i+1)  2^(2 * i) = oldreminder  (root * 2^(i+1) + 2^(2 * i)) I feel that this solution can be improved further by reducing the number of operations. Also there might be some interesting ideas by using some lookup tables. answered 12 Nov '13, 03:40

Note: I am assuming you asked for integers. You can do the check in log(N) using binary search. Using binary search, you can easily find the floor value of the squareroot of the number. Then the only check you need is to see if squaring the floor value obtained gives the original number. If yes, then the original number is a perfect square, otherwise not. answered 12 Nov '13, 13:21

Found some useful solutions in this discussion. But I still found a discussion on stackoverflow with much faster algorithms. Visit this link for more explanation. I found the accepted answer by A. Rex far more faster than the Newton method. Adding the code below.
Hope this helps :) answered 12 Nov '13, 18:51
