Finding the largest power of 10 that divides evenly into a list of numbers

Question

I'm trying to scale down a set of numbers to feed into a DP subset-sum algorithm. (It blows up if the numbers are too large.) Specifically, I need to find the largest power of 10 I can divide into the numbers without losing precision. I have a working routine but since it will run often in a loop, I'm hoping there's a faster way than the brute force method I came up with. My numbers happen to be Decimals.

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

You can use math.gcd to get the greatest common divisor of the given numbers, and then use decimal.Decimal.normalize to align the GCD with an exponent that would leave no zero on the right of its significant digits. That exponent would be the power of 10 you're looking for:

import math
from decimal import Decimal

def largest_common_power_of_10(numbers):
    return Decimal(math.gcd(*numbers)).normalize().as_tuple().exponent

so that:

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

outputs:

0
3
4

Demo: https://ideone.com/OBvYR2

Benchmark (test code borrowed from @KellyBundy):

  0.11 ± 0.01 ms  blhsing
  0.15 ± 0.00 ms  JesseSealand
 85.91 ± 0.50 ms  MikeP

Answer 2

This can be done all at once with the math library if your list is all integers.

import math

def largest_common_power_of_10(numbers):
    
    # get the greatest power of 10 that divides all numbers in list
    gcd_nums = math.gcd(*numbers)
    gcd = [x for x in range(1, len(str(gcd_nums))) if gcd_nums % math.pow(10, x) == 0]

    if len(gcd) == 0:
        return 0
    else:
        gcp = max(gcd)
        return gcp

Examples:

numbers = [11230000,125,44500000]
largest_common_power_of_10(numbers)
# 0

numbers = [11230000,1540,44500000]
largest_common_power_of_10(numbers)
# 1

numbers = [11230000,1540000,44500000]
largest_common_power_of_10(numbers)
# 4

Note:

This may only work with python 3.9 and greater because math.gcd() starrted accepting lists in that release.