Programming Praxis

In many of our programs involving prime numbers and number theory, we need to be able to determine if a number n is a perfect square. One way to do that is to determine the integer square root of the number, using Newton’s method, then multiply to determine if the original number is a square. But that’s slow. In a previous exercise, we used a method devised by Henri Cohen to calculate the quadratic residues of n to various moduli, which can quickly determine that some n cannot be perfect squares.

Over at Mersenne Forum, fenderbender extends Cohen’s idea to make a ridiculously fast square predicate: he precalculates multiple moduli to reduce the operation from big integers to 32-bit integers, chooses the moduli after extensive testing, and tests the quadratic residues using a 64-bit bloom filter. The result is impressive. Where Cohen eliminates the expensive square root calculation in 99% of cases, fenderbender eliminates the expensive square root calculation in 99.92% of cases, and does it faster than Cohen. Go read fenderbender‘s explanation to see a beautiful combination of number theory, wonky programming, and sheer artistry.

Your task is to implement fenderbender‘s square predicate. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2