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.

Advertisements

Pages: 1 2

3 Responses to “Identifying Squares, Revisited”

  1. Paul said

    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)
    
    """
    CPython3.6
    isSquare 7.860324823604874 50  (ProgrammingPraxis)
    isSquare2 11.401496343810134 50 (fenderbender)
    is_square 5.880065683130212 50
    is_square2 6.948259140474661 50
    
    PyPy3.6
    isSquare 2.482781270044901 50
    isSquare2 4.008553688261706 50
    is_square 2.052393072482361 50
    is_square2 1.6373788325849894 50
    """
    
  2. r. clayton said

    Some solutions in Racket.

  3. Milbrae said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: