fork(2) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
True
False
True
https://ideone.com/xeoSUx
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

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!