Converting An "Infinite" Float To An Int

Question

I'm trying to check if a number is a perfect square. However, i am dealing with extraordinarily large numbers so python thinks its infinity for some reason. it gets up to 1.1 X 10^154 before the code returns "Inf". Is there anyway to get around this? Here is the code, the lst variable just holds a bunch of really really really really really big numbers

import math
from decimal import Decimal
def main():
for i in lst:
    root = math.sqrt(Decimal(i))
    print(root)
    if int(root + 0.5) ** 2 == i:
       print(str(i) + " True")

score 3 · Answer 1 · answered Mar 29 '14 at 17:48

3

Replace math.sqrt(Decimal(i)) with Decimal(i).sqrt() to prevent your Decimals decaying into floats

answered Mar 29 '14 at 17:48

Eric

95,302
53
242
374

score 2 · Accepted Answer · answered Mar 29 '14 at 17:31

2

I think that you need to take a look at the BigFloat module, e.g.:

import bigfloat as bf
b = bf.BigFloat('1e1000', bf.precision(21))
print bf.sqrt(b)

Prints BigFloat.exact('9.9999993810013282e+499', precision=53)

answered Mar 29 '14 at 17:31

Steve Barnes

27,618
6
63
73

Without increasing the precision, it doesn't test if it is a perfect square. – casevh Mar 29 '14 at 17:34
1

Why use this module instead of using `Decimal`? – Mar 29 '14 at 17:49

casevh · Answer 3 · 2014-03-29T20:46:27.223

1

math.sqrt() converts the argument to a Python float which has a maximum value around 10^308.

You should probably look at using the gmpy2 library. gmpy2 provide very fast multiple precision arithmetic.

If you want to check for arbitrary powers, the function gmpy2.is_power() will return True if a number is a perfect power. It may be a cube or fifth power so you will need to check for power you are interested in.

>>> gmpy2.is_power(456789**372)
True

You can use gmpy2.isqrt_rem() to check if it is an exact square.

>>> gmpy2.isqrt_rem(9)
(mpz(3), mpz(0))
>>> gmpy2.isqrt_rem(10)
(mpz(3), mpz(1))

You can use gmpy2.iroot_rem() to check for arbitrary powers.

>>> gmpy2.iroot_rem(13**7 + 1, 7)
(mpz(13), mpz(1))

edited Mar 29 '14 at 20:46

answered Mar 29 '14 at 17:37

casevh

11,093
1
24
35

Is there a reason not to just use isqrt_rem() in the first place? Is is_power() significantly faster? – Rory Yorke Mar 29 '14 at 20:02
@RoryYorke I just timed both functions again. isqrt_rem() is faster than is_power(). is_power() has the advantage of checking for all possible powers. I'll update the answer. – casevh Mar 29 '14 at 20:25
@RoryYorke I made a type in my timing test. is_power() is significantly faster than isqrt_rem(). – casevh Mar 29 '14 at 20:36

score 1 · Answer 4 · answered Mar 29 '14 at 20:00

@casevh has the right answer -- use a library that can do math on arbitrarily large integers. Since you're looking for squares, you presumably are working with integers, and one could argue that using floating point types (including decimal.Decimal) is, in some sense, inelegant.

You definitely shouldn't use Python's float type; it has limited precision (about 16 decimal places). If you do use decimal.Decimal, be careful to specify the precision (which will depend on how big your numbers are).

Since Python has a big integer type, one can write a reasonably simple algorithm to check for squareness; see my implementation of such an algorithm, along with illustrations of problems with float, and how you could use decimal.Decimal, below.

import math
import decimal

def makendigit(n):
    """Return an arbitraryish n-digit number"""
    return sum((j%9+1)*10**i for i,j in enumerate(range(n)))  
x=makendigit(30)

# it looks like float will work...
print 'math.sqrt(x*x) - x: %.17g' % (math.sqrt(x*x) - x)
# ...but actually they won't
print 'math.sqrt(x*x+1) - x: %.17g' % (math.sqrt(x*x+1) - x)

# by default Decimal won't be sufficient...
print 'decimal.Decimal(x*x).sqrt() - x:',decimal.Decimal(x*x).sqrt() - x
# ...you need to specify the precision
print 'decimal.Decimal(x*x).sqrt(decimal.Context(prec=30)) - x:',decimal.Decimal(x*x).sqrt(decimal.Context(prec=100)) - x

def issquare_decimal(y,prec=1000):
    x=decimal.Decimal(y).sqrt(decimal.Context(prec=prec))
    return x==x.to_integral_value()

print 'issquare_decimal(x*x):',issquare_decimal(x*x)
print 'issquare_decimal(x*x+1):',issquare_decimal(x*x+1)

# you can check for "squareness" without going to floating point.
# one option is a bisection search; this Newton's method approach
# should be faster.

# For "industrial use" you should use gmpy2 or some similar "big
# integer" library.
def isqrt(y):
    """Find largest integer <= sqrt(y)"""
    if not isinstance(y,(int,long)):
        raise ValueError('arg must be an integer')
    if y<0:
        raise ValueError('arg must be positive')
    if y in (0,1):
        return y
    x0=y//2
    while True:
        # newton's rule
        x1= (x0**2+y)//2//x0
        # we don't always get converge to x0=x1, e.g., for y=3
        if abs(x1-x0)<=1:
            # nearly converged; find biggest
            # integer satisfying our condition
            x=max(x0,x1)
            if x**2>y:
                while x**2>y:
                    x-=1
            else:
                while (x+1)**2<=y:
                    x+=1
            return x
        x0=x1

def issquare(y):
    """Return true if non-negative integer y is a perfect square"""
    return y==isqrt(y)**2

print 'isqrt(x*x)-x:',isqrt(x*x)-x

print 'issquare(x*x):',issquare(x*x)
print 'issquare(x*x+1):',issquare(x*x+1)

Converting An "Infinite" Float To An Int

4 Answers4