key: cord-0046144-7umxx0tz
authors: Kristiansen, Lars; Simonsen, Jakob Grue
title: On the Complexity of Conversion Between Classic Real Number Representations
date: 2020-06-24
journal: Beyond the Horizon of Computability
DOI: 10.1007/978-3-030-51466-2_7
sha: e37950188e2bb214ca858e7372bdb6eeac0a4af4
doc_id: 46144
cord_uid: 7umxx0tz

It is known that while it is possible to convert between many different representations of irrational numbers (e.g., between Dedekind cuts and Cauchy sequences), it is in general not possible to do so subrecursively: conversions in general need to perform unbounded search. This raises the question of categorizing the pairs of representations between which either subrecursive conversion is possible, or is not possible. The purpose of this paper is to prove the following positive result: for a number of well-known representations (Beatty sequences, Dedekind cuts, General base expansions, Hurwitz characteristics, and Locators) conversion between the representations can be performed effectively and with good subrecursive bounds.

The benefits of various representations of real numbers by computable functions is well-studied [10, [16] [17] [18] [21] [22] [23] , and it is a standard result that the set of "computable reals" is the same in most representations, but that uniformly computable conversion between different representations is not always possible [18, 22] . When computable conversion is possible, it is in general necessary to perform unbounded search, and efficient, or subrecursive, conversion cannot be done. For example, for any sufficiently large subrecursive class S of functions satisfying mild conditions (e.g., the set of primitive recursive functions or the set of Kalmár elementary functions), write S F , S D , and S C for the sets of irrational numbers representable by continued fractions, Dedekind cuts, and rapidly converging Cauchy sequences computable by functions in S. Then it is known that S F S D S C [13, 21] , and thus a fortiori there can in general be no S-computable uniform conversion from the Cauchy representation to the Dedekind cut representation, or from the Dedekind cut representation to the continued fraction representation (for, if S is closed under composition, such uniform conversions would imply S F = S D = S C ).

In this paper we derive upper bounds on the computational complexity of conversion between various representations of irrational numbers where subrecursive conversion is possible. In general, an irrational α in some representation R 1 will be computable by some function f (e.g., for the continued fraction representation [3; 7, 15, 1, 292, . . .] of π, f (0) = 3, f(1) = 7, . . .), and in some other representation R 2 by some function g (e.g., for the decimal expansion of π, g(0) = 3, g(1) = 1, g(2) = 4); we are interested in the computational resources required to compute g(n) when given access to the function f -in general this will require both querying the function f a number of times and performing a number of other operations, which we collectively call the "overhead" of conversion. In addition to the intrinsic value of this is the consequence that, roughly, if the overhead is a function in S, and S satisfies natural closure properties, it follows that S R1 ⊆ S R2 .

The results of the paper are shown in the diagram below; all results in the left-hand side of the diagram are proved explicitly in the paper. The arrows in the right-hand side of the diagram are known from the literature [13] [14] [15] ; we defer more precise bounds on these (to wit, the existence of primitive recursive bounds) to future research. Dedekind For the purposes of the present paper, we are only interested in upper bounds on conversion overhead. Our results show that conversion between Dedekind cuts and other classic representations can be done with polynomial overhead (and, by composition, conversion between any two of the considered representations in the left-hand side of the diagram above can be done with exponential overhead). More involved algorithms than the one we present here can indubitably be made, forcing the upper bounds to be low-degree polynomials.

Certain prior results are known for the representations we consider, but at a much coarser level of granularity; for example, Lehman [17] proved that the Hurwitz characteristic of α is primitive recursive iff the Dedekind cut of α is primitive recursive. Remark 1. The overhead we consider is polynomial in the value of the index of the desired approximation to an irrational; for example, if one wants to compute the nth digit in the base-b expansion of an irrational α ∈ (0, 1) from a Dedekind cut of α, the overhead will be polynomial in n and b (as opposed to polynomial in the binary representations of n and b). Note that accordingly, the conversions we consider are thus computable in exponential time in the binary representations of n and b.

Remark 2. As the representations in the above diagrams are most easily expressed using functions, we believe that the natural formalizations for conversions are Turing machines with oracle access to the representations being converted from. In other work on real number computation, there is a welldeveloped notion of reducibility between representations that, roughly, requires the representation to be written as an infinite string on one of the input tapes of a type-2 Turing machine [6, 12, 22, 24] . In that setting, for example, a function f : Q ∩ [0, 1] −→ {0, . . . , b − 1} is most naturally expressed by imposing a computable ordering on its domain (e.g., rationals appear in non-decreasing order of their denominator), and the function values f (q) appear encoded as bit strings in this order. We strongly conjecture that our results carry over to the type-2 setting mutatis mutandis.

We assume basic familiary with computability and computational complexity (standard textbooks are [1, 8, 20] ). We write f (n) = poly(n) if f : N −→ N is bounded above by a polynomial in n with positive integer coefficients, and f (n) = polylog(n) if f is bounded above by a polynomial in log n with positive integer coefficients.

We first define oracle machines in the usual way: Definition 3. A (parameterized) function-oracle Turing machine is a (multitape) Turing machine M = (Q, q 0 , F, Σ, Γ, δ) with initial state q 0 ∈ Q, final states F ⊆ Q, input and tape alphabets Σ and Γ (with Σ ⊆ Γ and { } ⊆ Γ \ Σ), and partial transition function δ such that M has a special query tape and two distinct states q q , q a ∈ Q (the query and answer states).

To be executed, M is provided with a total function f : N −→ N (the oracle) prior to execution on any input. We write M f for M when f has been fixed-note that M f is then a usual (non-parameterized) function-oracle machine [8] . The transition relation of M f is defined as usual for Turing machines, except for the state q q : If M enters state q q , let m be (a representation in the tape alphabet of ) the value currently on the query tape; M moves to state q a in a single step, and the contents of the query tape are instantaneously changed to (the representation in the tape alphabet of ) f (m). The time-and space complexity of a functionoracle machine is counted as for usual Turing machines, with the transition between q q and q a taking |f (m)| time steps, and the space use of the query tape after the transition being |f (m)|. The (input) size of a query is the number of symbols on the query tape when M enters state q q .

Function-oracle machines are in standard use in complexity theory of functions on the set of real numbers (see, e.g., [11] ).

All input and output tapes of Turing machines are assumed to have alphabet {0, 1} in addition to the blank symbol. All work tapes have alphabet {0, 1, 2} in addition to the blank symbol. Unless otherwise stated, all elements of N, Z, and elements of any finite set, are assumed to be written on input, query, and output tapes in their binary representation. Pairs (p, q) of integers are assumed to be written using interleaved notation (i.e., the first bit of the binary representation of p followed by the first bit of the binary representation of q, and so forth). In case the representations have unequal length, the shortest binary representation is padded with '2' in the interleaving. Observe that the length of the representation of a pair (p, q) is then O(log max{p, q}). All elements p/q ∈ Q are assumed to be represented by the representation of (p, q).

As expected, using the semantic function of a function-oracle Turing machine M with oracle to f as the oracle of another function-oracle Turing machine N can be made to "cut out the middleman machine M "; that is, we could use a single oracle machine with an oracle to f with bounds on time and oracle use not much higher than the original machines M and N :

Then there is a parameterized function-oracle machine P such that φ f P = φ N g , and P f on input c ∈ C runs in time at most

Proof. P is merely N with the original oracle tape replaced by two new work tapes, a new oracle tape added, and each query to g replaced by execution of a copy of M , with the new work tapes functioning as the "input" and "output" tapes of the copy of M , and the new oracle tape as the oracle tape of the copy of M . Every time N would query g, it writes the query a on the new "input" work tape. The copy of M then computes g(a) using time at most t M (s(|c|)) with q M (s(|c|)) queries to f , hence a total of q N (|c|)q M (s(|c|)) queries to f . The total time spent by P is the time spent by N plus at most t M (s(|c|)) steps per oracle query, for a total of O(q N (|c|)t M (s(|c|)) + t N (|c|)) steps.

In particular, function-oracle machines running in polynomial time and having queries of polynomial input size are composable in the above way and yield new machines running in polynomial time.

A Farey sequence is a strictly increasing sequence of fractions between 0 and 1. The Farey sequence of order k, denoted F k , contains all fractions which when written in their lowest terms, have denominators less than or equal to k.

Let a/b and c/d be fractions in their lowest terms. The fraction m(a/b, c/d) = (a + c)/(b + d) is called the mediant of a/b and c/d. The ordered pair of two consecutive fractions in a Farey sequence is called a Farey pair. It is easy to see

We arrange the fractions strictly between 0 and 1 in a binary search tree T F . Thus, we have, for example:

We shall later need the two following ancillary propositions which we include without proof.

Efficient computations of the elements of the Stern-Brocot tree (and hence also the Farey pair tree) is possible [2, 19] ; for our purposes, we simply need the following result: 

We now introduce a number of well-known representations of real numbers. Representations by Dedekind cuts [4, 7] , Beatty sequences [3] 2 , and Hurwitz characteristics [9] 3 were known in the 19th century or earlier. The representations by locators and general base expansions are, to our knowledge, new, but natural. In particular, the general base expansion yields the base-b expansions of α in any integer base b ≥ 2 on demand; it turns out that this is the key to subrecursive equivalence with Dedekind cuts (whereas the base-b expansion for any fixed b is not subrecursively equivalent to Dedekind cuts, see [14] ). 

A general base expansion of the real number α is the function 2 Apparently, what is now known as Beatty sequences was used earlier by Bernard Bolzano [5] , whence this representation of reals could also be called Bolzano measures. 3 Use of the Hurwitz characteristic to represent numbers rather than a stepping stone for other material is a much younger invention [17] . 4 Strictly speaking, the classic Hurwitz characteristic corresponds to a path through the full Stern-Brocot tree (not just the "left" tree as we consider here), and hence the classic Hurwitz characteristic H of α ∈ (0, 1) is the function defined by H (0) = 0 and H (q) = 0 · H(q − 1) for q > 0. This does not change our results in any material way.

The remainder of the paper is devoted to proving the following theorem:

Theorem 14. For each representation R below there is a parameterized function-oracle machine M such that, for every irrational α between 0 and 1, M when provided with an oracle to the R-representation of α, will compute the Dedekind cut of R, and N when provided with an oracle to the Dedekind cut of α, will compute the R-representation of α. Let n be the largest integer in the input (i.e., n if domain of R is N,

. Then, M and N will produce their output in time poly(n) using at most poly(n) oracle calls of size at most poly(n).

-the locator of α -the Beatty sequence of α -the general base expansion of α -the Hurwitz characteristic of α Furthermore, conversion between any two of the above representations (e.g., from the locator of α to the Beatty sequence of α) can be done by function-oracle machines producing their output using exponential (in n) time, exponential (in n) number of oracle calls, and exponential (in n) size of oracle calls.

The proof of conversion from and to Dedekind cuts is contained in the sequence of lemmas below that all relate the various representations to the Dedekind cut. All lemmas assert existence of parameterized function-oracle machines that will convert from or to the Dedekind cut of α with polynomial overhead (often with smaller overhead, whence the result follows a fortiori ). The result that we can convert between any of the representations using exponential overhead then follows by an application of Proposition 5. 

Observe that, for any interval (r 1 , r 2 ), if D(r 1 ) = D(r 2 ) = 0, then α > r 2 , and if D(r 1 ) = D(r 2 ) = 1, then α < r 1 (and the case D(r 1 ) = 1 ∧ D(r 2 ) = 0 is not possible). Thus, M can use D to perform binary search on (the endpoints of) the above set of intervals to find the (necessarily unique) interval Proof. On input p/q ∈ Q, M first checks if q = 1, and outputs 0 if p ≤ 0 and 1 if p ≥ 1. Otherwise, q > 1, and M computes E(q, 1); by definition, this is an element of {0, . . . , q − 1}. Observe that D(p/q) = 0 iff p/q < α iff p ≤ E(q, 1). Hence, M outputs 0 if p ≤ E(q, 1), and outputs 1 otherwise. M needs to write the (representation of the) pair (q, 1) on the oracle tape and perform a single comparison of numbers of magnitude at most max{p, q}, hence M uses time O(log max{p, q}) for the comparison. M uses exactly one oracle call to E with the pair (q, 1), the representation of which uses at most O(log q) bits. (max{p 1 , q 1 , p 2 , q 2 }) ), and uses at most 2 oracle calls, each of input size at most O(log max{p 1 , q 1 , p 2 , q 2 }).

Proof. Let L be the locator of α. Observe that for any two rational numbers p 1 /q 1 , p 2 /q 2 ∈ Q, we have α ∈ (p 1 /q 1 , p 2 /q 2 ) iff L(p 1 /q 1 , p 2 /q 2 ) = 0 iff (D(p 1 /q 1 ) = 0∧D(p 2 /q 2 ) = 1). Hence, M simply queries D (using the binary representations of the rationals) twice, outputs 1 if (D(p 1 /q 1 ) = 0 ∧ D(p 2 /q 2 ) = 1), and outputs 1 otherwise. Clearly, the time needed is the time needed to transfer p 1 /q 1 and p 2 /q 2 to the query tape plus some constant independent of the size of the input, hence M uses time O(log(max{p 1 , q 1 , p 2 , q 2 })). Proof. Observe that for p/q ∈ (0, 1) ∩ Q, we have D(p/q) = L(p/q, 1). Hence, M may, on input p/q simply perform a single query to L; this requires copying its input to the oracle tape, i.e. only linear time in the size of the representation of the input. By convention, the input p/q is representable in at most O(log max{p, q}) bits. {0, 1 . . . , q−1}) . The comparison p ≤ B(q) can be performed bitwise using the binary representations of p and B(q) which is clearly linear in log(max{B(q), p}) ≤ log max{p, q}. Writing q on the oracle tape clearly also takes time linear in log q. in time at most O(i) = O(n) by two standard schoolbook additions, and the step i contains exactly one query to D. Hence, the total time needed for M to construct H(n) is at most O(npoly(n)) = poly(n), with exactly n oracle calls, each of size at most O(log 2 n ) = O(n).

