Меня интересует эффективная реализация на Python так называемой «функции чередования» f, которая принимает два числа a, b в (0,1) и чередует их десятичные цифры, т.е.
f(a,b) := 0.a1 b1 a2 b2 a3 b3 ... где a = 0.a1 a2 a3... и b = 0.b1 b2 b3... — десятичные представления a, b.
С математической точки зрения функция f представляет собой однозначное отображение из (0,1)x(0,1) в (0,1).
Можете ли вы предложить, как эффективно реализовать эту карту в Python, чтобы она оставалась взаимно однозначной?
Для эффективной реализации необходимо добиться двух вещей: минимальной асимптотической сложности с точки зрения большой нотации O и эффективные вычислительные операторы, позволяющие избежать повторных или иных ненужных вычислений.
Учитывая проблему, маловероятно, что ее можно решить с помощью алгоритма, менее чем линейного по длине входных чисел. С точки зрения операторов, учитывая, что мы работаем с десятичным форматированием, было бы трудно извлечь выгоду из некоторых побитовых (двоичных) вычислений. Таким образом, мы, вероятно, лучше всего справляемся с общими математическими операциями.
Первая наивная реализация попытается выполнить функцию для чисел с плавающей запятой:
def interleave_float(a: float, b: float) -> float:
a_rest = a
b_rest = b
result = 0
dst_pos = 1.0 # position of written digit
while a_rest != 0 or b_rest != 0:
dst_pos /= 10 # move decimal point of write
a_rest *= 10 # move decimal point of read
result += a_rest // 1 * dst_pos
a_rest %= 1 # remove current digit
dst_pos /= 10
b_rest *= 10
result += dst_pos * (b_rest // 1)
b_rest %= 1
return result
Однако простой тест выявил проблему — присущая ограниченная точность вычислений с плавающей запятой что искажает уже на 16-17 разряде после запятой:
>>> a = 0.987654321
>>> b = 0.1234567890123456789
>>> print(a)
0.987654321
>>> print(f"{b:.20}") # formatted to show higher precision
0.12345678901234567737
>>> print(f"Float: {interleave_float(a, b):.50}")
Float: 0.91827364554637280757987127799424342811107635498047
Распространенным способом решения проблемы точности является использование decimal.Decimal, реализация на python десятичной арифметики с фиксированной запятой:
from decimal import Decimal, getcontext
getcontext().prec = 50 # increase number precision
def interleave_fixed(a: Decimal, b: Decimal) -> Decimal:
a_rest = a
b_rest = b
result = 0
dst_pos = Decimal(1)
while a_rest != 0 or b_rest != 0:
dst_pos *= Decimal(0.1)
a_rest *= 10 # move decimal point
result += a_rest // 1 * dst_pos
a_rest %= 1 # remove current digit
dst_pos *= Decimal(0.1)
b_rest *= 10
result += dst_pos * (b_rest // 1)
b_rest %= 1
return result
Кажется, это работает лучше для b, но, к сожалению, это также приводит к неточности примерно той же цифры в результате. Об этой неточности также сигнализирует флаг Inexact в контексте после вычисления:
>>> print(getcontext())
Context(prec=50, rounding=ROUND_HALF_EVEN, Emin=-999999, Emax=999999, capitals=1, clamp=0, flags=[], traps=[InvalidOperation, DivisionByZero, Overflow])
>>> a = Decimal(".987654321")
>>> b = Decimal(".1234567890123456789")
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"Fixed: {interleave_fixed(a, b)}")
Fixed: 0.91827364554637287146771953200668367263491993253785
>>> print(getcontext())
Context(prec=50, rounding=ROUND_HALF_EVEN, Emin=-999999, Emax=999999, capitals=1, clamp=0, flags=[Inexact, FloatOperation, Rounded], traps=[InvalidOperation, DivisionByZero, Overflow])
Другой подход, который не должен накладывать ограничений из-за точности (и который вы придумали сами), заключается в выполнении синтаксической обработки строк:
def interleave_str(a: str, b: str) -> str:
result = "0."
src_pos = 2 # position of read digit
while len(a) > src_pos or len(b) > src_pos:
result += a[src_pos] if len(a) > src_pos else "0"
result += b[src_pos] if len(b) > src_pos else "0"
src_pos += 1
return result[:-1] if result.endswith("0") else result
Алгоритм не выполняет проверку, поэтому вам остается решить, что вы можете добавить. Тем не менее, тестирование дает желаемую точность:
>>> a = "0.987654321"
>>> b = "0.1234567890123456789"
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"String: {interleave_str(a, b)}")
String: 0.91827364554637281900010203040506070809
...но что можно сделать с полученной строкой? Может быть, снова преобразовать его в десятичное число? Зависит от того, как вы хотите использовать результат.
