Check if a number is a perfect square

Question

How could I check if a number is a perfect square   Speed is of no concern  for now  just working

User · Answer

This response doesn t pertain to your stated question  but to an implicit question I see in the code you posted  ie   how to check if something is an integer    The first answer you ll generally get to that question is  Don t   And it s true that in Python  typechecking is usually not the right thing to do   For those rare exceptions  though  instead of looking for a decimal point in the string representation of the number  the thing to do is use the isinstance function    gt  gt  gt  isinstance 5 int  True  gt  gt  gt  isinstance 5 0 int  False   Of course this applies to the variable rather than a value  If I wanted to determine whether the value was an integer  I d do this    gt  gt  gt  x 5 0  gt  gt  gt  round x     x True   But as everyone else has covered in detail  there are floating-point issues to be considered in most non-toy examples of this kind of thing

User · Answer

import math  def is square n       sqrt   math sqrt n      return sqrt    int sqrt    It fails for a large non-square such as 152415789666209426002111556165263283035677490

User · Answer

My answer is   def is square x       return x   5   1    0   It basically does a square root  then modulo by 1 to strip the integer part and if the result is 0 return True otherwise return False  In this case x can be any large number  just not as large as the max float number that python can handle  1 7976931348623157e 308  It is incorrect for a large non-square such as 152415789666209426002111556165263283035677490

User · Answer

Since you can never depend on exact comparisons when dealing with floating point computations  such as these ways of calculating the square root   a less error-prone implementation would be  import math  def is square integer       root   math sqrt integer      return integer    int root   0 5     2   Imagine integer is 9  math sqrt 9  could be 3 0  but it could also be something like 2 99999 or 3 00001  so squaring the result right off isn t reliable  Knowing that int takes the floor value  increasing the float value by 0 5 first means we ll get the value we re looking for if we re in a range where float still has a fine enough resolution to represent numbers near the one for which we are looking

User · Answer

a int input  enter any number    flag 0 for i in range 1 a       if a  i i          print a  is perfect square number           flag 1         break if flag  1      pass else      print a  is not perfect square number

User · Answer

The problem with relying on any floating point computation  math sqrt x   or x  0 5  is that you can t really be sure it s exact  for sufficiently large integers x  it won t be  and might even overflow   Fortunately  if one s in no hurry -  there are many pure integer approaches  such as the following      def is square apositiveint     x   apositiveint    2   seen   set  x     while x   x    apositiveint      x    x    apositiveint    x      2     if x in seen  return False     seen add x    return True  for i in range 110  130      print i  is square i    Hint  it s based on the  Babylonian algorithm  for square root  see wikipedia   It does work for any positive number for which you have enough memory for the computation to proceed to completion -    Edit  let s see an example     x   12345678987654321234567    2  for i in range x  x 2      print i  is square i    this prints  as desired  and in a reasonable amount of time  too -    152415789666209426002111556165263283035677489 True 152415789666209426002111556165263283035677490 False   Please  before you propose solutions based on floating point intermediate results  make sure they work correctly on this simple example -- it s not that hard  you just need a few extra checks in case the sqrt computed is a little off   just takes a bit of care   And then try with x  7 and find clever way to work around the problem you ll get   OverflowError  long int too large to convert to float   you ll have to get more and more clever as the numbers keep growing  of course   If I was in a hurry  of course  I d use gmpy -- but then  I m clearly biased -     gt  gt  gt  import gmpy  gt  gt  gt  gmpy is square x  7  1  gt  gt  gt  gmpy is square x  7   1  0   Yeah  I know  that s just so easy it feels like cheating  a bit the way I feel towards Python in general -  -- no cleverness at all  just perfect directness and simplicity  and  in the case of gmpy  sheer speed -

User · Answer