We have analyzed conversions between representations equivalent to Dedekind cuts, and we have seen that we can convert efficiently between any two such representations (Theorem 14) . We strongly conjecture that the same efficiency is not possible between representations equivalent to continued fractions. Indeed, we regard the representations equivalent to continued fractions to be the most interesting and challenging ones from a mathematical point of view. Among these representations we find the trace functions and the contractors (see the figure on Page 2). A function T : Q → Q is a trace function for the irrational number α when |α − r| > |α − T (r)|. A function F : [0, 1] → (0, 1) is a contractor if we have |F (r 1 ) − F (r 2 )| < |r 1 − r 2 | for any rationals r 1 , r 2 where r 1 = r 2 . Both trace functions and contractors can be converted to (and from) continued fractions without unbounded search, and converting from a contractor to a trace function is easy as it can be proved that every contractor is a trace function. But conversely, we believe that it is not possible to convert a trace function to a contractor within reasonably small time or space bounds.

Conversions between representations equivalent to rapidly converging Cauchy sequences also deserve a further study. One such representation will be base-2 expansions over the digits 0 (zero), 1 (one) and 1 (minus one). In this representation, the rational number 1/4 can be written as 0.01, but also as 0.11. Another interesting representation are the fuzzy Dedekind cuts. A fuzzy Dedekind cut for an irrational number α is a function D : Z × N → {0, 1} satisfying (i) D(p, q) = 0 implies α < (p + 1)/q and (ii) D(p, q) = 1 implies (p − 1)/q < α. Thus, each irrational α will have (infinitely) many fuzzy Dedekind cuts. If D is a fuzzy cut for α and we know that D (3, 8) = 0, then we know that α lies below 4/8 (but we do not know if α lies below 3/8). Moreover, if we also know that D(6, 16) = 1, then we know that α lies in the interval (3/8 − 1/16, 3/8 + 1/8) (but we do not know if α lies below or above 3/8).

