Description of Generalized Continued Fractions by Finite Automata

J. O. Shallit Department of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1 Canada

Abstract.

A generalized continued fraction algorithm associates with every real number x a sequence of integers; x is rational iff the sequence is finite. For a fixed algorithm, call a sequence of integers valid if it is the result of that algorithm on some input x_{0}. We show that, if the algorithm is sufficiently well-behaved, then the set of all valid sequences is accepted by a finite automaton.

I. Introduction.

It is well known that every real number x has a unique expansion as a simple continued fraction in the form

x = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + ⋯}}

= [a_{0}, a_{1}, a_{2}, ...]

where a_{i} ∈ ZZ for i ≥ 0, a_{j} ≥ 1 for j ≥ 1, and if the expansion terminates with a_{n}, then a_{n} ≥ 2.

Given x, we may find its simple continued fraction expansion with the following algorithm:

Algorithm SCF(x); outputs (a_{0}, a_{1}, …):

SCF1. Set x_{0} ← x; set i ← 0.

SCF2. Set a_{i} ← ⌊x_{i}⌋.

SCF3. If a_{i} = x_{i} then stop. Otherwise set x_{i+1} ← 1/(x_{i} − a_{i}); set i ← i + 1 and go to step SCF2.

For example, SCF(52/43) = (1, 4, 1, 3, 2).

In fact, the rules “a_{j} ≥ 1 for j ≥ 1” and “if the expansion terminates with a_{n}, then a_{n} ≥ 2” exist precisely so the set of valid expansions coincide with the possible outputs of the continued fraction algorithm.

There exist other versions of the continued fraction algorithm. For example, the socalled nearest integer continued fraction (NICF) satisfies the following rules: a_{j} ≤ −2 or a_{j} ≥ 2 for j ≥ 1; if a_{j} = −2 then a_{j+1} ≤ −2; if a_{j} = 2 then a_{j+1} ≥ 2; and if the expansion terminates with a_{n}, then a_{n} ≠ 2. The NICF is generated by algorithm SCF above with step SCF2 replaced by

SCF2′. Set a_{i} ← ⌊x_{i} + \frac{1}{2}⌋.

For example, NICF(52/43) = (1, 5, −4, −2).

(Actually, the NICF is usually described slightly differently in the literature, but our formulation is essentially the same. See [Hur2].)

The concept of “rules” that describe the set of possible outputs of a continued fraction expansion also appears in a paper of Hurwitz [Hur1] which describes the nearest integer continued fraction algorithm in ZZ[i].

In this paper, we are concerned with the following questions:

(1) Which functions f are suitable replacements for the floor function in Algorithm SCF (i. e. yield generalized continued fraction algorithms)?

(2) Which of these functions correspond to generalized continued fraction algorithms which have “easily describable” outputs (i. e. accepted by a finite automaton)?

In this paper, we will answer question (1) by fiat, and then examine the consequences for question (2).

II. Real Integer Functions and Finite Automata.

Let us introduce some notation. By [a_{0}, a_{1}, a_{2}, ..., a_{n}] we will mean the value of the expression

a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + ⋯ + \frac{1}{a_{n}}}} ,

and not necessarily the result of the algorithm SCF.

Let f : R → ZZ. We say f is a real integer function if

(i) |f(x) − x| < 1 for all x ∈ R;
(ii) f(x + j) = f(x) + j for all x ∈ R, j ∈ ZZ.

Examples are f(x) = ⌊x⌋, f(x) = ⌈x⌉, f(x) = ⌊x + \frac{1}{2}⌋.

Real integer functions induce generalized continued algorithms by imitating algorithm SCF above:

Algorithm CF_{f}(x);outputs (a_{0}, a_{1}, …):

CF1. Set x_{0} ← x; set i ← 0.

CF2. Set a_{i} ← f(x_{i}).

CF3. If a_{i} = x_{i} then stop. Otherwise set x_{i+1} ← 1/(x_{i} − a_{i}), i ← i + 1 and go to step C2.

We leave it to the reader to verify that (i) The algorithm CF_{f} terminates iff x is rational and (ii) if CF_{f}(x) terminates, with (a_{0}, a_{1}, … a_{n}) as output, then x = [a_{0}, a_{1}, …, a_{n}].

The main result of this paper is that the outputs of CF_{f} are easily describable in most of the interesting cases, including all the examples mentioned above. Let us define more rigorously what we mean by “easily describable”.

