8
$\begingroup$

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?

  • 1
    One could probably compute digits of the Champernowne constant in constant time...2012-07-14
  • 1
    Champernowne's constant can be computed in real-time. See http://rjlipton.wordpress.com/2012/06/04/transcendental-aspects-of-turing-machines/.2012-07-15

2 Answers 2