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