Call a (finite or infinite) sequence of integers valid if it is the result of CF_{f}(x) for some x. We envision a finite automaton which reads a purported finite expansion a = (a_{0}, a_{1}, … a_{n}) and reaches a final state on the last input iff a is valid. Also, given a valid infinite sequence (a_{0}, a_{1}, …), the automaton should never “crash” (i. e. attempt to make a transition for which the resulting state is undefined), though it may fail to “crash” on invalid infinite expansions.

We emphasize again that our description must in some sense cover all valid outputs of the algorithm, and is not concerned with, for example, the periodicity for specific inputs.

One minor problem with the model described above is that the a_{i} belong to ZZ, but in defining finite automata we usually insist that our alphabet Σ is finite. We can get around this in one of two ways: first, we could expand the definition of finite automata so that there can be infinitely many transitions (but still only finitely many states). Second, we could redefine our strings as numbers encoded in a particular base. (Even if a state has infinitely many transitions associated with it, they are all of a certain form that is easily describable by a regular set.) It turns out that either approach is satisfactory, but for simplicity we choose the first.

Definition.

A finite automaton is a 5-tuple (Q, Σ, δ, q_{0}, F) where Q is a finite set of states, Σ is a (not necessarily finite) input alphabet, q_{0} ∈ Q is the initial state, F ⊆ Q is the set of final states, and δ is the transition function mapping Q × Σ to Q. δ may be incomplete; i. e. δ(q, a) may be undefined for some pairs q, a.

We extend δ to a function which maps Q × Σ^{∗} to Q in the obvious fashion.

The reader to whom these definitions are unfamiliar should consult [HU].

Notation.

If A is a set, then by A^{−1} we mean the set {x ∈ R : x^{−1} ∈ A}. If f is a function, then by f^{−1}[a] we mean, as usual, the set {x ∈ R : f(x) = a}. If A is a set, then by A − a we mean the set {x : x + a ∈ A}. We will say x is quadratic if x is the real root of a quadratic equation with integer coefficients.

Definition.

Let f be a real integer function. Then we say that the finite automaton A = (Q, ZZ, δ, q_{0}, F) accepts the outputs of CF_{f} if

(i) δ(q_{0}, a_{0}a_{1}a_{2} ⋯ a_{n}) ∈ F iff there exists q ∈ |Q such that CF_{f}(q) = (a_{0}, a_{1}, …, a_{n}).

(ii) If x is irrational and CF_{f}(x) = (a_{0}, a_{1}, …), then δ(q_{0}, a_{0}a_{1} ⋯ a_{n}) is defined for

all n ≥ 0.

The object of this paper is to prove the following theorem:

Theorem 1.

Let f^{−1}[0] be the finite union of intervals. Then there exists a finite automaton accepting the outputs of CF_{f} iff all the endpoints of the intervals are rational or quadratic.

In section III below, we will prove one direction of this theorem; in section IV, we prove the other.

Comment.

No simple characterization seems to exist in the case where f is not the finite union of intervals. In section IV below, we will give an example of an f that is accepted by a finite automaton, but f^{−1}[0] is not the finite union of intervals.

III. One direction of the theorem.

Let f^{−1}[0] be the finite union of intervals. We will create a finite automaton as follows: states will correspond to certain subsets of f^{−1}[0], and transitions will correspond to partial quotients a_{i}. We will define δ(q_{0}, a_{0}) = f^{−1}[0] for all a_{0} ∈ ZZ and inductively define

δ(q_{i}, a) = q_{j}

where q_{j} = (q_{i}^{−1} ∩ f^{−1}[a]) − a. We say q_{i} ∈ F if 0 ∈ q_{i}.

To verify that this construction works, we need to show that (i) the automaton accepts CF_{f} and (ii) this process generates only a finite number of distinct states.

Let us agree to the following unpleasant notation. When we write

CF_{f}(x) = (a_{0}, a_{1}, a_{2}, …, a_{n}, …)

we will mean that the first n+1 outputs of the algorithm CF_{f} on x are given by a_{0} through a_{n}; there may be more outputs or not.

Lemma 2.

δ(q_{0}, a_{0}a_{1} ⋯ a_{n}) = {x : CF_{f}([a_{0}, a_{1}, a_{2}, ⋯, a_{n−1}, a_{n} + x]) = (a_{0}, a_{1}, …, a_{n}, …)}.

Proof.

The lemma is proved by induction. It is easy to verify that

δ(q_{0}, a_{0}) = f^{−1}[0] = {x : CF_{f}([a_{0} + x]) = (a_{0}, …)}.

Assume true for k. Then

