fork download
copy 
  1. def isqrt(n):
  2.     if n < 0:
  3.         raise ValueError("x must be non-negative")
  4.     if n == 0:
  5.         return 0
  6.     x = 2 ** ((n.bit_length() - 1) // 2 + 1)    # x > sqrt(n)
  7.     y = x - 1
  8.     while y < x:
  9.         x = y
  10.         y = (x + n//x) // 2
  11.     return x
  12.  
  13. # Quadratic residues mod
  14. d64 = set((0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57))
  15. d63 = set((0, 1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37, 43, 46, 49, 58))
  16. d25 = set((0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24))
  17. d31 = set((0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28))
  18. d23 = set((0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18))
  19. d19 = set((0, 1, 4, 5, 6, 7, 9, 11, 16, 17))
  20. d17 = set((0, 1, 2, 4, 8, 9, 13, 15, 16))
  21. d11 = set((0, 1, 3, 4, 5, 9))
  22.  
  23. def is_square(n):
  24.     return (n % 64 in d64 and n % 63 in d63 and n % 25 in d25 and
  25.             n % 31 in d31 and n % 23 in d23 and n % 19 in d19 and
  26.             n % 17 in d17 and n % 11 in d11 and isqrt(n)**2 == n)
  27.  
  28. a64 = [1 if i in d64 else 0 for i in range(64)]
  29. a63 = [1 if i in d63 else 0 for i in range(63)]
  30. a25 = [1 if i in d25 else 0 for i in range(25)]
  31. a31 = [1 if i in d31 else 0 for i in range(31)]
  32. a23 = [1 if i in d23 else 0 for i in range(23)]
  33. a19 = [1 if i in d19 else 0 for i in range(19)]
  34. a17 = [1 if i in d17 else 0 for i in range(17)]
  35. a11 = [1 if i in d11 else 0 for i in range(11)]
  36.  
  37. def is_square2(n):
  38.     return (a64[n % 64] and a63[n % 63] and a25[n % 25] and a31[n % 31] and
  39.             a23[n % 23] and a19[n % 19] and a17[n % 17] and a11[n % 11] and
  40.             isqrt(n)**2 == n)
  41.  
  42. def isSquare(n):
  43.     if 144680414395695635 >> (n%64) & 1 == 0: return False
  44.     if 288872697407275667 >> (n%63) & 1 == 0: return False
  45.     if    845593731871251 >> (n%52) & 1 == 0: return False
  46.     if    615814660213299 >> (n%55) & 1 == 0: return False
  47.     if  54655143861879507 >> (n%57) & 1 == 0: return False
  48.     if    576239692522003 >> (n%51) & 1 == 0: return False
  49.     s = isqrt(n)
  50.     return s*s == n
  51.  
  52. def isSquare(n):
  53.     return (144680414395695635 >> (n%64) & 1 and
  54.             288872697407275667 >> (n%63) & 1 and
  55.             845593731871251 >> (n%52) & 1 and
  56.             615814660213299 >> (n%55) & 1 and
  57.             54655143861879507 >> (n%57) & 1 and
  58.             576239692522003 >> (n%51) & 1 and
  59.             isqrt(n) ** 2 == n)
  60.  
  61. M = (63*25*11*17*19*23*31)
  62.  
  63. def isSquare2(n): # fenderbender
  64.   m = n & 127
  65.   if ((m*0x8bc40d7d) & (m*0xa1e2f5d1) & 0x14020a): return False
  66.   largeMod = n % M
  67.   m = largeMod % 63
  68.   if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008): return False
  69.   m = largeMod % 25
  70.   if ((m*0x1929fc1b) & (m*0x4c9ea3b2) & 0x51001005): return False
  71.   m = 0xd10d829a * (largeMod % 31) 
  72.   if (m & (m+0x672a5354) & 0x21025115): return False
  73.   m = largeMod % 23
  74.   if ((m*0x7bd28629) & (m*0xe7180889) & 0xf8300): return False
  75.   m = largeMod % 19
  76.   if ((m*0x1b8bead3) & (m*0x4d75a124) & 0x4280082b): return False
  77.   m = largeMod % 17 
  78.   if ((m*0x6736f323) & (m*0x9b1d499) & 0xc0000300): return False
  79.   m = largeMod % 11 
  80.   if ((m*0xabf1a3a7) & (m*0x2612bf93) & 0x45854000): return False
  81.   s = isqrt(n); return s*s == n
  82.  
  83.  
  84. if __name__ == '__main__':
  85.     from time import clock
  86.  
  87.     def bm(meth):
  88.         t0 = clock()
  89.         cnt = 0
  90.         N = 10 ** 6
  91.         start = 10 ** 10
  92.         for n in range(start, start + N):
  93.             if meth(n):
  94.                 cnt += 1
  95.         print(meth.__name__, clock() - t0, cnt)
  96.  
  97.     bm(isSquare)
  98.     bm(isSquare2)
  99.     bm(is_square)
  100.     bm(is_square2)
  101.  
  102. """
  103. N = 10^7
  104. CPython3.6
  105. isSquare 7.860324823604874 50
  106. isSquare2 11.401496343810134 50
  107. is_square 5.880065683130212 50
  108. is_square2 6.948259140474661 50
  109.  
  110. PyPy3.6
  111. isSquare 2.482781270044901 50
  112. isSquare2 4.008553688261706 50
  113. is_square 2.052393072482361 50
  114. is_square2 1.6373788325849894 50
  115. """
  116.  
Success #stdin #stdout 0.88s 27688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
isSquare 0.218415 5
isSquare2 0.31314600000000004 5
is_square 0.16686199999999995 5
is_square2 0.16870299999999994 5
https://ideone.com/YMJ75V
language:
Python 3 nbc (python 3.7.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!