Rounding ** 0.5 and math.sqrt

Question

In Python, are either

n**0.5  # or
math.sqrt(n) 

recognized when a number is a perfect square? Specifically, should I worry that when I use

int(n**0.5)  # instead of
int(n**0.5 + 0.000000001)

I might accidentally end up with the number one less than the actual square root due to precision error?

Answer 1

Yes, you should worry:

In [11]: int((100000000000000000000000000000000000**2) ** 0.5)
Out[11]: 99999999999999996863366107917975552L

In [12]: int(math.sqrt(100000000000000000000000000000000000**2))
Out[12]: 99999999999999996863366107917975552L

obviously adding the 0.000000001 doesn't help here either...

As @DSM points out, you can use the decimal library:

In [21]: from decimal import Decimal

In [22]: x = Decimal('100000000000000000000000000000000000')

In [23]: (x ** 2).sqrt() == x
Out[23]: True

for numbers over 10**999999999, provided you keep a check on the precision (configurable), it'll throw an error rather than an incorrect answer...

Answer 2

As several answers have suggested integer arithmetic, I'll recommend the gmpy2 library. It provides functions for checking if a number is a perfect power, calculating integer square roots, and integer square root with remainder.

>>> import gmpy2
>>> gmpy2.is_power(9)
True
>>> gmpy2.is_power(10)
False
>>> gmpy2.isqrt(10)
mpz(3)
>>> gmpy2.isqrt_rem(10)
(mpz(3), mpz(1))

Disclaimer: I maintain gmpy2.

Answer 3

Both **0.5 and math.sqrt() perform the calculation using floating point arithmetic. The input is converted to float before the square root is calculated.

Do these calculations recognize when the input value is a perfect square?

No they do not. Floating arithmetic has no concept of perfect squares.

large integers may not be representable, for values where the number has more significant digits than available in the floating point mantissa. It's easy to see therefore that for non-representable input values, n**0.5 may be innaccurate. And you proposed fix by adding a small value will not in general fix the problem.

If your input is an integer then you should consider performing your calculation using integer arithmetic. That ultimately is the right way to deal with this.

Answer 4

You can use the round(number, significant_figures) before converting to an int, I cannot recall if python truncs or rounds when doing a float-to-integer conversion.

In any case, since python uses floating point arithmetic, all the pitfalls apply. See:
http://docs.python.org/2/tutorial/floatingpoint.html

Answer 5

Perfect-square values will have no fractional components, so your main worry would be very large values, and for such values a difference of 1 or 2 being significant means you're going to want a specific numerical library that supports such high precision (as DSM mentions, the Decimal library, standard since Python 2.4, should be able to do what you want as it supports arbitrary precision.

http://docs.python.org/library/decimal.html

Answer 6

sqrt is one of the easier math library functions to implement, and any math library of reasonable quality will implement it with faithful rounding (sub-ULP accuracy). If the input is a perfect square, its square root is representable (in a reasonable floating-point format). In this case, faithful rounding guarantees the result is exact.

This addresses only the value actually passed to sqrt. Whether a number can be converted without error from another format to the floating-point input for sqrt is a separate issue.