GNU Info

(gmp.info)Perfect Square Algorithm

---

Next: Perfect Power Algorithm Prev: Nth Root Algorithm Up: Root Extraction Algorithms

---

Enter node , (file) or (file)node

Perfect Square
--------------

   `mpz_perfect_square_p' is able to quickly exclude most non-squares by
checking whether the input is a quadratic residue modulo some small
integers.

   The first test is modulo 256 which means simply examining the least
significant byte.  Only 44 different values occur as the low byte of a
square, so 82.8% of non-squares can be immediately excluded.  Similar
tests modulo primes from 3 to 29 exclude 99.5% of those remaining, or
if a limb is 64 bits then primes up to 53 are used, excluding 99.99%.
A single Nx1 remainder using `PP' from `gmp-impl.h' quickly gives all
these remainders.

   A square root must still be taken for any value that passes the
residue tests, to verify it's really a square and not one of the 0.086%
(or 0.000156% for 64 bits) non-squares that get through.  Note: Square
Root Algorithm.