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.
Programming Praxis 
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.
# Quadratic residues mod d64 = set((0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57)) d63 = set((0, 1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37, 43, 46, 49, 58)) d25 = set((0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24)) d31 = set((0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28)) d23 = set((0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18)) d19 = set((0, 1, 4, 5, 6, 7, 9, 11, 16, 17)) d17 = set((0, 1, 2, 4, 8, 9, 13, 15, 16)) d11 = set((0, 1, 3, 4, 5, 9)) def is_square(n): """using sets""" return (n % 64 in d64 and n % 63 in d63 and n % 25 in d25 and n % 31 in d31 and n % 23 in d23 and n % 19 in d19 and n % 17 in d17 and n % 11 in d11 and isqrt(n)**2 == n) a64 = [1 if i in d64 else 0 for i in range(64)] a63 = [1 if i in d63 else 0 for i in range(63)] a25 = [1 if i in d25 else 0 for i in range(25)] a31 = [1 if i in d31 else 0 for i in range(31)] a23 = [1 if i in d23 else 0 for i in range(23)] a19 = [1 if i in d19 else 0 for i in range(19)] a17 = [1 if i in d17 else 0 for i in range(17)] a11 = [1 if i in d11 else 0 for i in range(11)] def is_square2(n): """using lists""" return (a64[n % 64] and a63[n % 63] and a25[n % 25] and a31[n % 31] and a23[n % 23] and a19[n % 19] and a17[n % 17] and a11[n % 11] and isqrt(n)**2 == n)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 ;)