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

HTML 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 or add full text files to a record

Actions (login required)

View Item