Hi All,
The following gives a small performance boost (at a minimal cost to code
size). I have not been able to get to the library and zero in on residues of
the following moduli. From
http://www.gnu.org/software/gmp/manual/html_node/Perfect-Square-Algorithm.html:
Similar tests modulo primes from 3 to 29 exclude 99.5% of those
remaining...
I tried to pull it out of the GMP library, but damn if I could find it in
their source.
Jeff
bool Integer::IsSquare() const
{
Integer r = SquareRoot();
word res = 0;
if( false == IsNegative() ) {
//
// The resudues modulo 256
//
Divide( res, r, *this, 256 );
switch( res ) {
case 0: case 1: case 4: case 9:
case 16: case 17: case 25: case 33:
case 36: case 41: case 49: case 57:
case 64: case 65: case 68: case 73:
case 81: case 89: case 97: case 100:
case 105: case 113: case 121: case 129:
case 132: case 137: case 144: case 145:
case 153: case 161: case 164: case 169:
case 177: case 185: case 193: case 196:
case 201: case 209: case 217: case 225:
case 228: case 233: case 241: case 249:
break;
default:
return false;
}
//
// The resudues modulo 100
//
Divide( res, r, *this, 100 );
switch( res ) {
case 0: case 1: case 4: case 9: case 16:
case 21: case 24: case 25: case 29: case 36:
case 41: case 44: case 49: case 56: case 61:
case 64: case 69: case 76: case 81: case 84:
case 89: case 96:
break;
default:
return false;
}
} // IsNegative()
r = SquareRoot();
return *this == r.Squared();
}
