python - 寻找不同类型的 divmod 函数

Question

Python 的divmod 函数运行正常，几乎就是我想要的。但是，对于需要执行的操作，它对非整数的行为需要略有不同。运行以下代码时，您可能会看到它正在尝试完成什么。

>>> function = divmod
>>> from math import pi
>>> function(pi * pi, pi) == (pi, 0)
False
>>> 

如何在上面定义函数，使最终表达式的计算结果为True，而不是False？如果任何人都可以弄清楚如何获得 (pi, 0) 而不是 (3.0, 0.4448...)，这就是答案。

编辑 1:现在来看一个更复杂的示例，以下代码应生成 [3, 2, 1, 3, 2, 1]。

>>> x = 1 * pi ** 5 + \
        2 * pi ** 4 + \
        3 * pi ** 3 + \
        1 * pi ** 2 + \
        2 * pi ** 1 + \
        3 * pi ** 0
>>> digits = []
>>> while x:
        x, y = function(x, pi)
        digits.append(y)


>>> digits
[0.3989191524449005, 0.2212554774328268, 2.309739581793931, 0.1504440784612413,
2.858407346410207, 1.0]
>>> 

编辑 2: 下面显示的代码工作正常，只是它有意外但有效的输出。

import math

def convert_dec_to_pi(number):
    digits = get_pi_digits(number)
    digits, remainder = correct_pi_digits(digits)
    return make_pi_string(digits, remainder)

def get_pi_digits(number):
    digits = []
    while number:
        number, digit = divmod(number, math.pi)
        digits.append(digit)
    digits.reverse()
    return digits

def correct_pi_digits(digits):
    last = len(digits) - 1
    for index, digit in enumerate(digits):
        if index < last and digit % 1 != 0:
            a, b = get_digit_options(digit, digits[index + 1])
            digits[index:index+2] = a if 0 <= a[1] < math.pi else b
    digit, remainder = divmod(digits[-1], 1)
    digits[-1] = digit
    return digits, remainder

def get_digit_options(digit, next_digit):
    a, b = math.floor(digit), math.ceil(digit)
    if a not in range(4):
        return (b, (digit - b) * math.pi + next_digit), None
    if b not in range(4):
        return (a, (digit - a) * math.pi + next_digit), None
    c, d = ((a, (digit - a) * math.pi + next_digit),
            (b, (digit - b) * math.pi + next_digit))
    return (c, d) if digit - a < 0.5 else (d, c)

def make_pi_string(digits, remainder):
    return '{} base \u03C0 + {} base 10'.format(
        ''.join(str(int(d)) for d in digits), remainder)

下面的函数可以用来反转操作和检查结果。

import re

def convert_pi_to_dec(string):
    match = re.search('^(\\d+) base \u03C0 \\+ (0\\.\\d+) base 10$', string)
    if not match:
        raise ValueError()
    digits, remainder = match.groups()
    return sum(int(x) * math.pi ** y for y, x in enumerate(reversed(digits))) \
           + float(remainder)

以下代码不会引发AssertionError，因此很明显一切正常。

for n in range(1, 36):
    value = convert_dec_to_pi(n)
    print(value)
    assert convert_pi_to_dec(value) == n

那么这让我想到了下面的例子。输出可以毫无问题地转换回来，但人们会期望一些稍微不同的东西。

>>> convert_dec_to_pi(math.pi * math.pi)
'30 base π + 0.44482644031997864 base 10'
>>> convert_pi_to_dec(_) == math.pi * math.pi
True
>>> 

字符串应该是 100 base π + 0.0 base 10。此时输出是准确的，但不“正确”。

编辑 3: 下面的例子可能会提供一些额外的洞察力来了解我所追求的。在以不同的 π 次幂运行循环后，我希望所有输出的形式都是 10...base π + 0.0 base 10。结果与此不同，如下所示。

>>> for power in range(20):
    print(convert_dec_to_pi(math.pi ** power))


