A collection of Stern-Brocot based models and methods.
The Stern-Brocot algorithm describes a way of constructing sets of non-negative fractions arranged in a binary tree.
Construction of a SB tree starts by using the fractions 0/1 and 1/0, where 1/0 denotes infinity. Subsequent fractions are derived by the algorithm, (m + m′)/(n + n′), where m/n is the left adjacent fraction and m′/n′ is the right adjacent fraction, and m/n < m′/n′. This sum is called the mediant.
Given m/n = 0/1 and m′/n′ = 1/0, the first mediant sum, is:
0/1 + 1/0 => (0 + 1)/(1 + 0) = 1/1
Fractions constructed in this way, have the following properties:
- m/n < (m + m′)/(n + n′) < m′/n′
- m'n - mn' = 1
gem install fraction-tree
This project is licensed under the [MIT] License.
- Concrete Mathematics, chapter 4.5 Ronald Graham, Donald Knuth & Oren Patashnik
- Introductory reading on the Stern-Brocot tree
- Trees, Teeth, and Time: The mathematics of clock making
- Continued Fractions on the Stern-Brocot Tree
- The Stern-Brocot tree and Farey sequences
- The Wilson zig-zag (quotient sum) algorithm explained
- Erv Wilson's application of the tree to scales