If youre interested  I have a pure-math response to a similar question at math stackexchange   Detecting perfect squares faster than by extracting square root    My own implementation of isSquare n  may not be the best  but I like it  Took me several months of study in math theory  digital computation and python programming  comparing myself to other contributors  etc   to really click with this method  I like its simplicity and efficiency though  I havent seen better  Tell me what you think   def isSquare n          Trivial checks     if type n     int      integer         return False     if n  lt  0          positivity         return False     if n    0          0 pass         return True         Reduction by powers of 4 with bit-logic     while n amp 3    0              n n gt  gt 2         Simple bit-logic test  All perfect squares  in binary         end in 001  when powers of 4 are factored out      if n amp 7    1          return False      if n  1          return True     is power of 4  or even power of 2          Simple modulo equivalency test     c   n 10     if c in  3  7           return False     Not 1 4 5 6 9 in mod 10     if n   7 in  3  5  6           return False     Not 1 2 4 mod 7     if n   9 in  2 3 5 6 8           return False       if n   13 in  2 5 6 7 8 11           return False           Other patterns     if c    5      if it ends in a 5         if  n  10  10    2              return False       then it must end in 25         if  n  100  10 not in  0 2 6                return False       and in 025  225  or 625         if  n  100  10    6              if  n  1000  10 not in  0 5                   return False       that is  0625 or 5625     else          if  n  10  4    0              return False        4k  10    1 9           Babylonian Algorithm  Finding the integer square root         Root extraction      s    len str n  -1     2     x    10  s    4      A    x  n      while x   x    n          x    x    n    x    gt  gt  1         if x in A              return False         A add x      return True   Pretty straight forward  First it checks that we have an integer  and a positive one at that  Otherwise there is no point    It lets 0 slip through as True  necessary or else next block is infinite loop    The next block of code systematically removes powers of 4 in a very fast sub-algorithm using bit shift and bit logic operations   We ultimately are not finding the isSquare of our original n but of a k lt n that has been scaled down by powers of 4  if possible  This reduces the size of the number we are working with and really speeds up the Babylonian method  but also makes other checks faster too   The third block of code performs a simple Boolean bit-logic test   The least significant three digits  in binary  of any perfect square are 001  Always  Save for leading zeros resulting from powers of 4  anyway  which has already been accounted for   If it fails the test  you immediately know it isnt a square  If it passes  you cant be sure   Also  if we end up with a 1 for a test value then the test number was originally a power of 4  including perhaps 1 itself   Like the third block  the fourth tests the ones-place value in decimal using simple modulus operator  and tends to catch values that slip through the previous test  Also a mod 7  mod 8  mod 9  and mod 13 test   The fifth block of code checks for some of the well-known perfect square patterns  Numbers ending in 1 or 9 are preceded by a multiple of four  And numbers ending in 5 must end in 5625  0625  225  or 025  I had included others but realized they were redundant or never actually used   Lastly  the sixth block of code resembles very much what the top answerer - Alex Martelli - answer is   Basically finds the square root using the ancient Babylonian algorithm  but restricting it to integer values while ignoring floating point  Done both for speed and extending the magnitudes of values that are testable  I used sets instead of lists because it takes far less time  I used bit shifts instead of division by two  and I smartly chose an initial start value much more efficiently   By the way  I did test Alex Martelli s recommended test number  as well as a few numbers many orders magnitude larger  such as   x 1000199838770766116385386300483414671297203029840113913153824086810909168246772838680374612768821282446322068401699727842499994541063844393713189701844134801239504543830737724442006577672181059194558045164589783791764790043104263404683317158624270845302200548606715007310112016456397357027095564872551184907513312382763025454118825703090010401842892088063527451562032322039937924274426211671442740679624285180817682659081248396873230975882215128049713559849427311798959652681930663843994067353808298002406164092996533923220683447265882968239141724624870704231013642255563984374257471112743917655991279898690480703935007493906644744151022265929975993911186879561257100479593516979735117799410600147341193819147290056586421994333004992422258618475766549646258761885662783430625    2 for i in range x  x 2       print i  isSquare i     printed the following results   1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890625 True 1000399717477066534083185452789672211951514938424998708930175541558932213310056978758103599452364409903384901149641614494249195605016959576235097480592396214296565598519295693079257885246632306201885850365687426564365813280963724310434494316592041592681626416195491751015907716210235352495422858432792668507052756279908951163972960239286719854867504108121432187033786444937064356645218196398775923710931242852937602515835035177768967470757847368349565128635934683294155947532322786360581473152034468071184081729335560769488880138928479829695277968766082973795720937033019047838250608170693879209655321034310764422462828792636246742456408134706264621790736361118589122797268261542115823201538743148116654378511916000714911467547209475246784887830649309238110794938892491396597873160778553131774466638923135932135417900066903068192088883207721545109720968467560224268563643820599665232314256575428214983451466488658896488012211237139254674708538347237589290497713613898546363590044902791724541048198769085430459186735166233549186115282574626012296888817453914112423361525305960060329430234696000121420787598967383958525670258016851764034555105019265380321048686563527396844220047826436035333266263375049097675787975100014823583097518824871586828195368306649956481108708929669583308777347960115138098217676704862934389659753628861667169905594181756523762369645897154232744410732552956489694024357481100742138381514396851789639339362228442689184910464071202445106084939268067445115601375050153663645294106475257440167535462278022649865332161044187890626 False   And it did this in 0 33 seconds   In my opinion  my algorithm works the same as Alex Martelli s  with all the benefits thereof  but has the added benefit highly efficient simple-test rejections that save a lot of time  not to mention the reduction in size of test numbers by powers of 4  which improves speed  efficiency  accuracy and the size of numbers that are testable  Probably especially true in non-Python implementations   Roughly 99  of all integers are rejected as non-Square before Babylonian root extraction is even implemented  and in 2 3 the time it would take the Babylonian to reject the integer  And though these tests dont speed up the process that significantly  the reduction in all test numbers to an odd by dividing out all powers of 4 really accelerates the Babylonian test   I did a time comparison test   I tested all integers from 1 to 10 Million in succession   Using just the Babylonian method by itself  with my specially tailored initial guess  it took my Surface 3 an average of 165 seconds  with 100  accuracy   Using just the logical tests in my algorithm  excluding the Babylonian   it took 127 seconds  it rejected 99  of all integers as non-Square without mistakenly rejecting any perfect squares  Of those integers that passed  only 3  were perfect Squares  a much higher density    Using the full algorithm above that employs both the logical tests and the Babylonian root extraction  we have 100  accuracy  and test completion in only 14 seconds   The first 100 Million integers takes roughly 2 minutes 45 seconds to test   EDIT  I have been able to bring down the time further  I can now test the integers 0 to 100 Million in 1 minute 40 seconds   A lot of time is wasted checking the data type and the positivity   Eliminate the very first two checks and I cut the experiment down by a minute   One must assume the user is smart enough to know that negatives and floats are not perfect squares

