## Identifying Squares, Revisited

### May 7, 2019

Some algorithms require the ability to rapidly identify numbers such as 36 and 121 that are squares; for instance, in Fermat’s factoring algorithm, and variants derived from it, identifiying squares is the performance bottleneck of the procedure. A naive program computes the integer square root of the target number, squares it, and reports a square if it is equal to the original target:

def isqrt(n): if n < 1: return 0 u, s = n, n+1 while u < s: s = u t = s + n // s u = t // 2 return s

def isSquare(n): # naive s = isqrt(n); return s*s == n

(We are using Python instead of Scheme for this exercise because bit-operators like `&`

are easier to type than functions like `bitwise-and`

.)

This is very slow because the calculation to compute the integer square root takes a long time. In a previous exercise, we looked at a method for reducing the number of integer square roots that need to be computed:

def isSquare(n): # fenderbender m = n & 127 if ((m*0x8bc40d7d) & (m*0xa1e2f5d1) & 0x14020a): return False largeMod = n % (63*25*11*17*19*23*31) m = largeMod % 63 if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008): return False m = largeMod % 25 if ((m*0x1929fc1b) & (m*0x4c9ea3b2) & 0x51001005): return False m = 0xd10d829a * (largeMod % 31) if (m & (m+0x672a5354) & 0x21025115): return False m = largeMod % 23 if ((m*0x7bd28629) & (m*0xe7180889) & 0xf8300): return False m = largeMod % 19 if ((m*0x1b8bead3) & (m*0x4d75a124) & 0x4280082b): return False m = largeMod % 17 if ((m*0x6736f323) & (m*0x9b1d499) & 0xc0000300): return False m = largeMod % 11 if ((m*0xabf1a3a7) & (m*0x2612bf93) & 0x45854000): return False s = isqrt(n); return s*s == n

This is wicked fast because it computes residue classes based on small primes and quickly identifies numbers that cannot possibly be a square; fenderbender eliminates the expensive square root calculation in 99.92% of cases. But all those magic numbers make the function wicked, as well as wicked fast, and it is easy to make an editing error when copying the function to a new program (you will quickly and accurately guess how I know that).

Your task is to write a program that quickly identifies squares without all the magic numbers. 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.

This method is using quadratic residues for a number of modular values (each resulting in a set of allowed numbers). The speed of the method depends on how fast these sets can be accessed. In accesstimings.py the access times are measured for the different possiblillities (a set, a list, a tuple, a string, an int, a dict). The fastest methods appear to be a set or a list. The winner depends on what Python interpreter is used. In is_square.py the methods of @programmingpraxis (speeded up a little), using a set and a list are compared.

Some solutions in Racket.

@r. clayton… sorry to tell you, but your contribution is off topic and certainly belongs here: https://programmingpraxis.com/2019/05/03/three-homework-problems-4/

Nice work though ;)