FractionTree

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:

  1. m/n < (m + m′)/(n + n′) < m′/n′

  2. m’n - mn’ = 1

Installing

gem install fraction-tree

Authors

Jose Hales-Garcia

License

This project is licensed under the [MIT] License.

Acknowledgments