A note on the computation of the fraction of smallest denominator in between two irreducible fractions
Given two irreducible fractions f f and g g , with f<g f < g , we characterize the fraction h h such that f<h<g f < h < g and the denominator of h h is as small as possible. An output-sensitive algorithm of time complexity O(d) O ( d ) , where d d is the depth of h h is derived from this characterization.
algorithm simplest fraction continued fractions