StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem with relying on any floating point computation (<code>math.sqrt(x)</code>, or <code>x**0.5</code>) is that you can't really be sure it's exact (for sufficiently large integers <code>x</code>, 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...:</p> <pre><code>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) </code></pre> <p>Hint: it's based on the "Babylonian algorithm" for square root, see <a href="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots" rel="noreferrer">wikipedia</a>. It <em>does</em> work for any positive number for which you have enough memory for the computation to proceed to completion;-).</p> <p><strong>Edit</strong>: let's see an example...</p> <pre><code>x = 12345678987654321234567 ** 2 for i in range(x, x+2): print i, is_square(i) </code></pre> <p>this prints, as desired (and in a reasonable amount of time, too;-):</p> <pre><code>152415789666209426002111556165263283035677489 True 152415789666209426002111556165263283035677490 False </code></pre> <p>Please, before you propose solutions based on floating point intermediate results, make sure they work correctly on this simple example -- it's not <strong>that</strong> hard (you just need a few extra checks in case the sqrt computed is a little off), just takes a bit of care.</p> <p>And then try with <code>x**7</code> and find clever way to work around the problem you'll get,</p> <pre><code>OverflowError: long int too large to convert to float </code></pre> <p>you'll have to get more and more clever as the numbers keep growing, of course.</p> <p>If I <em>was</em> in a hurry, of course, I'd use <a href="http://www.gmpy.org/" rel="noreferrer">gmpy</a> -- but then, I'm clearly biased;-).</p> <pre><code>>>> import gmpy >>> gmpy.is_square(x**7) 1 >>> gmpy.is_square(x**7 + 1) 0 </code></pre> <p>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;-)...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload