[Math] Applications of finite continued fractions

applicationsbig-listcontinued-fractionsnt.number-theoryreference-request

I know some applications of finite continued fractions. Probably you know more. Can you add anything? (For Applications of periodic continued fractions I have made a special topic.)

1) (Trivial) Analysis of Euclidean algorithm (and its variants). This item includes extended Euclidean algorithm, calculation of $a^{-1}\pmod n$, lattice reduction, number recognition (Andreas Blass), parametrization of solution of the equation $ad-bc=N$, calculation of convex hull of non-zero lattice points from first quadrant etc.

2) Decomposition of prime $p=4n+1$ to the sum of two squares.

3) Rodseth's formula for Frobenius numbers with three arguments.

4) Analysis of Frieze Patterns from The Book of Numbers (Conway, J. H. and Guy, R. K.)

5) Calculation of goodness (dicrepancy or something similar) of 2-dimesional lattice rules for numerical integration.

6) Singularitie resolution in toric surfaces (added by J.C. Ottem).

7) Classification of rational tangles (added by Paolo Aceto).

8) Calculation of Dedekind sums.

9) Calculation of the number of A-graded algebras (V.I. Arnold A-graded algebras and continued fractions)

10) Asymptotic behavior of a curve in $\mathbb{R}^n$ with constant curvature $k_1$, constant second curvature $k_2$, … (till constant curvature $k_{n-1}$). (V.I. Arnold)

11) The way to attack (discovered by Michael J. Wiener) RSA public key crypto system with small private exponents (added by jp).

12) DDA-algorithm for converting a segment into a nice-looking sequence of pixels. Another algorithms of integer linear programming: finding a “closest points” in a given halfplane (added by Wilberd van der Kallen).

13) Analysis of Lehmer pseudo-random number generator (added by Gerry Myerson). See U. Dieter. Pseudo-random numbers. The exact distribution of pairs and Knuth D. E. The art of computer programming. Volume 2 (Theorem D, section 3.3.3).

14) Bach and Shallit show how to compute the Jacobi symbol in terms of the simple continued fraction (Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, pp. 343-344, 1996.)

15) A criterion for a rectangle to be tilable by rectangles of a similar shape. Construction of alternating-current circuits with given properties (added by M. Skopenkov).

16) Slam dunking of rational surgery diagrams for a three-manifolds (added by Kelly Davis).

17) CF allows to predict digets in $1/M$ random number generator, see Blum, L.; Blum, M. & Shub, M. A simple unpredictable pseudo-random number generator. SIAM J. Comput., 1986, 15, 364-383.

18) Asymptotic analysis of incomplete Gauss sums (theta sums) (Fiedler, H.; Jurkat, W. & Koerner, O. Asymptotic expansions of finite theta series. Acta Arith. , 1977, 32, 129-146; J. Marklof, Theta sums, Eisenstein series, and the semiclassical dynamics of a precessing spin, in: D. Hejhal, J. Friedman, M. Gutzwiller and A. Odlyzko (eds.), Emerging Applications of Number Theory, IMA Volumes in Mathematics and its Applications, Volume 109 (Springer, New York, 1999) pp. 405-450)

19) The statistics of the trajectory of Sinai billiard in a flat two-torus, see Boca, Gologan, Zaharescu and Bykovskii, Ustinov.

20) Analysis of "linear" permutations (from Zolotarev's proof of quadratic reciprocity law).

21) Calculation of quadratic character sums with polynomial arguments.

22) The signature of a generic symmetric integral matrix can be expressed as a finite continued fraction (added by Andrew Ranicki).

23) Lehman's algorithm for factoring large integers.

Best Answer

In knot theory continued fractions are used to classify rational tangles. Conway proved that two rational tangles are isotopic if and only if they have the same fraction. This is proved by Kauffman in http://arxiv.org/pdf/math/0311499.pdf. The paper also contains all the basic definitions and I think it can be read by any mathematician.

Related Question