Log precision in python

Question

Following is sourcecode which checks that wether a number can be expressed in power but why does the code fail for n = 76 ** 89 - 1 and n = 76 ** 89. How can I solve this error? For both n it gives x=log(n,2)/log(i,2)=89.0

from math import log,sqrt,floor
import sys
n= 76 ** 89 - 1
t=floor(sqrt(n))+1
flag=False


for i in range(2,t):
    x=log(n,2)/log(i,2)
    print(x)
    if x-int(x)<sys.float_info.epsilon:
        print("YESSSSSSSSSSSSS!")
        flag=True
        break

if not flag:
    print("Nooooooooooooooooooo!")

nice, but a real [mcve] isn't interactive. How are we supposed to enter `76 ** 89 - 1` since python 3 input doesn't perform evaluations? — Jean-François Fabre, Dec 31 '17 at 12:33
@Jean 246836689407345097174578535562295942574178711461144990797750214379645671228733039816084061952588114546106170632976745994369878558718869787931874388378698664981274034176 and 246836689407345097174578535562295942574178711461144990797750214379645671228733039816084061952588114546106170632976745994369878558718869787931874388378698664981274034175 — Demonking28, Dec 31 '17 at 12:35
What are you trying to do? You are just showing the tail of your actual problem. — user1767754, Dec 31 '17 at 12:37
As you've discovered, floating-point is not sufficient for these calculations, in general. You may make some headway by doing a sanity check once you've identified a candidate - compute `i**x` and see if it matches the original value. — Oliver Charlesworth, Dec 31 '17 at 12:38
@user1767754 - The user seems to have been fairly explicit about their aim - to write a program that determines whether an integer is an exact power. — Oliver Charlesworth, Dec 31 '17 at 12:39
I was looking into something similar: https://math.stackexchange.com/questions/4476802/is-there-a-mapping-function-to-transform-mn-to-sum-i-in-k2i-any-powe — juanmf, Jun 21 '22 at 21:00

Jean-François Fabre · Accepted Answer · 2017-12-31T23:53:41.933

3

Your code only finds candidates but doesn't check if they really match. Floating point inaccuracy makes that you cannot make the difference between a very big value like this and this same value minus one.

But since python has built-in unlimited range integer artihmetic, you could check that what you found is really a match.

My idea: once you find the power, compute the theoretical number to power (by rounding), then compute power in integer, and compare integers.

from math import log,sqrt,floor
import sys
n = 76 ** 89
t=floor(sqrt(n))+1
flag=False


for i in range(2,t):
    x=log(n,i)  # faster than x=log(n,2)/log(i,2)

    if x-int(x)<sys.float_info.epsilon:
        x = int(round(x))
        r = int(round(n**(1/x)))
        print("found candidate: ",x,r)
        if n == r**x:   # exact integer comparison with initial value & found values
            print("YESSSSSSSSSSSSS!")
            flag=True
            break
        else:
            print("but not exact")

if not flag:
    print("Nooooooooooooooooooo!")

with the 76 ** 89 - 1 value, you get "but not exact" because the computed power doesn't match n value.

Aside: it's faster to use x=log(n,i) instead of x=log(n,2)/log(i,2) and probably more accurate too as less float operations are involved.

edited Dec 31 '17 at 23:53

answered Dec 31 '17 at 12:40

Jean-François Fabre

137,073
23
153
219

1

Good stuff. But I can't convince myself that the floating-point limitations won't also be susceptible to false negatives. – Oliver Charlesworth Dec 31 '17 at 12:48
@OliverCharlesworth maybe we'll miss some with all the rounding which could go the wrong way (maybe it's what you're implying, still to find the cases) but the case we find are sure to work. – Jean-François Fabre Dec 31 '17 at 12:54
@Jean-FrançoisFabre - I'm thinking about the original `log/log` calculation - is the `epsilon` threshold sufficient to accept the result for all exact powers? – Oliver Charlesworth Dec 31 '17 at 12:58
@OliverCharlesworth that wouldn't hurt to specify a bigger epsilon. That would just be slower. another problem is that at some point `sqrt(n)` doesn't want to compute the square root: "OverflowError: int too large to convert to float". Interestingly, log works but not sqrt. – Jean-François Fabre Dec 31 '17 at 13:00
Q: Is `log(n, i)` better in terms of float point accuracy instead of `log(n, 2)/log(i, 2)`? I would expect that it is more accurate and faster. – Mr. T Dec 31 '17 at 15:55

Log precision in python

1 Answers1

Linked