The Stern-Brocot tree is a binary tree of fractions where each fraction is acquired by adding the numerators and denominators of the two fractions neighbouring it in the levels above.
It is generated by starting with 0/1
and 1/0
as "endpoint fractions", and from there, iterating by placing one fraction between each consecutive pair of fractions by adding the numerators and denominators of those fractions together, like so:
0. 0/1 1/0
1. 0/1 1/1 1/0
2. 0/1 1/2 1/1 2/1 1/0
3. 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
4. 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0
In each iteration of the Stern-Brocot tree (the n
th iteration), there are 2^n + 1
elements in the sequence, to which we can ascribe a fraction from 0/2^n
to 2^n/2^n
. Each new iteration simply inserts one fraction "halfway" between each pair of consecutive fractions.
This makes the Stern-Brocot tree a one-to-one mapping between the positive rational numbers and the binary fractions between 0 and 1, thereby also serving as a proof that the two sets have the same cardinality.
Your task is to write a program or function that, given the numerator and denominator of a positive rational number in lowest terms, determines the binary fraction that corresponds to that fraction's position in the Stern-Brocot tree.
Examples of inputs and outputs are provided below:
2/3 -> 3/8 (4th number in iteration 3)
4/7 -> 9/32 (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2 (middle number in the first iteration)
Inputs you don't need to support, but are included for reference:
0/1 -> 0/1 (0/1 is considered the left number)
1/0 -> 1/1 (1/0 is considered the rightmost number)
The shortest program in any language to achieve this goal wins.
1/1 => 1
,1/2 => 2
,2/1 => 3
,1/3 => 4
, etc.). If the number so generated for a node isn
, then2^lg n
(binary log) is the highest bit set inn
, and the desired binary fraction is(2*(n - 2^lg n) + 1) / 2^(lg n + 1)
. (Anyone attempting an assembler solution in an instruction set with a get-highest-set-bit will probably want to use this approach). \$\endgroup\$