与えられた小数に近い整数比を生成するジェネレータ

（はじめに、注）

この記事は 2010 年 4 月 5 日に自分のブログに書いていた記事を拾ってきて転載したものであります。
元記事

---

まずは

ある浮動小数点数が与えられたときに、それを簡単な整数比で表せないか、できるだけ簡単な整数比で表したいのだが ... 。という問題を解決するためのジェネレータを作ってみた。小数部分だけ整数比で表せれば整数部は簡単に求まるので、0 以上 1 未満の小数が与えられたときに、1/1 から試してだんだん誤差が小さくなる数列を生成するようにしてみた。効率はおそろしくよくない。

rasi.py

def rasi(target):
    a, b = 1, 1
    min_error = -1
    while True:
        ratio = float(b) / a
        diff = target - ratio
        error = abs(diff)
        if min_error < 0 or min_error > error:
            min_error = error
            yield (b, a, ratio, error)
            if error == 0:
                return
        if diff > 0:
            b += 1
        else:
            a += 1

たとえば 0.315 で実行すると次のようになる。

>>> import rasi
>>> for i in rasi.rasi(0.315): print "%d/%d = %g : %g" % i
... 
1/1 = 1 : 0.685
1/2 = 0.5 : 0.185
1/3 = 0.333333 : 0.0183333
3/10 = 0.3 : 0.015
4/13 = 0.307692 : 0.00730769
5/16 = 0.3125 : 0.0025
6/19 = 0.315789 : 0.000789474
11/35 = 0.314286 : 0.000714286
17/54 = 0.314815 : 0.000185185
23/73 = 0.315068 : 6.84932e-05
40/127 = 0.314961 : 3.93701e-05
63/200 = 0.315 : 0

1/1 のときは誤差 0.685、次の近似は 1/2 で誤差 0.185、... となって 63/200 で誤差 0 になる。この辺は Python よくできてるなあ。

追記

min_error は 1 で初期化すれば変な条件式を追加しなくてよかったな ...。

追記 2010-04-06

πでもやってみましょう。

>>> for i in rasi.rasi(math.pi): print "%d/%d = %g : %g" % i
... 
1/1 = 1 : 2.14159
2/1 = 2 : 1.14159
3/1 = 3 : 0.141593
13/4 = 3.25 : 0.108407
16/5 = 3.2 : 0.0584073
19/6 = 3.16667 : 0.025074
22/7 = 3.14286 : 0.00126449
179/57 = 3.14035 : 0.00124178
201/64 = 3.14062 : 0.000967654
223/71 = 3.14085 : 0.000747583
245/78 = 3.14103 : 0.000567013
267/85 = 3.14118 : 0.000416183
289/92 = 3.1413 : 0.000288306
311/99 = 3.14141 : 0.000178512
333/106 = 3.14151 : 8.32196e-05
355/113 = 3.14159 : 2.66764e-07
52163/16604 = 3.14159 : 2.66213e-07
...

有名な近似値 355/113 が相当いいものであることがわかる。その次はいきなり 5 桁同士の比だもんね。

って、0 以上 1 未満の数じゃないし。でも動いてるし。