[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gmp-discuss
Subject:    Test if a number is a perfect square
From:       edwin.klement () netsurf ! de (Dr !  Edwin Klement)
Date:       2009-12-02 19:31:02
Message-ID: 4B16C076.9060402 () netsurf ! de
[Download RAW message or body]

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


[prev in list] [next in list] [prev in thread] [next in thread]