寻找可整除Decimal列表的最大10的幂以优化DP子集和算法

我需要缩放一组数字以输入DP子集和算法（数值过大会导致算法崩溃）。具体来说，要找到能整除所有Decimal数字且不损失精度的最大10的幂。我已有可行实现，但因需频繁循环执行，希望找到比暴力法更快的方案。

原实现代码 #

from decimal import Decimal
import math

def largest_common_power_of_10(numbers: list[Decimal]) -> int:
    """
    找出能整除所有数字且不丢失小数点左侧有效数字的最大10的幂的指数
    """
    min_exponent = float('inf')
    for num in numbers:
        if num != 0:
            # 统计数字末尾的零的个数
            exponent = 0
            while num % 10 == 0:
                num //= 10
                exponent += 1
            min_exponent = min(min_exponent, exponent)

    # 最大的10的幂是10的min_exponent次方
    return int(min_exponent)


decimal_numbers = [Decimal("1234"), Decimal("5000"), Decimal("200")]
result = largest_common_power_of_10(decimal_numbers)
assert(result == 0)
decimal_numbers = [Decimal(470_363_000.0000), Decimal(143_539_000.0000), Decimal(1_200_000.0000)]
result = largest_common_power_of_10(decimal_numbers)
assert(result == 3)
divisor = 10**result
# 后续处理可使用缩放后的列表
scaled_list = [x/divisor for x in decimal_numbers]
assert(scaled_list == [Decimal('470363'), Decimal('143539'), Decimal('1200')])
reconstituted_list = [x * divisor for x in scaled_list]
assert(reconstituted_list == decimal_numbers)

优化方案 #

原方法通过循环除以10统计末尾零的个数，对于末尾零较多的数字，循环次数会很高，影响频繁调用时的性能。以下两种方案可以大幅提升效率：

方案1：利用字符串统计末尾零 #

直接将Decimal转换为字符串（自动忽略末尾的零值小数部分），然后统计字符串末尾连续零的数量：

from decimal import Decimal

def largest_common_power_of_10(numbers: list[Decimal]) -> int:
    min_exponent = float('inf')
    for num in numbers:
        if num != 0:
            # 转换为字符串，去除可能的小数部分（如".0000"）
            s = num.to_integral_value().to_eng_string()
            # 统计末尾零的个数
            exponent = len(s) - len(s.rstrip('0'))
            min_exponent = min(min_exponent, exponent)
    return min_exponent if min_exponent != float('inf') else 0

方案2：质因数分解统计2和5的最小指数 #

10的幂由质因数2和5的乘积构成，每个数能被10^k整除的最大k等于该数中2的因子个数和5的因子个数的较小值。我们只需统计每个数的这两个值，再取所有数的最小值即可：

from decimal import Decimal

def count_factor(n: int, factor: int) -> int:
    count = 0
    while n % factor == 0 and n != 0:
        count +=1
        n = n // factor
    return count

def largest_common_power_of_10(numbers: list[Decimal]) -> int:
    min_exponent = float('inf')
    for num in numbers:
        if num != 0:
            # 转换为整数（假设输入均为整数型Decimal）
            n = int(num.to_integral_value())
            count_2 = (n & -n).bit_length() -1 if n !=0 else 0
            count_5 = count_factor(n,5)
            current_k = min(count_2, count_5)
            min_exponent = min(min_exponent, current_k)
    return min_exponent if min_exponent != float('inf') else 0

这两种方案都避免了循环除以10的操作，字符串方案实现简单，质因数分解方案在处理极大数字时性能更优。

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