Clever Geek Handbook

Optimized way to find if a number is a perfect square

I was wondering if the number was a perfect square or not:

A perfect square is an element of an algebraic structure that is equal to the square of another element.

For example: 4, 9, 16, etc.

My friends, if n

is a number, they were looping around n - 1

, 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 right.

Is it a more streamlined solution than others?

+3


source to share


7 replies


Tested and true remains:



double sqrt(double x); // from lib

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


source


You will need to know the complexity of the sqrt (x) function on your computer in order to compare it with other methods. By the way, you are calling sqrt (n) twice; consider storing it in a variable (even if the compiler will probably do it for you).

If you are using something like Newton's method, the complexity of sqrt (x) is in O(M(d))

, where M (d) measures the time it takes to multiply two d-digit numbers. Wikipedia

Your friend method is doing (n - 2) multiplications (worst case scenario), so its complexity is similar to O(n * M(x))

where x is a growing number.



Your version only uses sqrt () (ceil and floor can be ignored due to their constant complexity) making it O(M(n))

.

O(M(n)) < O(n * M(x))

- Your version is more optimized than your friend's, but not the most efficient one. Take a look at the interjay link for a better approach.

+2


source


I don't know what limits you have, but a great definition of a square number is clear

Another way to say that a (non-negative) number is a square number is that its square roots are again integers on 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))

+1


source 


#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;
}
0


source


I recommend this

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

This works because ... all integers (and only positive integers) are positive multiples of 1

and hence the solution .....

You can also run a test test; I did with the 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 only 10,049 units of time

Also, I use a few extra steps that involve type conversion

as

(unsigned long long)sqrt(Number))

Without it, he can do even better.

Hope this helps .....

To have a good day....

0


source


Your solutions are more streamlined, but may not work. Since it sqrt(x)

can return the true square root +/- epsilon, there are 3 different roots to check:

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

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

}
0


source


This is simple python code for finding the 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")
0


source






More articles:


All Articles