Test if a number is a perfect square
Dr. Edwin Klement
edwin.klement at netsurf.de
Wed Dec 2 20:31:02 CET 2009
Hello,
I'm very interesting in number theory. Therefore I found GMP
very useful for calculation using large numbers.
Inside the procedure mpn_perfect_square_p a simple test excludes about
82% of the perfect square candidates.
With another simple test about additional 10% can be excluded after this simple test.
This can be done by calculating the digital root of a number.
This is a necessary (but not sufficient) condition for a number to be
square, the digital root of a perfect square is either 1, 4, 7, or 9
(maybe with the exception of the number ZERO).
Here is the software I use to exclude additional candidates:
int digitroot(mpz_t q)
{
mp_limb_t limb;
int result;
int i;
int j;
int qtab[] = {1, 2, 4, 8, 7, 5};
int qind;
int qsiz = sizeof(qtab) / sizeof(qtab[0]);
int qsizm1 = qsiz - 1;
int sizeoflimb = GMP_NUMB_BITS;
result = 0;
qind = 0;
if (mpz_sgn(q) <= 0) return(0);
for (i = 0; i < q->_mp_size; i++)
{
limb = q->_mp_d[i];
for (j = 0; j < sizeoflimb; j++)
{
if (limb & 1)
{
result = result + qtab[qind];
while (result >= 10) result = 1 + result - 10;
}
qind = (qind == qsizm1) ? 0 : (qind + 1);
limb >>= 1;
}
}
return(result);
}
What do you think? Is this useful to speed up the test?
Regards,
Edwin Klement
More information about the gmp-discuss
mailing list