求满足3^k < N的最大整数k：算法优化与精度问题求助

我需要找到小于给定数字N的最大3的幂次对应的整数k。我的算法通过了大部分测试，但在Codewars的最终测试用例中超时（无法查看失败用例）。原本以为先求平方根再反向遍历是最快的方法，后来改成用立方根反向遍历，代码如下：

def largest_power(number):
    for index in range(int(number ** (1.0 / 3.0)), -1, -1):
        if 3 ** index < number:
            return index
    return -1


if __name__ == '__main__':
    result = largest_power(100)
    print(result)

但这段代码仍在某未知测试用例中超时，想找更快的实现方式。

编辑：后来尝试了对数方法，但存在测试用例失败，比如N=3时预期返回0而非1，硬编码处理这个情况后通过了该测试，但仍有其他测试失败，同样看不到具体用例：

def largest_power(number):
    if number == 3:
        return 0
    return int(log(number, 3))

优化方案 #

1. 修正浮点精度问题的对数法

直接使用log函数会因为浮点精度误差导致错误，比如当N恰好是3的整数次幂时，log(N,3)的计算结果可能出现偏差，或者刚好等于幂次但不符合“小于N”的要求。正确的逻辑应该结合验证步骤：

import math

def largest_power(number):
    if number <= 1:
        return -1
    # 先基于number-1计算，避免N是3的幂时的问题
    k = int(math.log(number - 1, 3))
    # 双向验证，确保结果准确
    while 3 ** k >= number:
        k -= 1
    while 3 ** (k + 1) < number:
        k += 1
    return k

2. 迭代倍增法（无浮点运算，性能最优）

这种方法完全采用整数运算，彻底避免浮点精度问题，且时间复杂度为O(log₃N)，循环次数极少，哪怕面对极大的N也不会超时：

def largest_power(number):
    if number <= 1:
        return -1
    current_power = 1
    k = 0
    # 快速找到第一个接近number的3的幂
    while current_power * 3 < number:
        current_power *= 3
        k += 1
    # 判断当前幂是否小于number，否则减1
    return k if current_power < number else k - 1

问题根源说明 #

• 立方根遍历法的问题：当N极大时（比如10^100），立方根会是一个极大的数，遍历次数过多直接导致超时。
• 原始对数法的问题：浮点运算的精度误差会导致结果偏离，硬编码单一边界情况无法覆盖所有特殊场景。

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