sqrt(int) vs int(sqrt(real))

[MikeStgt]

Every now and then I find something

unsigned long long n
...
unsigned long long imax = sqrt( n + 0.5 );

what to my understanding converts n to real, adds 1/2, computes real sqrt and converts the result to integer (discarding all decimal places). Nosy as I am I'd like to know the difference to imax = sqrt( n ), so n is integer I guess the sqrt procedure is a different one than for an argument of type real.
To find differences in the result I run following, alas not completely convinced if it makes sense, i) in a fundamental view, and ii) in some details.

Questions about i) are there for sure differences for the two manner to get int(sqrt(int))? If yes, where? Where in two ways, where documented and where in the number range. Probably I start my search from the wrong end, when I begin at max and decrement the chance for rounding effects could be more present.

Questions about ii) How may I make sure that imax = sqrt( n ) uses a different routine for sqrt than imax = sqrt( (real) n )? Besides unwinding the (i % 1000000000 == 0) test (to get a hint about "progress"), are there options to quicken this drudgery?

#include <iostream>		/* cout, cin, endl */
using namespace std;

int main()
{
      for(unsigned long long i = 0; i<=~0ull; i++)
    {
        unsigned long long p = sqrt( i );
        unsigned long long q = sqrt( i + .5 );
        if (p != q) cout << "\nGotcha at " << i;
        if (i % 1000000000 == 0) cout << "\n" << i;
    }
    cout << " FIN";
}

Edit: formatting

[keskiverto]

http://www.cplusplus.com/reference/cmath/sqrt/
https://en.cppreference.com/w/cpp/numeric/math/sqrt
do say that there are overloads for integral types (since C++11), but they all cast argument to double.

Therefore, your both approaches are likely to call double sqrt ( double arg );

[MikeStgt]

Thank you for your prompt reply.
So I was on the wrong track. Remains only one question, if and if yes where are differences to expect from unsigned long long p = sqrt( i ); and unsigned long long q = sqrt( i + .5 );

[lastchance]

If you are referring to another recent thread ( http://www.cplusplus.com/forum/beginner/253928/#msg1115840 ) where I used
unsigned long long imax = sqrt( n + 0.5 );
and you chose to amend it, then it was written like that "for safety's sake". The RHS will be worked out as a double (as @Keskiverto points out), then truncated down to an int to go into imax. It was making sure that there was no integer above imax but below the exact (but possibly unrepresentable) sqrt of n.

I have fallen foul of enough times when 9.99999 gets truncated to 9 not to take any chances. If the value of imax turns out to occasionally be a little larger than is strictly necessary for checking out primes then that is a small price to pay for not being wrong on primality. It wasn't aimed at being the actual square root of n ... just "safely big enough" to check that a number had any proper divisors.

As a limit on checking divisors for primes I will continue to use the +0.5 or do other schizophrenic things such as
unsigned long long imax = sqrt( n ) + 1;
The C++ standard may or may not guarantee sufficient exactitude to get away without it, but I wouldn't necessarily trust any particular compiler to adhere to it, nor to rely on it being so in other programming languages.

[Ganado]

It would have to be an integer whose sqrt produces something like X.99999, where adding 0.5 makes the sqrt of that number go just over to be (X+1).00000. But the chances of this would decrease as i gets higher (edit: actually it might increase. dunno). I don't know if such a number exists, especially because as you get into the higher numbers, I believe at some point i == i + 0.5. So the two statements might be equivalent for all integers in unsigned long long but I'm not sure how to prove it (brute force is infeasible unless you want to write some GPU program to do it).

[MikeStgt]

Yes, I am referring to that thread, but that is not the point. I comprehend your argument 'better safe than sorry'. I had to learn by keskivert's reply that my idea of sqrt() was wrong, there is nothing like a special sqrt(int). And I am about to learn about C++, which is (with my current knowledge) here and there thin ice not too loadable. Part of my learnig is asking questions. And - honestly - slowly it begins to dawn on me that the same code also may act different depending on compilers and ~ options. As such, in case I do not find any difference between int sqrt(n) and int sqrt(n+0.5) it is valid for my system and not necessarily also for others.

And then there are still the unexpected traps:

#include <iostream>
using namespace std;

bool is_prime( unsigned n )
{
    if( n < 2 ) return false ;
    if( n == 2 ) return true ; // 2 is a prime number
    if( n%2 == 0 ) return false ; // even numbers greater than two are not prime

    // trial division by odd numbers up to the square root of n
    for( unsigned div = 3 ; (div*div) <= n ; div += 2 ) if( n%div == 0 ) return false ;
    return true ; // not evenly divisible by any of the candidates
}

int main()
{
    unsigned ntt = 4294967291;
    cout << ntt << (is_prime(ntt)? " is prime." : " is not prime.");
} 

4294967291 is not prime.

Alas, it is.

Edit: set unsigned div to unsigned long div to cure it.

[keskiverto]

higher numbers, I believe at some point i == i + 0.5.

Yes, floating point type can have less significant digits than integral type. Then insignificant changes are ... insignificant. This can be a real issue in numerical methods.
See digits10 in http://www.cplusplus.com/reference/limits/numeric_limits/

Whether that rounding affects square root is ... topic of this thread?

brute force is infeasible unless you want to write some GPU program to do it

You mean that it takes too long to compute in CPU's, but workload could be split more in GPU?

The precision of GPU and CPU is not identical. It takes effort to get exact same results from both (if at all possible). Besides, most GPU's are massively parallel only for floats and half-floats; that is good enough for pretty pictures.

[MikeStgt]

If you are referring to another recent thread ( http://www.cplusplus.com/forum/beginner/253928/#msg1115840 )

You convinced me so I changed it.

[lastchance]

Yes, I should probably have commented mine too to indicate that it was purely a safety mechanism for insecurity about the precision of floating-point arithmetic.

I believe that the required accuracy of sqrt() may have hardened at some point since the initial standardisation of C++, but don't quote me on it.

[MikeStgt]

Whether that rounding affects square root is ... topic of this thread?

Yes, and still is. I give up brute force at 4,8E-6% finished. Remains unfinished ;)