Exact arithmetic on the Stern-Brocot tree

In this paper we present the Stern-Brocot tree as a basis for performing exact arithmetic on rational numbers. There exists an elegant binary representation for positive rational numbers based on this tree [Graham et al., Concrete Mathematics, 1994]. We will study this representation by investigating various algorithms to perform exact rational arithmetic using an adaptation of the homographic and the quadratic algorithms that were first proposed by Gosper for computing with continued fractions. We will show generalisations of homographic and quadratic algorithms to multilinear forms in n variables. Finally, we show an application of the algorithms for evaluating polynomials. (C) 2006 Elsevier B.V. All rights reserved.