User · Answer

You could binary-search for the rounded square root  Square the result to see if it matches the original value   You re probably better off with FogleBirds answer - though beware  as floating point arithmetic is approximate  which can throw this approach off  You could in principle get a false positive from a large integer which is one more than a perfect square  for instance  due to lost precision

User · Answer

Decide how long the number will be  take a delta 0 000000000000       000001 see if the  sqrt x   2 - x is greater   equal  smaller than delta and decide based on the delta error

User · Answer

Use Newton s method to quickly zero in on the nearest integer square root  then square it and see if it s your number  See isqrt   Python   3 8 has math isqrt  If using an older version of Python  look for the  def isqrt n   implementation here   import math  def is square i  int  - gt  bool      return i    math isqrt i     2

User · Answer

I just posted a slight variation on some of the examples above on another thread  Finding perfect squares  and thought I d include a slight variation of what I posted there here  using nsqrt as a temporary variable   in case it s of interest   use   import math  def is square n     if not  isinstance n  int  and  n  gt   0        return False    else      nsqrt   math sqrt n      return nsqrt    math trunc nsqrt    It is incorrect for a large non-square such as 152415789666209426002111556165263283035677490

User · Answer

If you want to loop over a range and do something for every number that is NOT a perfect square  you could do something like this   def non squares upper       next square   0     diff   1     for i in range 0  upper           if i    next square              next square    diff             diff    2             continue         yield i   If you want to do something for every number that IS a perfect square  the generator is even easier    n   n for n in range upper

User · Answer

This is my method   def is square n  - gt  bool      return int n  0 5   2    int n    Take square root of number  Convert to integer  Take the square  If the numbers are equal  then it is a perfect square otherwise not   It is incorrect for a large square such as 152415789666209426002111556165263283035677489

