Determining if square root is an integer

Question

In my program, I am trying to take the find the largest prime factor of the number 600851475143. I have made one for loop that determines all the factors of that number and stores them in a vector array. The problem I am having is that I don't know how to determine if the factor can be square rooted and give a whole number rather than a decimal. My code so far is:

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
vector <int> factors;

int main()
{
    double num = 600851475143;
    for (int i=1; i<=num; i++)
    {
        if (fmod(num,i)==0)
        {
            factors.push_back(i);
        }
    }

     for (int i=0; i<factors.size(); i++)
     {
         if (sqrt(factor[i]))                      // ??? 
     }
}

Can someone show me how to determine whether a number can be square rooted or not through my if statement?

Answer 1

int s = sqrt(factor[i]);
if ((s * s) == factor[i]) 

As hobbs pointed out in the comments,

Assuming that double is the usual 64-bit IEEE-754 double-precision float, for values less than 2^53 the difference between one double and the next representable double is less than or equal to 1. Above 2^53, the precision is worse than integer.

So if your int is 32 bits you are safe. If you have to deal with numbers bigger than 2^53, you may have some precision errors.

Answer 2

Perfect squares can only end in 0, 1, 4, or 9 in base 16, So for 75% of your inputs (assuming they are uniformly distributed) you can avoid a call to the square root in exchange for some very fast bit twiddling.

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

usage:

for ( int i = 0; i < factors.size(); i++) {
   if ( isPerfectSquare( factor[ i]))
     //...
}

Fastest way to determine if an integer's square root is an integer

Answer 3

The following should work. It takes advantage of integer truncation.

if (int (sqrt(factor[i])) * int (sqrt(factor[i])) == factor[i])

It works because the square root of a non-square number is a decimal. By converting to an integer, you remove the fractional part of the double. Once you square this, it is no longer equal to the original square root.

Answer 4

You also have to take into account the round-off error when comparing to cero. You can use std::round if your compiler supports c++11, if not, you can do it yourself (here)

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
vector <int> factors;

int main()
{
    double num = 600851475143;
    for (int i=1; i<=num; i++)
    {
        if (round(fmod(num,i))==0)
        {
            factors.push_back(i);
        }
    }

     for (int i=0; i<factors.size(); i++)
     {
         int s = sqrt(factor[i]);
         if ((s * s) == factor[i])  
     }
}

Answer 5

You are asking the wrong question. Your algorithm is wrong. (Well, not entirely, but if it were to be corrected following the presented idea, it would be quite inefficient.) With your approach, you need also to check for cubes, fifth powers and all other prime powers, recursively. Try to find all factors of 5120=5*2^10 for example.

---

The much easier way is to remove a factor after it was found by dividing

num=num/i

and only increase i if it is no longer a factor. Then, if the iteration encounters some i=j^2 or i=j^3,... , all factors j, if any, were already removed at an earlier stage, when i had the value j, and accounted for in the factor array.

---

You could also have mentioned that this is from the Euler project, problem 3. Then you would have, possibly, found the recent discussion "advice on how to make my algorithm faster" where more efficient variants of the factorization algorithm were discussed.

Answer 6

Here is a simple C++ function I wrote for determining whether a number has an integer square root or not:

bool has_sqrtroot(int n)
{
    double sqrtroot=sqrt(n);
    double flr=floor(sqrtroot);
    if(abs(sqrtroot - flr) <= 1e-9)
        return true;

    return false;
}

Answer 7

As sqrt() function works with floating-point it is better to avoid working with its return value (floating-point calculation occasionally gives the wrong result, because of precision error). Rather you can write a function- isSquareNumber(int n), which will decide if the number is a square number or not and the whole calculation will be done in integer.

bool isSquareNumber(int n){
    int l=1, h=n;
    while(l<=h){
        int m = (l+h) / 2;
        if(m*m == n){
            return true;
        }else if(m*m > n){
            h = m-1;
        }else{
            l = m+1;
        }
    }
    return false;
}

int main()
{
   // ......
     for (int i=0; i<factors.size(); i++){
         if (isSquareNumber(factor[i]) == true){
              /// code
         }
     }
}