δ(q_{0}, a_{0}a_{1} ⋯ a_{k}) = {x : CF_{f}([a_{0}, a_{1}, ⋯, a_{k−1}, a_{k} + x]) = (a_{0}, a_{1}, … a_{k}, …)}. Thus

δ(q_{0}, a_{0}a_{1} ⋯ a_{k})^{−1} = {x^{−1} : CF_{f}([a_{0}, a_{1}, ⋯, a_{k−1}, a_{k} + x]) = (a_{0}, a_{1}, … a_{k}, …)}
⇒ δ(q_{0}, a_{0}a_{1} ⋯ a_{k})^{−1} = {x : CF_{f}([a_{0}, a_{1}, ⋯, a_{k−1}, a_{k}, x]) = (a_{0}, a_{1}, … a_{k}, …)}
⇒ δ(q_{0}, a_{0}a_{1} ⋯ a_{k})^{−1} ∩ f^{−1}[a_{k+1}] = {x : CF_{f}([a_{0}, a_{1}, ⋯, a_{k−1}, a_{k}, x]) =
(a_{0}, a_{1}, … a_{k}, a_{k+1}, …)}
⇒ δ(q_{0}, a_{0}a_{1} ⋯ a_{k+1}) = (δ(q_{0}, a_{0}a_{1} ⋯ a_{k})^{−1} ∩ f^{−1}[a_{k+1}]) − a_{k+1}
= {x : CF_{f}([a_{0}, a_{1}, ⋯, a_{k}, a_{k+1} + x]) = (a_{0}, a_{1}, … a_{k}, a_{k+1}, …)}.

which completes the proof. Corollary.

δ(q_{0}, a_{0}a_{1} ⋯ a_{n}) ∈ F iff there exists q ∈ |Q such that CF_{f}(q) = (a_{0}, a_{1}, …, a_{n}). Proof.

Assume δ(q_{0}, a_{0}a_{1} ⋯ a_{n}) ∈ F. Then by the definition of the set of final states F, we must have 0 ∈ δ(q_{0}, a_{0}a_{1} ⋯ a_{n}). But by the lemma, then the first n + 1 outputs of the algorithm CF_{f} on input [a_{0}, a_{1}, …, a_{n}] are precisely (a_{0}, a_{1}, …, a_{n}). Hence we may take q = [a_{0}, a_{1}, …, a_{n}].

Now assume that there exists q ∈ |Q such that CF_{f}(q) = (a_{0}, a_{1}, …, a_{n}). Then from the definition of CF_{f}, we see that x_{n} = a_{n}; hence

0 = x_{n} − a_{n} ∈ δ(q_{0}, a_{0}a_{1} ⋯ a_{n})

which shows that δ(q_{0}, a_{0}a_{1} ⋯ a_{n}) is a final state.

We leave it to the reader to verify that if x is irrational and CF_{f}(x) = (a_{0}, a_{1}, …), then the automaton never crashes on any prefix of the output.

It remains to show that this construction generates a finite number of states. By the inductive definition of states as certain subsets of f^{−1}[0], we see that if e ∈ [−1, 1] is an endpoint of an interval in q_{j}, then either e is an endpoint of an interval of f^{−1}[0], or e = (1/d) − f(1/d), where d is an endpoint of an interval q_{i}, where there exists a transition δ(q_{i}, a) = q_{j}. Since for any particular x we have f(x) = ⌊x⌋ or f(x) = ⌈x⌉, it suffices to prove the following:

Lemma 3.

Define s_{1} : x → (1/x) − ⌊1/x⌋ and s_{2} : x → (1/x) − ⌈1/x⌉. Consider the semigroup u formed by s_{1} and s_{2} under composition. Let u(x) be the orbit of x under elements of u.

Then u(x) is finite iff x is rational or quadratic.

Proof.

One direction is easy. Assume u(x) is finite. Then in particular the set

x, s_{1}(x), s_{1}^{(2)}(x), …

is finite. Hence we have s_{1}^{(j)}(x) = s_{1}^{(k)}(x) for some j ≠ k. But it is easily proved by induction that

x = [0, a_{0}, a_{1}, …, a_{n−1} + s_{1}^{(n)}(x)]

for some sequence of integers a_{0}, a_{1}, …; hence there exist integers such that

x = \frac{a_{j} + b_{j}s_{1}^{(j)}(x)}{c_{j} + d_{j}s_{1}^{(j)}(x)},

and similarly

x = \frac{a_{k} + b_{k}s_{1}^{(k)}(x)}{c_{k} + d_{k}s_{1}^{(k)}(x)}.