User · Answer

If the modulus  remainder  leftover from dividing by the square root is 0  then it is a perfect square  def is square num  int  - gt  bool      return num   math sqrt num     0  I checked this against a list of perfect squares going up to 1000

User · Answer

A variant of  Alex Martelli s solution without set  When x in seen is True    In most cases  it is the last one added  e g  1022 produces the x s sequence  511  256  129  68  41  32  31  31  In some cases  i e   for the predecessors of perfect squares   it is the second-to-last one added  e g  1023 produces 511  256  129  68  41  32  31  32    Hence  it suffices to stop as soon as the current x is greater than or equal to the previous one   def is square n       assert n  gt  1     previous   n     x   n    2     while x   x    n          x    x    n    x      2         if x  gt   previous              return False         previous   x     return True  x   12345678987654321234567    2 assert not is square x-1  assert is square x  assert not is square x 1    Equivalence with the original algorithm tested for 1  lt  n  lt  10  7  On the same interval  this slightly simpler variant is about 1 4 times faster

User · Answer

The idea is to run a loop from i   1 to floor sqrt n   then check if squaring it makes n   bool isPerfectSquare int n          for  int i   1  i   i  lt   n  i                   If  i   i   n           if   n   i    0   amp  amp   n   i    i                  return true                         return false

User · Answer

import math  def is square n       sqrt   math sqrt n      return  sqrt - int sqrt      0   A perfect square is a number that can be expressed as the product of two equal integers  math sqrt number  return a float  int math sqrt number   casts the outcome to int   If the square root is an integer  like 3  for example  then math sqrt number  - int math sqrt number   will be 0  and the if statement will be False  If the square root was a real number like 3 2  then it will be True and print  it s not a perfect square    It fails for a large non-square such as 152415789666209426002111556165263283035677490

User · Answer

This can be solved using the decimal module to get arbitrary precision square roots and easy checks for  exactness    import math from decimal import localcontext  Context  Inexact  def is perfect square x         If you want to allow negative squares  then set x   abs x  instead     if x  lt  0          return False        Create localized  default context so flags and traps unset     with localcontext Context    as ctx            Set a precision sufficient to represent x exactly   x or 1  avoids           math domain error for log10 when x is 0         ctx prec   math ceil math log10 x or 1     1    Wrap ceil call in int   on Py2           Compute integer square root  don t even store result  just setting flags         ctx sqrt x  to integral exact             If previous line couldn t represent square root as exact int  sets Inexact flag         return not ctx flags Inexact    For demonstration with truly huge values     I just kept mashing the numpad for awhile  -   gt  gt  gt  base   100009991439393999999393939398348438492389402490289028439083249803434098349083490340934903498034098390834980349083490384903843908309390282930823940230932490340983098349032098324908324098339779438974879480379380439748093874970843479280329708324970832497804329783429874329873429870234987234978034297804329782349783249873249870234987034298703249780349783497832497823497823497803429780324  gt  gt  gt  sqr   base    2  gt  gt  gt  sqr    0 5    Too large to use floating point math Traceback  most recent call last     File   lt stdin gt    line 1  in  lt module gt  OverflowError  int too large to convert to float   gt  gt  gt  is perfect power sqr  True  gt  gt  gt  is perfect power sqr-1  False  gt  gt  gt  is perfect power sqr 1  False   If you increase the size of the value being tested  this eventually gets rather slow  takes close to a second for a 200 000 bit square   but for more moderate numbers  say  20 000 bits   it s still faster than a human would notice for individual values   33 ms on my machine   But since speed wasn t your primary concern  this is a good way to do it with Python s standard libraries   Of course  it would be much faster to use gmpy2 and just test gmpy2 mpz x  is square    but if third party packages aren t your thing  the above works quite well

User · Answer

I think that this works and is very simple    import math  def is square num       sqrt   math sqrt num      return sqrt    int sqrt    It is incorrect for a large non-square such as 152415789666209426002111556165263283035677490

[python] Check if a number is a perfect square

Examples related to python

Examples related to math

Examples related to perfect-square