指数方程整数解的对数解法数值精度探究

Great question—this is a classic pitfall with floating-point math, especially when working with integer inputs. Let's break this down step by step to clarify the safety of your approach and the best practices for your use case.

First, let's restate the problem clearly: we need to verify if there exists a natural number n such that x * sⁿ = y for positive int32 integers x, y, s. As you noted, this first requires checking if y is divisible by x (so z = y/x is an integer); if not, we can immediately return false. The real challenge is determining if z is an integer power of s.

The naive approach of checking n == int(n) where n = log(z)/log(s) works for many cases, but it’s not inherently safe across all inputs. Floating-point calculations of logarithms can introduce tiny rounding errors—for example, a theoretically exact integer n might become 9.0000000000001 or 8.9999999999999 due to precision limits, breaking the direct equality check.

Here’s the good news: for all positive int32 integers z and s (where s ≥ 2), if z is indeed an integer power of s, the double-precision calculation of log(z)/log(s) will be accurate enough that round(n) gives the correct integer, and even direct equality with int(n) will work—most of the time.

Why is this true?

• Double-precision floats have 53 bits of mantissa (including an implicit leading 1), which means they can represent all integers up to 2^53 (~9e15) exactly. Since the maximum int32 value is 2^31 - 1 (~2.1e9), every int32 integer can be stored perfectly as a double with no rounding loss.
• When z = sⁿ (both int32), the ratio log(z)/log(s) will compute to a value so close to the true integer n that the error is far smaller than 0.5. This means converting to an integer (or rounding) will always give the correct value.

The only critical edge case to handle separately is s = 1:

• If s = 1, the only valid z is 1 (since 1ⁿ = 1 for any n). Any other z will return false.

Your intuition about integer differences is correct: if z is not an exact power of s, the gap between the nearest power of s and z is at least 1 (since all values are integers). This gap translates to a noticeable difference between log(z)/log(s) and the nearest integer—one that’s way larger than double-precision’s inherent error margin. So direct equality checks won’t accidentally flag non-powers as valid.

That said, using an epsilon comparison is still a safer, more robust practice to eliminate any edge-case risks.

For double-precision calculations, the machine epsilon (the smallest value that can be added to 1 to get a distinct double) is ~2.2e-16, but we don’t need something that tiny. A value like 1e-12 strikes the perfect balance:

• It’s much larger than any rounding error from logarithm calculations on int32 values.
• It’s small enough that it won’t mistakenly accept non-integer powers as valid.

Here’s an improved version of your code with these safeguards:

import math

def check_power(z, s):
    # Handle s=1 edge case first
    if s == 1:
        return z == 1
    # Ensure z is a positive integer (we assume z = y/x passed divisibility check)
    if z <= 0:
        return False
    
    try:
        n = math.log(z) / math.log(s)
    except ValueError:
        return False  # Catches log(0) or negative inputs, though z is positive here
    
    # Use epsilon comparison instead of direct equality
    return abs(n - round(n)) < 1e-12

If you want a 100% precise fallback (or a way to test the logarithm method), an iterative approach works perfectly for int32 values (since the maximum number of iterations is log2(2^31) ≈ 31):

def check_power_iterative(z, s):
    if s == 1:
        return z == 1
    current = 1
    while current < z:
        current *= s
        if current == z:
            return True
    return current == z

内容的提问来源于stack exchange，提问作者Mario Dekena