Noob C question

[nuggetprime]

Hi,
I'm quite a noob to C yet, so I decided to open this thread for noob C questions by me and others.
My first question is: how do I implement a function than checks if an integer is a square number?

Nice day,
nuggetprime

[bsquared]

Well, the question is more complicated than that. There are simple ways that are not particularly efficient, but may be fine for your application, or not, depending. This thread goes into some detail about the subtle issues of checking for squaritude quickly on large inputs:
http://www.mersenneforum.org/showthread.php?t=8719

But, for simple purposes on integers less than 2^32, you could just do

 
int issquare(unsigned int x)
{
   unsigned int root = (unsigned int)sqrt(x);
   if (root * root == x) return 1;
   else return 0;
}

[nuggetprime]

Thanks,
nugget

[ewmayer]

Not quite so fast - the potential problem is that if x is indeed a perfect square, the floating-point sqrt(x) may end up being just a tad less than the true square root due to roundoff error, in which case Bruce's function will yield a false negative.

Methinks there should be a nearest-int in there, say using the "poor man's NINT" like so:

(uint)(sqrt((double)x) + 0.5)

Note: The cast-to-double is also recommended to prevent a potential cast-to-single which could cause the result to overflow a single-precision mantissa. The proper default here (i.e. in the absence of an explicit cast) is cast-to-double, but when dealing with compiled code, it's always best to be safe rather than sorry and cast explicitly. Actually, the round-to-nearest may introduce enough "fudge factor" to make the result correct even if x were cast to single, but I'll let someone else do the error analysis of that scenario, if they are interested.

[Batalov]

http://alpertron.com.ar/ecm.java has a PowerCheck() routine for checking is a number is a (prime) power. It is very educational to read it. A fantastic and polished piece of work.

If you'd need to port it to C and simplify to check only for squares, there are a few not-so-impassable hurdles. One needs to use e.g. GMP instead of BigInt, so a bit of further documentation reading would be needed. But both of these are highly practical to learn.

(That reminds me of a fantastic and aptly titled 48-pager document that was and maybe still googleable "What Every Computer Scientist Should Know About Floating-Point Arithmetic". Not for this topic, but I cannot find a counter-argument how anyone could have read it and then many years later said - "there was this one time when I wasted so-and-so much time reading that".)

P.S. msieve, I think, has a code that checks for the input number being a power, too. But I didn't have time to find it. Look there. Again, your time will not be wasted.

P.P.S. ((Edit)) using GMP, seems to be already in the library by the way of calling

mpz_sqrtrem(x,rem,x); /* this means you don't need the root value */
/* catch errors if needed*/
/* then check if rem is zero. Left as an excercise to the reader */

-Serge

[jasonp]

Originally Posted by Batalov

P.S. msieve, I think, has a code that checks for the input number being a power, too. But I didn't have time to find it. Look there. Again, your time will not be wasted.

It's in common/driver.c, in msieve_run_core; basically it makes use of the fact that the input to the library has already had factors below 100k stripped out, so you can extract larger and larger roots until the result is below 100k (or you detect the input is a perfect power by exponentiating each computed root).

GMP has much more advanced algorithms.

[ATH]

If you use GMP you can check if the function mpz_perfect_square_p(x) is non-zero.

There is also the function mpz_perfect_power_p(x) which returns non-zero if x is any power a^b.