Stern–Brocot tree

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

Each node of the star - Brocot tree is defined as, with the next parent node on the left and the next one on the right is ( one of which is the direct ancestor, the other a standing above ). The values ​​of the far left and right of the tree are defined here as follows respectively.

Best approximations

Using a binary search on the star - Brocot tree can be best rational approximations for real numbers find. They are best approximations, in the sense that each rational number, is closer to the desired value, has a larger denominator.

The approximate function in the following Haskell program generates a list of all best approximations to a positive real number, which is given as a function which indicates for each rational number, if it is larger, smaller, or equal to the requested.

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: mid case c of          LT -> h ( mid, hi)          GT -> h ( lo, mid)          EQ - > []          where mid = mediant interval The generated list is finite, if the requested number is rational.

• Number Theory