在 Python 中交错两位小数
Interleaving two decimal digits in Python
我对所谓的 'interleaving function' f 的高效 Python 实现很感兴趣,它采用 (0,1) 中的两个数字 a、b 并交错其十进制数字,即
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 中有效地实现此映射以保持它是一对一的?
为了实现高效的实施,需要确保实现两件事:big O notation 方面的最小渐近复杂度和高效的计算运算符,避免重复或不必要的计算。
考虑到这个问题,不太可能使用输入数字长度小于线性的算法来解决它。在运算符方面,鉴于我们使用十进制格式,我们很难从某些 bit-wise(二进制)计算中获益。因此,我们可能最擅长一般数学运算。
使用浮动
第一个天真的实现会尝试在浮点数上执行函数:
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
然而,一个简单的测试显示了一个问题 - inherently limited precision of floating point arithmetic 已经在浮点数后的第 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, the python implementation of fixed-point decimal arithmetic:
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
删除尾随 0(如果存在)
该算法不进行验证,因此您可以自行决定要添加的内容。然而,对此进行测试可提供所需的精度:
>>> a = "0.987654321"
>>> b = "0.1234567890123456789"
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"String: {interleave_str(a, b)}")
String: 0.91827364554637281900010203040506070809
...但是可以用结果字符串做什么呢?也许再次将其转换为小数?取决于你想如何使用结果。
我对所谓的 'interleaving function' f 的高效 Python 实现很感兴趣,它采用 (0,1) 中的两个数字 a、b 并交错其十进制数字,即
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 中有效地实现此映射以保持它是一对一的?
为了实现高效的实施,需要确保实现两件事:big O notation 方面的最小渐近复杂度和高效的计算运算符,避免重复或不必要的计算。
考虑到这个问题,不太可能使用输入数字长度小于线性的算法来解决它。在运算符方面,鉴于我们使用十进制格式,我们很难从某些 bit-wise(二进制)计算中获益。因此,我们可能最擅长一般数学运算。
使用浮动
第一个天真的实现会尝试在浮点数上执行函数:
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
然而,一个简单的测试显示了一个问题 - inherently limited precision of floating point arithmetic 已经在浮点数后的第 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, the python implementation of fixed-point decimal arithmetic:
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
删除尾随 0(如果存在)
该算法不进行验证,因此您可以自行决定要添加的内容。然而,对此进行测试可提供所需的精度:
>>> a = "0.987654321"
>>> b = "0.1234567890123456789"
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"String: {interleave_str(a, b)}")
String: 0.91827364554637281900010203040506070809
...但是可以用结果字符串做什么呢?也许再次将其转换为小数?取决于你想如何使用结果。