找到能整除一系列数字的最大 10 次方

Question

我正在尝试缩小一组数字以输入 DP 子集和算法。（如果数字太大，它就会爆炸。） 具体来说，我需要找到可以除以数字而不损失精度的 10 的最大幂。我有一个工作例程，但由于它经常循环运行，我希望有一种比我想出的蛮力方法更快的方法。我的数字恰好是小数。

from decimal import Decimal
import math

def largest_common_power_of_10(numbers: list[Decimal]) -> int:
    """
    Determine the largest power of 10 in list of numbers that will divide into all numbers
    without losing a significant digit left of the decimal point
    """
    min_exponent = float('inf')
    for num in numbers:
        if num != 0:
            # Count the number of trailing zeros in the number
            exponent = 0
            while num % 10 == 0:
                num //= 10
                exponent += 1
            min_exponent = min(min_exponent, exponent)

    # The largest power of 10 is 10 raised to the 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
# Later processing can use scaled_list
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)

Answer 1

您可以使用math.gcd获取给定数字的最大公约数，然后使用decimal.Decimal.normalize将 GCD 与指数对齐，该指数的有效数字右侧不会留下零。该指数就是您要查找的 10 的幂：

\n

import math\nfrom decimal import Decimal\n\ndef largest_common_power_of_10(numbers):\n    return Decimal(math.gcd(*numbers)).normalize().as_tuple().exponent\n

\n

以便：

\n

print(largest_common_power_of_10([1234, 5000, 200]))\nprint(largest_common_power_of_10([470_363_000, 143_539_000, 1_200_000]))\nprint(largest_common_power_of_10([11_230_000, 1_540_000, 44_500_000]))\n

\n

输出：

\n

0\n3\n4\n

\n

演示： https: //ideone.com/OBvYR2

\n

基准测试（借自@KellyBundy的测试代码）：

\n

  0.11 \xc2\xb1 0.01 ms  blhsing\n  0.15 \xc2\xb1 0.00 ms  JesseSealand\n 85.91 \xc2\xb1 0.50 ms  MikeP\n

\n