Thus we see that s_{1}^{(j)}(x) is the root of a quadratic equation, and so is either quadratic or rational. Thus x itself is either quadratic or rational.

Now let us prove the other direction. The assertion is trivial for x rational, x = p/q, for then s_{1}(p/q) = (q mod p)/p and s_{2}(p/q) = −((−q) mod p)/p. Thus an application of s_{1} or s_{2} decreases the absolute value of the numerator, while retaining the relationship |x| < 1. Thus iterated applications of s_{1} and s_{2} reduce p/q to 0.

Now let us consider the case where x is the root of a quadratic equation with integer coefficients. We use the classical theorem that the simple continued fraction for x is ultimately periodic iff x is quadratic. If x is quadratic, let r(x) denote the length of the repeating portion (period) of the simple continued fraction for x, and let q(x) denote the length of the leading portion of the continued fraction. (Example: if x = \sqrt{7}, then SCF(x) = (2, 1, 1, 1, 4, 1, 1, 1, 4, …); hence r(x) = 4 and q(x) = 1.)

Let S_{1} : x → 1/(x − ⌊x⌋) and S_{2} : x → 1/(x − ⌈x⌉). Since S_{1}(x) = s_{1}(x^{−1})^{−1} and S_{2}(x) = s_{2}(x^{−1})^{−1}, it suffices to prove the theorem for the semigroup U formed by S_{1} and S_{2} under composition.

Let x be quadratic. We will show that U(x) is finite by showing that repeated application of the maps S_{1} and S_{2} can result in at most a finite number of distinct simple continued fraction expansions. More precisely, we show that every element in U(x) has a simple continued fraction whose period is identical to or is a cyclic shift of the period for x; that there exists a uniform upper bound for q(y) for y ∈ U(x), and that the partial quotients of the continued fraction for each y ∈ U(x) are also bounded.

Let the simple continued fraction expansion of x be given by (a_{0}, a_{1}, a_{2}, a_{3}, …). Then

SCF(S_{1}(x)) = (a_{1}, a_{2}, a_{3}, …).  (1)

The description of S_{2}(x) is slightly more complicated:

