Perfect integer evaluation fails with input 343

Question

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 (7³).

when asking a question, please try to always ask it in a way it can be useful to as many others as possible (with similar problems). for example, a title of "prefect integer evaluation fails with input 343" would make more sense. please also describe the resulting problem more precisely then "does not work". does it crash? lead to wrong results? or something else? — hoijui, Jun 06 '15 at 07:09

score 4 · Answer 1 · edited Jun 06 '15 at 08:19

4

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.

edited Jun 06 '15 at 08:19

answered Jun 06 '15 at 06:57

Paul Cornelius

9,245
1
15
24

But (8**(1./3.)) - is 2. Why with 343 its turns to .99999? – Araz Hajiyev Jun 06 '15 at 08:16
Because of the way computers represent floating point numbers and the round-off errors inherent in standard math functions. See [http://en.wikipedia.org/wiki/Floating_point](http://en.wikipedia.org/wiki/Floating_point) for more details than you ever wanted to know. – Paul Cornelius Jun 06 '15 at 09:04

score 0 · Accepted Answer · edited May 23 '17 at 12:06

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.

Thank you. I just tried to use math way to solve the task. Please look at this : http://www.bymath.net/studyguide/alg/sec/alg17h.gif — Araz Hajiyev, Jun 06 '15 at 08:28
Good answer, but perhaps it's better to use the standard library function round() to coerce the float results to the nearest integer. — Paul Cornelius, Jun 06 '15 at 09:09
Absolutely. I'm a noob at python, but I've done a lot of scientific computing in C++. I don't know the libraries and helpers, but I can do things manually to make sense. And perhaps `round()` would not give the desired results. @PaulCornelius — Dagrooms, Jun 06 '15 at 09:10

score 0 · Answer 3 · answered Jun 06 '15 at 10:37

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.

Perfect integer evaluation fails with input 343

3 Answers3