Star Brocot Tree

The first stages of construction of the Star Brocot tree

The Stern-Brocot tree is an arrangement of all positive rational numbers in the form of a binary tree . It is based on the Stern-Brocot series and was discovered independently by the German mathematician Moritz Stern in 1858 and by the French watchmaker Achille Brocot in 1860 .

Each node of the Star Brocot tree is defined as having the next parent node on the left and the next on the right (one is the direct ancestor and the other is higher). The values on the far left and right of the tree are defined as and respectively . ${\ displaystyle {\ tfrac {m + m ^ {\ prime}} {n + n ^ {\ prime}}}}$ ${\ displaystyle {\ tfrac {m} {n}}}$ ${\ displaystyle {\ tfrac {m ^ {\ prime}} {n ^ {\ prime}}}}$ ${\ displaystyle {\ tfrac {0} {1}}}$ ${\ displaystyle {\ tfrac {1} {0}}}$

Best approximations

With the help of a binary search on the star Brocot tree, the best rational approximations for real numbers can be found. They are best approximations in the sense that any rational number that is closer to the value you are looking for has a larger denominator.

The function approximatein the following Haskell program generates the list of all best approximations for a positive real number, which is given as a function that indicates for each rational number whether it is greater, less or equal to the one sought.

type Ratio = (Integer, Integer)

type Interval = (Ratio, Ratio)

mediant :: Interval -> Ratio
mediant ((m, n), (m', n')) = (m+m', n+n')

approximate :: (Ratio -> Ordering) -> [Ratio]
approximate c = h ((0,1),(1,0)) where
    h interval@(lo, hi) = mid : case c mid of
        LT -> h (mid, hi)
        GT -> h (lo, mid)
        EQ -> []
        where mid = mediant interval

The generated list is finite if the number sought is rational.