CODEWITHSUNDEEP
pythonmath
Araz Hajiyev
Araz Hajiyev

Reputation: 33

Perfect integer evaluation fails with input 343

Perfect power is a positive integer that can be expressed as an integer power of another positive integer.

The task is to check whether a given integer is a perfect power.

Here is my code:

def isPP2(x):
    c=[]
    for z in range(2,int(x/2)+1):

        if (x**(1./float(z)))*10%10==0:
            c.append(int(x**(1./float(z)))), c.append(z)
    if len(c)>=2:
        return c[0:2]
    else:
        return None

It works perfect with all numbers, for example:

isPP2(81)
[9, 2]
isPP2(2187)
[3, 7]

But it doesn't work with 343 (73).

Upvotes: 1

Views: 104

Answers (3)

PeterE
PeterE

Reputation: 5855

As the other answers have already explained why your algorithm fails, I will concentrate on providing an alternative algorithm that avoids the issue.

import math

def isPP2(x):
    # exp2 = log_2(x) i.e. 2**exp2 == x 
    # is a much better upper bound for the exponents to test,
    # as 2 is the smallest base exp2 is the biggest exponent we can expect.
    exp2 = math.log(x, 2)
    for exp in range(2, int(exp2)):
        # to avoid floating point issues we simply round the base we get
        # and then test it against x by calculating base**exp
        # side note: 
        #   according to the docs ** and the build in pow() 
        #   work integer based as long as all arguments are integer.
        base = round( x**(1./float(exp)) ) 
        if base**exp == x:
            return base, exp

    return None

print( isPP2(81) )        # (9, 2)
print( isPP2(2187) )      # (3, 7)
print( isPP2(343) )       # (7, 3)
print( isPP2(232**34) )   # (53824, 17)

As with your algorithm this only returns the first solution if there is more than one.

Upvotes: 0

Dagrooms
Dagrooms

Reputation: 1564

As explained in this link, floating point numbers are not stored perfectly in computers. You are most likely experiencing some error in calculation based off of this very small difference that persists in floating point calculations.

When I run your function, the equation ((x ** (1./float(z))) * 10 % 10) results in 9.99999999999999986, not 10 as is expected. This is due to the slight error involved in floating point arithmetic.

If you must calculate the value as a float (which may or may not be useful in your overall goal), you can define an accuracy range for your result. A simple check would look something like this:

precision = 1.e-6    

check = (x ** (1./float(z))) * 10 % 10
if check == 0:
    # No changes to previous code
elif 10 - check < precision:
    c.append(int(x**(1./float(z))) + 1)
    c.append(z)

precision is defined in scientific notation, being equal to 1 x 10^(-6) or 0.000001, but it can be decreased in magnitude if this large range of precision introduces other errors, which is not likely but entirely possible. I added 1 to the result since the original number was less than the target.

Upvotes: 0

Paul Cornelius
Paul Cornelius

Reputation: 10946

Because 343**(1.0/float(3)) is not 7.0, it's 6.99999999999999. You're trying to solve an integer problem with floating point math.

Upvotes: 4

Related Questions