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?

Entropy

possible duplicate of Fastest way to determine if an integer's square root is an integer – Sikhism

The problem is Euler project no. 3, last discussed here: https://mcmap.net/q/1630851/-advice-on-how-to-make-my-algorithm-faster/3088138 – Poe

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.

Sharlasharleen

Yep. This should work for factor[i] up to 2^53 or so. – Serranid

Yes, and since factor is a vector of int's, we're safe. – Sharlasharleen

Well int could be 64-bit for all we know. :) – Serranid

But then I suppose your 2^53 limit would be raised too. Where did you get it, btw? – Sharlasharleen

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. – Serranid

(Because there is 1 sign bit, 11 exponent bits, and 52 (plus one hidden) mantissa bits) – Serranid

@Serranid I'm still not 100% convinced that this would affect the result in this particular case, but you are right. I'll add this to the answer. – Sharlasharleen

Answer 2

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.

Sternutatory

I don't think "decimal" is the right word, since we're not talking about strings. – Vulgate

Thanks. Although decimal portion made sense, it wasn't the correct way of saying it. I had to look up what the numbers before and after the decimal place were called. Apparently one of the accepted methods is fractional part. Found the answer here. – Sternutatory

Answer 3

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

Sikhism

if ((((1<<0)|(1<<1)|(1<<4)|(1<<9)) & (1 << (n & 15)))!=0) ... – Corridor

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])  
     }
}

Chacha

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.

Poe

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

Stretchy

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
         }
     }
}

Changeover