Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a integral modular.

But this kind of easy things won't happen on some other numbers, like PI. (this wiki page http://en.wikipedia.org/wiki/Calculating_pi#Digit_extraction_methods says that it costs O(n^2) to calculate the Nth digit in PI)

After that observation I make a rudimentary assertions (if we assume that modular operation is constant time complexity):

  • For any rational number (and its decimal form), it costs constant time to calculate its any digit;
  • Conversely, given a number, if it costs constant time to calculate its any digit, it is a rational number.

I have tried and I think it's close to prove the first one, but I don't have any idea about the second. Have anyone got any idea about that? Or have I missed any articles describing this kind of problems?

Moreover, if we call the time complexity to calculate a digit in a decimal as its digit time complexity (seems we need a better name), we could partition all real numbers by its digit time complexity. Then how to calculate the cardinal for each subset?

share|improve this question
1  
One could probably compute digits of the Champernowne constant in constant time... –  J. M. Jul 14 '12 at 1:54
1  
Champernowne's constant can be computed in real-time. See rjlipton.wordpress.com/2012/06/04/…. –  Jeremy Hurwitz Jul 15 '12 at 21:55
add comment

2 Answers

This is basically the Hartmanis-Stearns Conjecture, and it is a major open question. The basic difference between your question and the Conjecture is basically a formalization of "constant time". See http://rjlipton.wordpress.com/2012/06/04/transcendental-aspects-of-turing-machines/ and http://rjlipton.wordpress.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/ for lots of discussion on the topic.

In a nutshell, the Hartmanis-Stearns Conjecture considers the complexity of computing the next digit in the decimal expansion. Rather than taking $n$ as an input and outputting the $n$-th digit (as you propose), the machine prints the decimal expansion forever. The catch is that it must print the digits at a constant rate. This is known as being computable in "real time".

The HS Conjecture says that any such number is either rational or transcendental.


Let's take a look at your two claims.

For any rational number (and its decimal form), it costs constant time to calculate its any digit;

The intuition behind this is that any rational number's decimal expansion is eventually periodic. In other words, there is a fixed prefix, followed by a repeating pattern forever. So to output the $n$th digit, we have two cases. If $n$ is within the initial prefix, we output that digit (from a pre-computed table). Otherwise, we compute $n \bmod p$ and return that element of the repeating pattern.

Unfortunately, this is not technically "constant time". Both checking if $n$ is within the prefix and computing $n\bmod p$ require time $O(\log n)$ since you have to read every bit.

In the HS version, the machine can remember its location between digits. It therefore only has to increment a pointer -- either move to the next spot in the pre-computed table or move to the next location in the repeating pattern. These are both actually constant time operations.

Conversely, given a number, if it costs constant time to calculate its any digit, it is a rational number.

Again, we run into technicalities of what exactly constant-time means. Under many reasonable encoding schemes for $n$ (ie, little-endian binary) this does indeed imply rationality.

Other reasonable encodings (ie, big-endian binary) yield transcendental numbers. Consider the number whose $n$-th binary digit is 0 iff the second bit in $n$ (written in big-endian binary) is 0. This number is clearly not periodic, since the runs keep increasing in length, so it's not rational. In fact, it's actually transcendental.


Note that the Hartmanis-Stearns conjecture does not claim that every transcendental number can be printed in real time. I don't have a counter-example handy (please leave a comment if you do!)

Another issue is that the HS conjecture allows for extremely-complicated calculations for some digits, provided that they are preceded by a sufficiently-long trivial stretch. Converting the big-endian example above into the real-time formalism uses this trick, for example. However, if you view the theorem as a negative statement about computing irrationals, then the loophole actually strengthens the conjecture (since more potential algorithms are legal).

Another way of formalizing constant time is the word-model. In this model, basic integer operations ($+$, $-$, $<$, $=$, etc) are considered constant time. I don't know what the status of the conjecture is in that model. (Pointers greatly appreciated!)

share|improve this answer
add comment

One candidate of an irrational that is easy to calculate the digits is $\sum_{i=1}^{\infty} \frac {1}{2^{2^i}}$ (assuming you want binary. If not change 2 to 10). I have seen on these pages that you can't even read in $n$ in constant time-it has $\log n$ bits. Given that you can read in $n$, just remove the first bit and check for equality with $0$. Whether you think that is constant time depends on your model of computation.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.