尋找一種不同的divmod函數

Question

Python的divmod函數可以正常工作，而且幾乎是我想要的。但是，對於需要執行的操作，其非整數數字的行爲需要略有不同。運行以下代碼時，您可能會看到它正在嘗試完成的工作。

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

如何function以上這樣來定義最終表達式求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表示形式。

維基百科描述了一種由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的擴張是第一位非貪​​婪，但在最後一位貪婪。

Answer 2

認識到浮點算術根據定義是不精確的。像pi*pi這樣的操作不能保證等於數學常數π^2（因爲math.pi只與「可用精度」一樣精確 - 也就是說它也不是正確的值）。因此實際上不可能對浮點數進行操作，將它們視爲實數。

一般的解決方案是檢查一些ε值的距離，但這有明顯的侷限性。你會更好地重新檢查你的基本需求（爲什麼你需要實數精度？）並嘗試從不同的方向解決問題。

對於你描述的例子，你爲什麼需要實際使用π值？你能否把π的實際計算直到最後，並只對係數進行操作？

例如，存儲列表[3, 2, 1, 3, 2, 1]直接，並與他們係數隱性契約做你的操作和轉換，然後定義是這樣的：

toFloat(ls,mult): 
    pow = 0 
    ret = 0 
    for coef in ls: 
    ret += coef * mult**pow 
    pow += 1 
    return ret 

印刷前的最後一步。更好的是，你可以把這種行爲包裝在課堂上（我願意打賭別人之前做過這個），並且讓__str__()做toFloat()的行爲，以便顯示你的對象給你提供最精確的值。

Answer 3

這一個很簡單，似乎比OP更好。我認爲，在結果的缺陷是精度有關：

import math 
import struct 
import os 
from decimal import Decimal, getcontext 

getcontext().prec = 1000 

def digits_base_b(n, b): 
    n = Decimal(n) 
    b = Decimal(b) 
    digits = {} 
    while n >= b: 
     exp = int(math.log(n, b)) 
     digit = int(n/b**exp) 
     digits[exp] = digit 
     n -= digit*b**exp 
    return digits, n # n is less than b**1, idk how you want to handle those 

def digits_2_str(digits, base): 
    exps = sorted(digits, reverse=True) 
    result = [] 
    format_spec = '%d*'+base+'^%d' 
    for exp in exps: 
     result.append(format_spec % (digits[exp], exp)) 
    return ' + '.join(result) 

pi = Decimal(
'3.14159265358979323846264338327950288419716939937510' 
'58209749445923078164062862089986280348253421170679' 
'82148086513282306647093844609550582231725359408128' 
'48111745028410270193852110555964462294895493038196' 
'44288109756659334461284756482337867831652712019091' 
'45648566923460348610454326648213393607260249141273' 
'72458700660631558817488152092096282925409171536436' 
'78925903600113305305488204665213841469519415116094' 
'33057270365759591953092186117381932611793105118548' 
'07446237996274956735188575272489122793818301194912' 
'98336733624406566430860213949463952247371907021798' 
'60943702770539217176293176752384674818467669405132' 
'00056812714526356082778577134275778960917363717872' 
'14684409012249534301465495853710507922796892589235' 
'42019956112129021960864034418159813629774771309960' 
'51870721134999999837297804995105973173281609631859' 
'50244594553469083026425223082533446850352619311881' 
'71010003137838752886587533208381420617177669147303' 
'59825349042875546873115956286388235378759375195778' 
'18577805321712268066130019278766111959092164201989' 
) 

if __name__ == '__main__': 
    random_float = lambda: struct.unpack('d', os.urandom(8))[0] 
    x = random_float() 
    while x < pi: # some floats are no good, i've only tested with positives 
     x = random_float() 

    digits, leftover = digits_base_b(x, pi) 
    print x, '=' 
    print digits_2_str(digits, u'\u03C0') 

    for i in range(20): 
     digits, leftover = digits_base_b(pi**i, pi) 
     print float(pi**i), '=', digits_2_str(digits, u'\u03C0'), '+', float(leftover) 

UPDATE 我丕了互聯網的第一個千個位數，並使用了和decimal.Decimal並得到了幾個錯誤更少，但有仍然是一對夫婦。因此，我相信差異與精度有關。而且，隨着精度的提高，計算所花費的時間也會大大增加。