Optimized way to find if a number is a perfect square

Question

I had a question in my assignment to find whether a number was perfect square or not:

Perfect square is an element of algebraic structure which is equal to the square of another element.

For example: 4, 9, 16 etc.

What my friends did is, if n is the number, they looped n - 1 times calculating n * n:

// just a general gist
int is_square = 0;
for (int i = 2; i < n; i++)
{
  if ((i * i) == n)
  {
    std::cout << "Yes , it is";
    is_square = 1;
    break;
  }
}
if (is_square == 0)
{
  std::cout << "No, it is not";
}

I came up with a solution as shown below:

 if (ceil(sqrt(n)) == floor(sqrt(n)))
 {
   std::cout << "Yes , it is";
 }
 else
 {
   std::cout << "no , it is not";
 }

And it works properly.

Can it be called as more optimized solution than others?

Although a Java question, the algorithms should also be applicable in C++ (and the accepted answer uses C++): [Fastest way to determine if an integer's square root is an integer](http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) — interjay, Aug 27 '14 at 16:31
in addition to all the other answers, there's a bunch of tricks you can use to right away eliminate cases. For example, all squares end in 1, 4, 5, 6, 9 and 00. — Ben, Aug 27 '14 at 16:33
I do not think your solution is 100% fool proof. It might be that sqrt(k*k) returns a number that is slightly less than k (k-epsilon), and then floor will be different from ceil. — ragnarius, Aug 27 '14 at 18:29

score 4 · Accepted Answer · answered Aug 27 '14 at 16:29

4

The tried and true remains:

double sqrt(double x); // from lib

bool is_sqr(long n) {
    long root = sqrt(n);
    return root * root == n;
}

answered Aug 27 '14 at 16:29

Paul Evans

27,315
3
37
54

score 2 · Answer 2 · answered Aug 27 '14 at 16:44

You would need to know the complexity of the sqrt(x) function on your computer to compare it against other methods. By the way, you are calling sqrt(n) twice ; consider storing it into a variable (even if the compiler probably does this for you).

If using something like Newton's method, the complexity of sqrt(x) is in O(M(d)) where M(d) measures the time required to multiply two d-digits numbers. Wikipedia

Your friend's method does (n - 2) multiplications (worst case scenario), thus its complexity is like O(n * M(x)) where x is a growing number.

Your version only uses sqrt() (ceil and floor can be ignored because of their constant complexity), which makes it O(M(n)).

O(M(n)) < O(n * M(x)) - Your version is more optimized than your friend's, but is not the most efficient. Have a look at interjay's link for a better approach.

PauloASilva · Answer 3 · 2014-08-27T17:24:39.763

1

I don't know what limitations do you have but perfect square number definition is clear

Another way of saying that a (non-negative) number is a square number, is that its square roots are again integers in wikipedia

IF SQRT(n) == FLOOR(SQRT(n)) THEN
    WRITE "Yes it is"
ELSE
    WRITE "No it isn't"

examples sqrt(9) == floor(sqrt(9)), sqrt(10) == floor(sqrt(10))

edited Aug 27 '14 at 17:24

answered Aug 27 '14 at 16:30

PauloASilva

1,000
1
7
19

Isn't SQRT(n) == FLOOR(N) only true if n is 1 or 0? – horriblyUnpythonic Aug 27 '14 at 17:15

score 1 · Answer 4 · answered Aug 27 '14 at 16:31

#include <iostream>
using namespace std;
void isPerfect(int n){
    int ctr=0,i=1;
    while(n>0){
        n-=i;
        i+=2;
        ctr++;
    }
    if(!n)cout<<"\nSquare root = "<<ctr;
    else cout<<"\nNot a perfect square";
}
int main() {
    isPerfect(3);
    isPerfect(2025);
    return 0;
}

score 0 · Answer 5 · answered Aug 27 '14 at 17:09

I'll recommend this one

if(((unsigned long long)sqrt(Number))%1==0) // sqrt() from math library
{
   //Code goes Here
}

It works because.... all Integers( & only positive integers ) are positive multiples of 1

and Hence the solution.....

You can also run a benchmark Test like; I did with following code in MSVC 2012

#include <iostream>
#include <conio.h>
#include <time.h>
#include <math.h>

using namespace std;

void IsPerfect(unsigned long long Number);

void main()
{
    clock_t Initial,Final;
    unsigned long long Counter=0;
    unsigned long long Start=Counter;
    Start--;
    cout<<Start<<endl;
    Initial=clock();
    for( Counter=0 ; Counter<=100000000 ; Counter++ )
    {
        IsPerfect( Counter );
    }
    Final=clock();
    float Time((float)Final-(float)Initial);
    cout<<"Calculations Done in "<< Time ;
    getch();
}

void IsPerfect( unsigned long long Number)
{
    if(ceil(sqrt(Number)) == floor(sqrt(Number)))
    //if(((unsigned long long)sqrt(Number))%1==0) // sqrt() from math library
    {
    }

}

Your code took 13590 time units

Mine just 10049 time units

Moreover I'm using few extra steps that is Type conversion

like

(unsigned long long)sqrt(Number))

Without this it can do still better

I hope it helps .....

Have a nice day....

ragnarius · Answer 6 · 2014-08-27T18:31:22.087

0

Your solutions is more optimized, but it may not work. Since sqrt(x) may return the true square root +/- epsilon, 3 different roots must be tested:

bool isPerfect(long x){
  double k = round( sqrt(x) );

  return (n==(k-1)*(k-1)) || (n==k*k) || (n==(k+1)*(k+1));

}

edited Aug 27 '14 at 18:31

answered Aug 27 '14 at 17:59

ragnarius

5,642
10
47
68

score 0 · Answer 7 · edited Jan 19 '18 at 03:04

0

This is simple python code for finding perfect square r not:

import math
n=(int)(input())
giv=(str)(math.sqrt(n))
if(len(giv.split('.')[1])==1):
    print  ("yes")
else:
    print ("No")

edited Jan 19 '18 at 03:04

Stephen Rauch

47,830
31
106
135

answered Jan 19 '18 at 02:44

gowtham raj

1

Optimized way to find if a number is a perfect square

7 Answers7

Linked