Beynon, Meurig (1981) On Raney's binary encoding for continued fractions, generalisations of Pell's Equation, and the theory of factorisation. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Preview

Text WRAP_Beynon_cs-rr-034.pdf - Published Version Download (15Mb) | Preview

Abstract

Raney's algorithm for computing the continued fraction expansion of (ax+b)/cx+d) from the continued fraction expansion of x was first described in [R]. In that paper, a simple binary encoding for continued fraction expansions is of fundamental importance. In some sense, the study of this encoding - wnich is fully described in $1 below - is the unifying idea underlying this paper. The first five sections of the paper cover essentially the same ground as [R], but adopt a perspective in which the algorithm is the central object of interest. As far as the mathematical results are concerned, any originality is confined to presentation and organisation, and the most novel aspects of these sections are concerned with the formulation and justification of the algorithm and its derivatives. Of particular interest is the use of Dijkstra's guarded command notation [Di], a formalism ideally suited for expressing Raney's algorithm in its non-deterministic form (Algorithm 3.4).

Request changes to a record

Actions (login required)

View Item