Programming Praxis

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