Finally, some well-known representations are not subrecursively equivalent to any of the three representations above, for example the base-b representation for any integer base b ≥ 2. It is possible to convert a Dedekind cut to a base-b expansion and a base-b expansion into a Cauchy sequence without unbounded search, but not the other way around [14, 21] . It is interesting to investigate the set of representations subrecursively equivalent to such expansions.

Computational Complexity: A Modern Approach

Locating terms in the Stern-Brocot tree

Problems for solutions: 3173-3180

Traité d'arithmétique (1849)

Pure Theory of Numbers

Topological properties of real number representations

Stetigkeit und irrationale Zahlen

Theory of Computational Complexity

Ueber die angenäherte Darstellung der Irrationalzahlen durch rationale Brüche

On the definitions of some complexity classes of real numbers

Computational complexity of real functions

Theory of representations

On subrecursive representability of irrational numbers

On subrecursive representability of irrational numbers, part ii

On subrecursive representability of irrational numbers: continued fractions and contraction maps

Real numbers, continued fractions and complexity classes

On primitive recursive real numbers

On computable sequences

Exact arithmetic on the Stern-Brocot tree

Introduction to the Theory of Computation

Nicht konstruktiv beweisbare Sätze der

The degrees of discontinuity of some translators between representations of real numbers

Computable Analysis