1 base π + 0.0 base 10
10 base π + 0.0 base 10
30 base π + 0.44482644031997864 base 10
231 base π + 0.8422899173517213 base 10
2312 base π + 0.6461318165449161 base 10
23122 base π + 0.029882968108176033 base 10
231220 base π + 0.0938801130760924 base 10
2312130 base π + 0.7397595138779653 base 10
23121302 base π + 0.3240230542211062 base 10
231213021 base π + 0.017948446735832846 base 10
2312130210 base π + 0.05638670840988885 base 10
23121302100 base π + 0.17714406890720072 base 10
231213021000 base π + 0.5565145054551264 base 10
2312130133130 base π + 0.6366321966964654 base 10
23121301331302 base π + 3.9032618162071486e-05 base 10
231213013313020 base π + 0.00012262302157861615 base 10
2312130133123211 base π + 0.24905356925301847 base 10
23121301331232110 base π + 0.7824248909895828 base 10
231213013312321102 base π + 0.4580601707952492 base 10
2312130133123211021 base π + 0.4390387422112354 base 10
>>> convert_pi_to_dec('2312130133123211021 base π + 0.4390387422112354 base 10')
2791563949.5978436
>>> convert_pi_to_dec('10000000000000000000 base π + 0.0 base 10')
2791563949.5978436
>>> 

还显示了最后两个字符串是如何等效的，但输出应该是第二个字符串的形式。我发现 10000000000000000000 base π 和 2312130133123211021 base π 之间的差异是 0.4390387422112354 base 10，但这种差异对表示。输出应该如下所示。

1 base π + 0.0 base 10
10 base π + 0.0 base 10
100 base π + 0.0 base 10
1000 base π + 0.0 base 10
10000 base π + 0.0 base 10
100000 base π + 0.0 base 10
1000000 base π + 0.0 base 10
10000000 base π + 0.0 base 10
100000000 base π + 0.0 base 10
1000000000 base π + 0.0 base 10
10000000000 base π + 0.0 base 10
100000000000 base π + 0.0 base 10
1000000000000 base π + 0.0 base 10
10000000000000 base π + 0.0 base 10
100000000000000 base π + 0.0 base 10
1000000000000000 base π + 0.0 base 10
10000000000000000 base π + 0.0 base 10
100000000000000000 base π + 0.0 base 10
1000000000000000000 base π + 0.0 base 10
10000000000000000000 base π + 0.0 base 10

有没有我遗漏的东西，有没有解决这个问题的方法，或者这应该被认为是徒劳的？

Answer 1

您正在寻找一种算法来确定 non-integer base float 的表示。

维基百科描述了一种由 Rényi 和 Frougny 提出的贪心算法；这是对实现的尝试:

from math import log, floor
def expansion(x, b):
    k = int(floor(log(x) / log(b)))
    d, r = divmod(x / float(b ** k), 1)
    digits = [int(d)]
    for _ in range(k):
        d, r = divmod(b * r, 1)
        digits.append(int(d))
    def rest(b, d, r):
        while r:
            d, r = divmod(b * r, 1)
            yield int(d)
    return digits, rest(b, d, r)

这给出了字典序的初始扩展；你可以通过一些小摆弄来获得按字典顺序排列的终端扩展:

def expansion(x, b, greedy=True):
    if not greedy:
        m = (floor(b) / (b - 1)) - 1
    k = int(floor(log(x) / log(b)))
    d, r = divmod(x / float(b ** k), 1)
    if not greedy and r < m:
        d, r = d - 1, r + 1
    digits = [int(d)]
    for _ in range(k):
        d, r = divmod(b * r, 1)
        if not greedy and r < m:
            d, r = d - 1, r + 1
        digits.append(int(d))
    def rest(d, r):
        while r:
            d, r = divmod(b * r, 1)
            if not greedy and r < m:
                d, r = d - 1, r + 1
            yield int(d)
    return digits, rest(d, r)

不幸的是，这仍然无法正常工作，因为 OP 的扩展在第一位是非贪婪的，但在最后一位是贪婪的。