与えられた分母の範囲に対してPiの最も近い近似を見つける

Question

可能な分母の包括的な範囲（dmin、dmaxを含む）からPiに最も近い共通分数n/dを見つけるアルゴリズム（好ましくはGoまたはC）を探しています。 1 < = dmin < = dmax < = 1e15）。 Piと同じ距離の共通分数が複数ある場合は、分母が最小のものを探したい。

Note：ブルートフォースアプローチは十分に効率的ではないため、よりスマートで効率的なソリューションを探しています。

例：dminのために = 1とDMAX = 10に最も近い共通の割合は約0.001

最初に考えたのパイまでの距離に7分の22です：ファレイ数列を見ると、我々は見つけることができますdmaxまでのすべての分母の最も近い近似。残念なことに、その結​​果はdminの制約を満たしません。

Answer 1

私は完全な答えを得る時間がありませんが、ここには部分的な答えがあります。このテクニックは継続的な分数の概念を使用しています。あなたの値dminは無視されますが、これは以下では使用されません。

continued fraction expansion of piは、必要なだけ多くの場所に入手してください。 DMAX < = 1E15のごバウンドのためには、

[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上記の分母を持つパイのためのconvergentsを見つけるために、短いループを使用している唯一の最初の28個の数字を、必要とします。 Pythonでは分数numlo/denomloを使用しますが、それよりも良い近似があるかもしれません、Microsoft Excelなどの

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 

一部のソフトウェア、あろうこと。 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つのステップが必要です。より多くの記憶装置を使用し、計算を少なくする別の可能性は、すべての中間部分を記憶することであろう。そのストレージは、少なくとも300の何百に入るだろう。 piの継続的な分数展開のために格納されたリストが気に入らなければ、piの値を使ってその値を計算することができますが、double precision（Cで）を使用すると、私が示した28の数字だけになります。

さらなる研究のために、分画および中間画分を検索してください。