在給定的分母範圍內找到Pi的最接近的近似值

我正在尋找一種算法（最好在Go或C中）以找到Pi的最接近的共同部分n/d，其中包含範圍可能的分母（dmin，dmax與1 < = dmin < = dmax < = 1e15）。如果有多個與Pi具有相同距離的普通分數，我想找到分母最小的分數。在給定的分母範圍內找到Pi的最接近的近似值

注意：暴力方法效率不夠高，因此我正在尋找更智能/更高效的解決方案。

示例：對於DMIN = 1和Dmax = 10的最接近的共同部分是22/7與大約0.001

首先想到到裨的距離：綜觀法裏數列，我們可以找到所有分母最接近dmax的近似值。不幸的是，結果不符合dmin的約束條件。

來源

2017-02-26 Frank Smith

'44/14'對'dmin = 13'和'dmax = 15'是一個可以接受的答案嗎？ –

或者換句話說：是什麼激發了'dmin'約束？如果唯一的原因是要確保近似值「足夠好」，那麼以另一種方式重新說明問題可能會更容易。例如有一個相當簡單的算法，用於在給定的有理區間內找到最簡單的理性，如果該約束實際上是近似值和pi相差至多1/dmin（這是一個稍微不同的約束），則可以很容易地應用該算法。 –

我沒有時間給出完整答案，但這裏是部分答案。這項技術使用連續分數的概念 - 網上有很多關於它們的內容。我會忽略你的價值dmin，這不在下面使用。

獲取continued fraction expansion of pi爲您需要的任意位置。爲了您綁定的DMAX < = 1E15的你只需要第28號，這是

[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13]

使用短環發現有分母略低於和略高於DMAX pi的漸近。在Python這將是

pi_cont_frac = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 
       3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 
       1, 84, 2, 1, 1, 15, 3, 13] 
denomlo, denomhi = 1, 0 
numlo, numhi = 0, 1 
for q in pi_cont_frac: 
    denomlo, denomhi = denomhi, q * denomhi + denomlo 
    numlo, numhi = numhi, q * numhi + numlo 
    if denomhi > dmax: 
     break

一些軟件，如Microsoft Excel，將使用部分numlo/denomlo，但有可能是更好的近似比。現在找到使得denomhi - r * denomlo恰好低於（或等於）dmax的自然數r的值。

然後或者numlo/denomlo或(denomhi - r * denomlo)/(denomhi - r * denomlo)是您希望的pi最接近的分數。只要檢查哪一個更接近。

該算法的階數爲log（dmax），由於pi的屬性，通常要低得多。對於dmax < = 1e15，它需要28個循環，但需要更多的清理聲明。

您可以通過預先計算和存儲收斂值（numhi和denomhi的值）並在dmax之上搜索denomhi的值來製作更快的算法。這也只需要28個數字，但分子和分母都需要這個數字。二進制搜索最多需要5個步驟才能找到它 - 實際上是瞬時的。使用更多存儲和更少計算的另一種可能性是存儲所有中間分數。這個存儲將進入數百個，至少有三百個。如果你不喜歡這個存儲列表來繼續擴展pi的分數，你可以使用pi的值來即時計算，但是使用雙精度（C）會讓你只能看到我給你看的28個數字。

欲瞭解更多的研究，查找連續分數和中間分數。

來源

2017-02-26 20:04:53

由於滿足最小分母約束條件，所以正確答案不一定在pi的連續分數展開式中。 –

沒錯，這就是爲什麼我說我的是「一個部分答案」，而「我會忽略你的價值dmin」。完整的答案需要解決您的問題。 –

在給定的分母範圍內找到Pi的最接近的近似值

回答

相關問題