SCF(S_{2}(x)) = \{ \begin{matrix}(−(a_{2} + 2), a_{4} + 1, a_{5}, a_{6}, …) & if a_{1} = 1, a_{3} = 1; \\ (−(a_{2} + 2), 1, a_{3} − 1, a_{4}, a_{5}, …) & if a_{1} = 1, a_{3} ≥ 2; \\ (−2, a_{2} + 1, a_{3}, a_{4}, …) & if a_{1} = 2; \\ (−2, 1, a_{1} − 2, a_{2}, a_{3}, …) & if a_{1} ≥ 3. \end{matrix}  (2)

For example, see [Knu, pp. 358, 600].

From equations (1) and (2), it is clear that

r(S_{i}(x)) = r(x)

for i = 1, 2. An application of S_{i} does not change the period, although by “sliding” elements off the left end of the continued fraction, it may shift the period cyclically.

Now define t(x) = max(q(x), r(x), 3). I claim that

t(S_{i}(S_{j}(x))) ≤ t(x),

for 1 ≤ i, j ≤ 2. This is a tedious verification of cases, and is left to the reader. Since t is bounded, it follows that q is also bounded.

It remains to show that the partial quotients of elements of U(x) are bounded. Let a(x; i) denote the ith partial quotient of the simple continued fraction for x. Let x^{(k)} denote the kth iterate of x under one of the two maps S_{1} and S_{2}. Let M = max_{i≥0} |a(x; i)|. Clearly M is finite since the simple continued fraction for x is ultimately periodic.

Then we will show that, for all k ≥ 0,

(a) 1 ≤ a(x^{(k)}; j) ≤ M for all j ≥ 2.

(b) 1 ≤ a(x^{(k)}; 1) ≤ M + 1.

(c) |a(x^{(k)}; 0)| ≤ M + 2.

Assume not. Then there exists a minimal superscript m such that one of the conditions above fails for x^{(m)}.

Write SCF(x^{(m−1)}) = (a_{0}, a_{1}, a_{2}, …). Then using the lemma above, we have

SCF(x^{(m)}) = \{ \begin{matrix}(a_{1}, a_{2}, a_{3}, …) & (i) \\ (−(a_{2} + 2), a_{4} + 1, a_{5}, a_{6}, …) & (ii) \\ (−(a_{2} + 2), 1, a_{3} − 1, a_{4}, a_{5}, …) & (iii) \\ (−2, a_{2} + 1, a_{3}, a_{4}, …) & (iv) \\ (−2, 1, a_{1} − 2, a_{2}, a_{3}, …) & (v) \end{matrix}

Assume (a) fails for k = m. Then a(x^{(m)}; j) > M for some j. But this is clearly false for j ≥ 3. For j = 2, it is clearly false for cases (i), (ii), and (iv). For case (iii), a_{3} − 1 > M ⇒ a_{3} > M + 1, which is impossible by minimality of m. For case (v), a_{1} − 2 > M ⇒ a_{1} > M + 2, impossible by minimality of m.

Now assume (b) fails for k = m. Then a(x^{(m)}; 1) > M + 1. But this is clearly false for cases (i), (iii), (v). For case (ii), a_{4} + 1 > M + 1 ⇒ a_{4} > M, which is a contradiction. For case (iv), a_{2} + 1 > M + 1 ⇒ a_{2} > M, a contradiction.

Now assume (c) fails for k = m. Then |a(x^{(m)}; 0| > M + 2. But this is clearly false for cases (i), (iv), and (v). For cases (ii) and (iii), | − (a_{2} + 2)| > M + 2 ⇒ a_{2} > M, which is a contradiction.

This completes the proof of the Lemma 3.

Combining Lemmas 2 and 3 completes the proof of one direction of Theorem 1.

We now give an example of the construction of the finite automaton. Let us obtain the description of the outputs for CF_{f} for f(x) = ⌊x + \frac{\sqrt{2}}{2}⌋. We find q_{0} = f^{−1}[0] = [−\frac{\sqrt{2}}{2}, \frac{2−\sqrt{2}}{2}); q_{1} = [−\frac{\sqrt{2}}{2}, 1 − \sqrt{2}]; q_{2} = (\sqrt{2} − 2, \frac{2−\sqrt{2}}{2}); q_{3} = [1 − \sqrt{2}, \frac{2−\sqrt{2}}{2}). The transitions δ(q_{i}, a) are given by the following table:

Insert table here

IV. Completing the proof of Theorem 1.

We now wish to show that if f^{−1}[0] consists of the finite union of intervals, but one of those intervals has an endpoint that is not rational or quadratic, then no finite automaton can accept CF_{f}.

Assume that such an automaton A exists. Then we may assume that each state is in fact reachable from q_{0}; otherwise this state may be discarded without affecting A. For each state q_{j}, construct an input sequence a_{0}a_{1} ⋯ a_{i} such that δ(q_{0}, a_{0}a_{1} ⋯ a_{i}) = q_{j}. Let us label each state q_{j} with a subset of |Q, L(q_{j}), by the following rule: If δ(q_{0}, a_{0}a_{1} ⋯ a_{i}) = q_{j}, then

L(q_{j}) = {x ∈ |Q : CF_{f}([a_{0}, a_{1}, …, a_{i−1}, a_{i} + x]) = (a_{0}, a_{1}, …, a_{i}, …)}.

We need to show that this map is indeed well-defined, in the sense that different paths from q_{0} to q_{j} give the same labels L(q_{j}). Assume that

δ(q_{0}, a_{0}a_{1} ⋯ a_{i}) = q_{j}

and

δ(q_{0}, b_{0}b_{1} ⋯ b_{k}) = q_{j},

and there exists a rational number p such that

p ∈ S_{1} = {x ∈ |Q : CF_{f}([a_{0}, a_{1}, …, a_{i−1}, a_{i} + x]) = (a_{0}, a_{1}, …, a_{i}, …)}  (3)

but

p ∉ S_{2} = {x ∈ |Q : CF_{f}([b_{0}, b_{1}, …, b_{k−1}, b_{k} + x]) = (b_{0}, b_{1}, … b_{k}, …)}.  (4)

Write CF_{f}(p) = (0, a_{i+1}, …, a_{n}); by our definition of what it means to accept the output of CF_{f}, we know that

δ(q_{j}, a_{i+1} ⋯ a_{n}) = q_{r} ∈ F,

a final state. Let y = [b_{0}, b_{1}, …, b_{k}, a_{i+1}, … a_{n}]. Then since the automaton is in state q_{j} upon reading inputs b_{0}b_{1} ⋯ b_{k}, we have

δ(q_{0}, b_{0}b_{1} ⋯ b_{k}a_{i+1} ⋯ a_{n}) = q_{r}.

Hence CF_{f}(y) = (b_{0}, b_{1}, …, b_{k}, a_{i+1}, … a_{n}). But then y = [b_{0}, b_{1}, …, b_{k} + p] which shows that indeed p ∈ S_{2}, a contradiction.

Thus we may assume that sets L_{i} = L(q_{i}) are well-defined. Let Ā denote the closure of the set A in R, and consider the sets L̄_{i}. I claim that since f^{−1}[0] consists of the finite union of intervals, so does each of the sets L̄_{i}; this follows easily from the definition of CF_{f}. Suppose δ(q_{i}, a) = q_{j}; then the endpoints e of intervals of L̄_{j} are those of f^{−1}[0] or are related to the endpoints E of L̄_{i} by the equation

e = \frac{1}{E} − a.

Since f^{−1}[0] contains an endpoint which is not rational or quadratic, so must L̄_{0}. Hence there exists a transition δ(q_{0}, a) = q_{i} such that L̄_{i} contains an endpoint which is not rational or quadratic. Continuing in this fashion, and remembering that there are only a finite number of states, we eventually return to a state previously visited, which gives one of the two equations

e = [0, a_{1}, …, a_{k}]

or

e = [0, a_{1}, …, a_{k} + e]

which shows that e is rational or quadratic, contrary to assumption.

This completes the proof of Theorem 1.

Now let us give an example of an f such that f^{−1}[0] is not the finite union of intervals, but nevertheless there is a finite automaton accepting CF_{f}.

Let f(x) be defined by

f(x) = \{ \begin{matrix}⌊x⌋, & if x is rational; \\ ⌈x⌉, & if x is irrational. \end{matrix}

Then

f^{−1}[0] = {x : x rational , 0 ≤ x ≤ 1} ∪ {x : x irrational , −1 ≤ x < 0}.

Clearly f^{−1}[0] cannot be written as the finite union of intervals. Then it is easily verified that the procedure of section III generates a finite automaton with four states that accepts CF_{f}.

It may be of interest to remark that the automata accepting the result of CF_{f} may be arbitrarily complex. For example, it can be easily shown that the automaton corresponding to

f^{−1}[0] = [−\frac{F_{n−1}}{F_{n}} , \frac{F_{n−2}}{F_{n}})

has n + 1 states. (Here F_{n} denotes the nth Fibonacci number.)

V. Epilogue.

Several other writers have noted connections between finite automata and continued fractions. One of the best known papers is that of Raney, who showed how to obtain the simple continued fraction for

β = \frac{aα + b}{cα + d}

in terms of the continued fraction for α. See [Ran], [Bey].

Istrail considered the language consisting of all prefixes of the continued fraction for x, and observed that this language is context-free and non-regular iff x is a quadratic irrational [Ist].

Allouche discusses several applications of finite automata to number theory, including continued fractions [All].

In this paper, we have been concerned with a different approach; namely, describing the “set of rules” associated with a generalized continued fraction algorithm. One immediately wonders if similar theorems may be obtained for continued fraction algorithms in ZZ[i], such as those discussed by Hurwitz [Hur1] and McDonnell [McD].

In [Sha], the author proved that the McDonnell’s continued fraction algorithm can be described by a finite automaton with 25 states. The corresponding result for Hurwitz’s algorithm is not known.

References

[All] J.-P. Allouche, Finite automata in number theory, to appear.

[Bey] W. M. Beynon, A formal account of some elementary continued fraction algorithms, J. Algorithms 4 (1983) 221-240.

[HU] J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, 1979.

[Hur1] A. Hurwitz, Über die Entwicklung Complexer Grössen in Kettenbrüche, Acta Arithmetica 11 (1888) 187-200 (= Werke, II, 72-83).

[Hur2] A. Hurwitz, Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen, Acta

Arithmetica 12 (1889) 367-405 (= Werke, II, 84-115).

[Ist] S. Istrail, On formal construction of algebraic numbers of degree two, Rev. Roum. Math. Pures et Appl. 22 (1977) 1235-1239.

[Knu] D. E. Knuth, The art of computer programming, V. II (Seminumerical Algorithms), 2nd Edition, Addison-Wesley, 1981.

[McD] E. E. McDonnell, Integer functions of complex numbers, with applications, IBM Philadelphia Scientific Center, Technical Report 320-3015, (February, 1973).

[Ran] G. N. Raney, On continued fractions and finite automata, Math. Ann. 206 (1973) 265-283.

[Sha] J. O. Shallit, Integer functions and continued fractions, A. B. Thesis, Princeton University, 1979.