Imprecise results of logarithm and power functions in Python

Question

I am trying to complete the following exercise: https://www.codewars.com/kata/whats-a-perfect-power-anyway/train/python

I tried multiple variations, but my code breaks down when big numbers are involved (I tried multiple variations with solutions involving log and power functions):

Exercise:
Your task is to check wheter a given integer is a perfect power. If it is a perfect power, return a pair m and k with m^k = n as a proof. Otherwise return Nothing, Nil, null, None or your language's equivalent.

Note: For a perfect power, there might be several pairs. For example 81 = 3^4 = 9^2, so (3,4) and (9,2) are valid solutions. However, the tests take care of this, so if a number is a perfect power, return any pair that proves it.

The exercise uses Python 3.4.3

My code:

import math
def isPP(n):
    for i in range(2 +n%2,n,2):
            a = math.log(n,i)
            if int(a) == round(a, 1):
                if pow(i, int(a)) == n:
                    return [i, int(a)]
    return None

Question: How is it possible that I keep getting incorrect answers for bigger numbers? I read that in Python 3, all ints are treated as "long" from Python 2, i.e. they can be very large and still represented accurately. Thus, since i and int(a) are both ints, shouldn't the pow(i, int(a)) == n be assessed correctly? I'm actually baffled.

Answer 1

(edit note: also added integer nth root bellow)

you are in the right track with logarithm but you are doing the math wrong, also you are skipping number you should not and only testing all the even number or all the odd number without considering that a number can be even with a odd power or vice-versa

check this

>>> math.log(170**3,3)
14.02441559235585
>>> 

not even close, the correct method is described here Nth root

which is:

let x be the number to calculate the Nth root, n said root and r the result, then we get

rⁿ = x

take the log in any base from both sides, and solve for r

log_b( rⁿ ) = log_b( x )

n * log_b( r ) = log_b( x )

log_b( r ) = log_b( x ) / n

b^{log_b( r )} = b^{log_b( x ) / n}

r = b^{log_b( x ) / n}

so for instance with log in base 10 we get

>>> pow(10, math.log10(170**3)/3 )
169.9999999999999
>>> 

that is much more closer, and with just rounding it we get the answer

>>> round(169.9999999999999)
170
>>> 

therefore the function should be something like this

import math

def isPP(x):
    for n in range(2, 1+round(math.log2(x)) ):
        root   = pow( 10, math.log10(x)/n )
        result = round(root)
        if result**n == x:
            return result,n

the upper limit in range is to avoid testing numbers that will certainly fail

test

>>> isPP(170**3)
(170, 3)
>>> isPP(6434856)
(186, 3)
>>> isPP(9**2)
(9, 2)
>>> isPP(23**8)
(279841, 2)
>>> isPP(279841)
(529, 2)
>>> isPP(529)
(23, 2)
>>> 

EDIT

or as Tin Peters point out you can use pow(x,1./n) as the nth root of a number is also expressed as x^1/n

for example

>>> pow(170**3, 1./3)
169.99999999999994
>>> round(_)
170
>>> 

but keep in mind that that will fail for extremely large numbers like for example

>>> pow(8191**107,1./107)
Traceback (most recent call last):
  File "<pyshell#90>", line 1, in <module>
    pow(8191**107,1./107)
OverflowError: int too large to convert to float
>>> 

while the logarithmic approach will success

>>> pow(10, math.log10(8191**107)/107)
8190.999999999999
>>> 

the reason is that 8191¹⁰⁷ is simple too big, it have 419 digits which is greater that the maximum float representable, but reducing it with a log produce a more reasonable number

EDIT 2

now if you want to work with numbers ridiculously big, or just plain don't want to use floating point arithmetic altogether and use only integer arithmetic, then the best course of action is to use the method of Newton, that the helpful link provided by Tin Peters for the particular case for cube root, show us the way to do it in general alongside the wikipedia article

def inthroot(A,n):
    if A<0:
        if n%2 == 0:
            raise ValueError
        return - inthroot(-A,n)
    if A==0:
        return 0
    n1 = n-1
    if A.bit_length() < 1024: # float(n) safe from overflow
        xk = int( round( pow(A,1/n) ) )
        xk = ( n1*xk + A//pow(xk,n1) )//n  # Ensure xk >= floor(nthroot(A)).
    else:
        xk = 1 << -(-A.bit_length()//n)  # power of 2 closer but greater than the nth root of A
    while True:
        sig = A // pow(xk,n1)
        if xk <= sig:
            return xk
        xk = ( n1*xk + sig )//n

check the explanation by Mark Dickinson to understand the working of the algorithm for the case of cube root, which is basically the same for this

now lets compare this with the other one

>>> def nthroot(x,n):
        return pow(10, math.log10(x)/n )

>>> n = 2**(2**12) + 1  # a ridiculously big number
>>> r = nthroot(n**2,2)
Traceback (most recent call last):
  File "<pyshell#48>", line 1, in <module>
    nthroot(n**2,2)
  File "<pyshell#47>", line 2, in nthroot
    return pow(10, math.log10(x)/n )
OverflowError: (34, 'Result too large')
>>> r = inthroot(n**2,2)
>>> r == n
True
>>> 

then the function is now

import math

def isPPv2(x):
    for n in range(2,1+round(math.log2(x))):
        root = inthroot(x,n)
        if root**n == x:
            return root,n

test

>>> n = 2**(2**12) + 1  # a ridiculously big number
>>> r,p = isPPv2(n**23)
>>> p
23
>>> r == n
True
>>> isPPv2(170**3)
(170, 3)
>>> isPPv2(8191**107)
(8191, 107)
>>> isPPv2(6434856)
(186, 3)
>>>

now lets check isPP vs isPPv2

>>> x = (1 << 53) + 1
>>> x
9007199254740993
>>> isPP(x**2)
>>> isPPv2(x**2)
(9007199254740993, 2)
>>>     

clearly, avoiding floating point is the best choice