## Identifying Squares, Revisited

### May 7, 2019

Our solution uses the same method as fenderbender for identifying residue classes that can’t contain squares, but instead of the bloom filter that fenderbender uses, we store a bit-array in an integer:

def isSquare(n): # def q(n): # from sets import Set # s, sum = Set(), 0 # for x in xrange(0,n): # t = pow(x,2,n) # if t not in s: # s.add(t) # sum += pow(2,t) # return len(s), sum # q(64) = 12, 144680414395695635 # q(63) = 16, 288872697407275667 # q(52) = 14, 845593731871251 # q(55) = 18, 615814660213299 # q(57) = 20, 54655143861879507 # q(51) = 18, 576239692522003 # about 99.77% of non-squares are caught by the # filters prior to computation of the square root if 144680414395695635 >> (n%64) & 1 == 0: return False if 288872697407275667 >> (n%63) & 1 == 0: return False if 845593731871251 >> (n%52) & 1 == 0: return False if 615814660213299 >> (n%55) & 1 == 0: return False if 54655143861879507 >> (n%57) & 1 == 0: return False if 576239692522003 >> (n%51) & 1 == 0: return False s = isqrt(n); return s*s == n

We rearranged the filters so all of the bit arrays fit in a 64-bit integer. The percentage of numbers that are caught by the filters and avoid the computation of the square root is 1 – 12/64 * 16/63 * 7/13 * 18/55 * 10/19 * 9/17 = 1 – 108/46189 = 99.77% (repeated factors don’t count), which is very close to fenderbender’s 99.92%. If you are determined, building filters using 64, 27, 25, 49, 31, 29, 23, 19, 17, 13 and 11, in that order, gets you to 104544 / 607759061 = 99.9828%, but beware that diminishing returns set in very quickly, so do timing experiments to verify that your algorithm is useful, as the point of diminishing returns varies from one environment to another.

Our function still uses magic numbers. But we expose the magic in the comments, so anybody can verify that it’s been done correctly and there are no errors when transcribing the function. And our function is still wicked fast, even if not quite as fast as fenderbender’s function.

You can run the program at https://ideone.com/xeoSUx.

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 ;)