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?