fork download
  1. # identifying squares, revisited
  2.  
  3. def isqrt(n):
  4. if n < 1: return 0
  5. u, s = n, n+1
  6. while u < s:
  7. s = u
  8. t = s + n // s
  9. u = t // 2
  10. return s
  11.  
  12. def isSquare(n): # naive
  13. s = isqrt(n); return s*s == n
  14.  
  15. def isSquare(n): # fenderbender
  16. m = n & 127
  17. if ((m*0x8bc40d7d) & (m*0xa1e2f5d1) & 0x14020a): return False
  18. largeMod = n % (63*25*11*17*19*23*31)
  19. m = largeMod % 63
  20. if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008): return False
  21. m = largeMod % 25
  22. if ((m*0x1929fc1b) & (m*0x4c9ea3b2) & 0x51001005): return False
  23. m = 0xd10d829a * (largeMod % 31)
  24. if (m & (m+0x672a5354) & 0x21025115): return False
  25. m = largeMod % 23
  26. if ((m*0x7bd28629) & (m*0xe7180889) & 0xf8300): return False
  27. m = largeMod % 19
  28. if ((m*0x1b8bead3) & (m*0x4d75a124) & 0x4280082b): return False
  29. m = largeMod % 17
  30. if ((m*0x6736f323) & (m*0x9b1d499) & 0xc0000300): return False
  31. m = largeMod % 11
  32. if ((m*0xabf1a3a7) & (m*0x2612bf93) & 0x45854000): return False
  33. s = isqrt(n); return s*s == n
  34.  
  35. def isSquare(n):
  36. # def q(n):
  37. # from sets import Set
  38. # s, sum = Set(), 0
  39. # for x in xrange(0,n):
  40. # t = pow(x,2,n)
  41. # if t not in s:
  42. # s.add(t)
  43. # sum += pow(2,t)
  44. # return len(s), sum
  45. # q(64) = 12, 144680414395695635
  46. # q(63) = 16, 288872697407275667
  47. # q(52) = 14, 845593731871251
  48. # q(55) = 18, 615814660213299
  49. # q(57) = 20, 54655143861879507
  50. # q(51) = 18, 576239692522003
  51. # about 99.77% of non-squares are caught by the
  52. # filters prior to computation of the square root
  53. if 144680414395695635 >> (n%64) & 1 == 0: return False
  54. if 288872697407275667 >> (n%63) & 1 == 0: return False
  55. if 845593731871251 >> (n%52) & 1 == 0: return False
  56. if 615814660213299 >> (n%55) & 1 == 0: return False
  57. if 54655143861879507 >> (n%57) & 1 == 0: return False
  58. if 576239692522003 >> (n%51) & 1 == 0: return False
  59. s = isqrt(n); return s*s == n
  60.  
  61. print isSquare(36)
  62. print isSquare(27)
  63. print isSquare(123412341234*123412341234)
Success #stdin #stdout 0s 23296KB
stdin
Standard input is empty
stdout
True
False
True