Imprecise Results Of Logarithm And Power Functions In Python

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 bi

Solution 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 = b

r = b

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

defisPP(x):
    for n inrange(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

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 calllast):
  File "<pyshell#90>", line 1, in<module>
    pow(8191**107,1./107)
OverflowError: int too largetoconverttofloat>>>

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

definthroot(A,n):
    if A<0:
        if n%2 == 0:
            raise ValueError
        return - inthroot(-A,n)
    if A==0:
        return0
    n1 = n-1if 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 AwhileTrue:
        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

>>> defnthroot(x,n):
        returnpow(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
    returnpow(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

defisPPv2(x):
    for n inrange(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