|
Post Made Community Wiki by S. Carnahan♦
|
||||
|
|
||||
|
3 | added 488 characters in body | ||
|
There are reasons that any modern example is likely to resemble the status of Legendre's constant. Most (but not all) interesting numbers admit a polynomial-time algorithm to compute their digits. In fact, there is an interesting semi-review by Borwein and Borwein that shows that most of the usual numbers in calculus (for example, $\exp(\sqrt{2}+\pi)$) have a quasilinear time algorithm on a RAM machine, meaning $\tilde{O}(n) = O(n(\log n)^\alpha)$ time to compute $n$ digits. Once you have $n$ digits, you can use the continued fraction algorithm to find the best rational approximation with at most $n/2-O(1)$ digits in the denominator. The continued fraction algorithm is equivalent to the Euclidean algorithm, which also has a quasilinear time version according to Wikipedia. Euler's constant has been to computed almost 30 billion digits, using a quasilinear time algorithm due to Brent and McMillan. As a result, for any such number it's very difficult to be surprised. You would need a mathematical coincidence that the number is rational, but with a denominator that is out of reach for modern computers. (This was Brent and MacMillian's stated motivation in the case of Euler's constant.) I think that it would be fairly newsworthy if it happened. On the other hand, if you can only compute the digits very slowly, then your situation resembles Legendre's. I got e-mail asking for a reference to the paper of Borwein and Borwein. The paper is On the complexity of familiar functions and numbers. To summarize the relevant part of this survey paper, any value or inverse value of an elementary function in the sense of calculus, including also hypergeometric functions as primitives, can be computed in quasilinear time. So can the gamma or zeta function evaluated at a rational number. |
||||
|
2 | deleted 47 characters in body | ||
|
There is a mathematical and social reason are reasons that any modern example is likely to resemble the status of Legendre's constant. Most (but not all) interesting numbers admit a polynomial-time algorithm to compute their digits. In fact, there is an interseting old interesting semi-review by Borwein and Borwein that shows that most of the usual numbers in calculus (for example, $\exp(\sqrt{2}+\pi)$) have a quasilinear time algorithm on a RAM machine, meaning $\tilde{O}(n) = O(n(\log n)^\alpha)$ time to compute $n$ digits. Then, once Once you have $n$ digits, you can use the Euclidean algorithm / continued fractions fraction algorithm (and even that is quasilinear time, according to Wikipedia) to find the best rational approximation with at most $n/2-O(1)$ digits in the denominator. The continued fraction algorithm is equivalent to the Euclidean algorithm, which also has a quasilinear time version according to Wikipedia. Euler's constant is known has been to computed almost 30 billion digits, which suggests using a quasilinear time algorithm . (The description in the algorithm paper by due to Brent and MacMillian confirms this.)McMillan. As a result, for any such number it's very difficult to be surprised. You would need a mathematical coincidence that the number is rational, but with a denominator that is out of reach for modern computers. (Indeed, this This was exactly Brent and MacMillian's stated motivation in the case of Euler's constant.) I think that it would be fairly newsworthy if it happened. On the other hand, if you can only compute the digits very slowly, then your situation resembles Legendre's. |
||||
|
1 |
|
||

