stern-brocot 木

stern-brocot 木
Stern-Brocot 木の「親」の値は数直線の区間です。
頂点の親「根」の値は
０〜∞
左端が０で、右は無限大です。
それを分数で０/１、１/０とそれぞれ表します。
さらにHaskellではタプルで
(0,1) ,(1,0)
と表します。
つまりHaskellでStern-Brocot 木の根はタプルのタプルで
（(0,1) ,(1,0))
と表せます。
親はいつでも自動で左の子、右の子を生成することができます。
Haskellで書くとこのような関数になります。

sb ((x,y),(z,w)) = (a,b)  where  a = ((x,y),c) ; b = (c,(z,w)); c = (z+x,y+w)

aが左の子ｂが右の子です。左の子の右端と右の子の左端は同じです。分割点になります。

main = do
    let a = (0,1)
    let b = (1,0)
    let r = (a,b)
    print r
    print $ sb r

((0,1),(1,0))
(((0,1),(1,1)),((1,1),(1,0)))

数直線の区間
０〜∞
を
０〜１
と
１〜∞
の２つの区間に分割したのと同じです。

もう一世代増やしてみましょう。

main = do
    let a = (0,1)
    let b = (1,0)
    let r = (a,b)
   
    let (a,b) = sb r
    print $ sb a
    print $ sb b

(((0,1),(1,2)),((1,2),(1,1)))
(((1,1),(2,1)),((2,1),(1,0)))

これは
数直線の区間
０〜１
を
０〜０．５
と
０．５〜１
に
１〜∞
を
１〜２
と
２〜∞
に分割したのと同じです。
これを繰り返せば数直線を無限に分割できます。
Stern-Brocot 木の木構造としての性質等は
Spaghetti Source - Stern-Brocot 木
http://www.prefield.com/algorithm/math/stern_brocot_tree.html

を参照してください。
さてStern-Brocot木を２分探索してゆけば全ての少数を分数に変換できるのですが、
そのためにはStern-Brocot木を前もって作成しておく必要はありません。
与えられた少数と分割点とを比較しながら片側の子のみを辿ってゆけばよい。

この辺はコードにしたほうがわかりやすい。

---

	import Data.Ratio
	loop x a = do
	print a
	let (l,r) = sb a
	let (_,(d,e)) = l
	case compare (fromRational (d%e)) x of
	EQ -> return $ d%e
	GT -> loop x l
	LT -> loop x r
	sb((x,y),(z,w))=(a,b)
	where a = ((x,y),c)
	b= (c,(z,w))
	c= (z+x,y+w)
	main = do
	let a = (0,1)
	let b = (1,0)
	let r = (a,b)
	loop pi r >>= print

view raw sb.hs hosted with ❤ by GitHub

---

実行結果

245850922 % 78256779

---