Representations of the real numbers and of the open subsets of the set of real numbers

We are grateful for the meticulous comments of one of the referees; these have helped to significantly improve the paper.

Proof. On input p/q ∈ Q (where we assume wlog. that p/q is reduced to lowest terms), M computes H(p + q) (using polylog(max{p, q}) operations to compute the binary representation of p + q, and then performing a single oracle call; note that the result of the oracle H(p + q) is a bit string of length exactly p + q = poly(max{p, q}). M then computes T F (H(p + q)) (by Proposition 8 this can be done in time poly(1 + |H(p + q)|) = poly(max{p, q})) to obtain a Farey pair (a/b, c/d) such that a/b < α < c/d. By Proposition 7, any reduced fraction p/q occurs as one of the fractions in a Farey pair in T F at depth at most p+q −1, and thus exactly one of (i) p/q ≤ a/b and (ii)It is an easy induction on the depth d to see that a numerator or denominator in any fraction occurring in a Farey pair at depth Proof. On input n, M constructs a path of length n in the tree T SB corresponding to the bit string H(n) by building the corresponding path in T F . M can do this by starting at i = 0 and incrementing i, maintaining a current Farey pairHence, M starts with (a 0 /b 0 , c 0 /d 0 ) = (0/1, 1/1), and constructs the n intervals (a i /b i , c i /d i ) for i = 1, . . . , n by computing the mediant and querying D in each step. Observe that the query in step i is the (binary representation of the) mediant of a Farey pair at depth i − 1, thus its denominator is bounded above by 2 i and its binary representation uses at most O(log 2 i ) = O(i) bits.As the numerators and denominators at depth i in T F are of size at most 2 i (hence representable by i bits), computing the mediant at step i can be done