## 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.

Pages: 1 2