Continued Fractions, Comparison Algorithms, and Fine Structure Constants
Philippe Flajolet, Brigitte Vallée · 2000
. There are known algorithms based on continued fractions for comparing fractions and for determining the sign of 2 \\Theta 2 determinants. The analysis of such extremely simple algorithms leads to an incursion into a surprising variety of domains. We take the reader through a light tour of dynamical systems (symbolic dynamics), number theory (continued fractions), special functions (multiple zeta values), functional analysis (transfer operators), numerical analysis (series acceleration), and complex analysis (the Riemann hypothesis). These domains all eventually contribute to a detailed characterization of the complexity of comparison and sorting algorithms, either on average or in probability. Motivations The topic of this paper is the study of one of the simplest possible algorithms for one of the simplest conceivable tasks---the comparison of two fractions. The algorithm has been proposed in the celebrated "Hackers' Memorandum" known as HAKMEM [4], an amazing bag of tricks for com...