緩募: 代数的実数A,Bの間に含まれる最も単純な有理数を求めるアルゴリズム。ただし、A,Bを上下から任意精度で近似する有理数は計算可能とする。また、単純さ...

Shiro Kawai - 2013-10-04T14:34:39+0000

Gaucheでは上限と下限を連分数展開して間を探すということをしていますが、そういう感じでしょうか。

http://blog.practical-scheme.net/gauche/20120925-rationalize

実際の実装ではOpen rangeも考慮してこんなふうになっています (real->rationalの部分)

https://github.com/shirok/Gauche/blob/master/lib/gauche/numerical.scm

Masahiro Sakai - 2013-10-04T16:34:45+0000

rationalizeはapproxRationalと同じ機能ですね。approxRationalのコードは、上下限が有理数にで表現できる場合しか扱っていなかったのですが、連分数展開する方法は上下限が有理数で表現できない場合でもいけそうでしょうか？

Shiro Kawai - 2013-10-04T18:28:17+0000

A < Bとして、A, Bそれぞれのn項までの連分数近似をRA_n, RB_n とすると、 A < RA_n < RB_n < B となってる時、 [A, RA_n) の範囲内にはRA_n より単純な有理数はなく、 (RB_n, B] 内にRB_nより単純な有理数はない、ということが言えませんかね。それが言えればわりとストレートに連分数挟み撃ちでいけそうな。

Masahiro Sakai - 2013-10-05T02:24:31+0000

http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_within_an_interval によると、それでいけそうです。

Masahiro Sakai - 2013-10-05T02:33:49+0000

それと、Twitterの方で +Yusuke Endoh さんから、Stern-Brocot tree でいけるとのことでした。 https://twitter.com/masahiro_sakai/status/385981418507366400

Shiro Kawai - 2013-10-05T03:47:09+0000 - 更新日時: 2013-10-05T03:48:02+0000

Stern-Brocot treeだと収束が極端に遅くなる場合があるのですが (最初に示したblog参照)、その回避方法があるのでしょうか。(上のtwitter見た限りではナイーブな実装しか見つけられなかったので)

Shiro Kawai - 2013-10-05T03:51:05+0000

あ、待てよ、今回はrationalizeのように誤差範囲を別に指定するわけじゃないから大丈夫なのかな?

Shiro Kawai - 2013-10-05T04:00:41+0000

いや、やはり、例えばAとBが1.1e-20と1.2e-20とかだったら大変ですね。

Masahiro Sakai - 2013-10-06T02:33:29+0000

なるほど。
連分数展開でもいけそうですし、まずは連分数展開で実装してみようかと思います。

Masahiro Sakai - 2013-10-12T00:24:46+0000

とりあえず、こんな感じで実装してみました。
https://github.com/msakai/data-interval/commit/8760d67570b6c0434a40bd8fbf4dfc5a943f5184#diff-674786031b416986a693b0ad3dd9ace5

Data.Ratio