13
$\begingroup$

I've seen various fast algorithms for computing the first few, or directly the $n$-th, digits of $\pi$. However, it seems to me that all these algorithms assume (see last sentence here) that there are no very long carries in the computation, which I'm sure would follow from certain conjectures in number theory, but are not proven yet. So my question is:

What is the best known $F(n)$ for which the first $n$ digits of $\pi$ can be computed in $F(n)$ steps?

As was pointed by Arno in a comment, some computable $F(n)$ needs to exist, but I would like a specific bound. Of course, if anyone has a polynomial bound on $F(n)$, that would be best.

Improve this question
$\endgroup$
4
  • $\begingroup$ As $\pi$ is a computable real, there clearly is a computable such $F$, given by "Run an algorithm for $\pi$ and count how many steps it takes to provide the $n$-th digit". It's only once you move to lower runtimes that getting digits vs getting approximations makes a difference. $\endgroup$
    – Arno
    Commented Nov 1, 2022 at 15:12
  • $\begingroup$ You are right, this should follow from $\pi$ not being a rational number. I'll modify my question to ask for a specific bound. $\endgroup$
    – domotorp
    Commented Nov 1, 2022 at 15:35
  • $\begingroup$ Can you specify what model of computation you're using? $\endgroup$
    – Sam Hopkins
    Commented Nov 1, 2022 at 15:41
  • 1
    $\begingroup$ I don't think that matters much, take your favorite standard computational model. $\endgroup$
    – domotorp
    Commented Nov 1, 2022 at 16:07

1 Answer 1

Reset to default
18
$\begingroup$

Mahler proved(1) that for any $p,q$, $\left | \pi -\frac{p}{q} \right| > \frac{1}{q^{42}}$. It follows that if one can compute $2^{ 42n} \pi$ to within an error of at most $1$, one can compute the first $n$ digits of $\pi$, since the only way the knowledge of $2^{42n}\pi$ to within an error of $1$ would not be determinative is if $ \left|\pi - \frac{p}{2^n } \right| \leq \frac{1}{ 2^{42n}}$.

So running an algorithm "assuming there are no long carries" to compute the first $42n$ digits will suffice unconditionally to compute the first $n$ digits.

(1): K. Mahler. On the approximation of π. Nederl. Akad. Wetensch. Proc. Ser. A 56=Indag. Math., 15:30–42, 1953.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ So, in particular, $F(n)=O(M(n)\log n)=O(n(\log n)^2)$ using the Brent-Salamin $\pi$ algorithm and the Harvey-van der Hoeven multiplication algorithm. $\endgroup$
    – Emil Jeřábek
    Commented Nov 1, 2022 at 16:34
  • $\begingroup$ Can you give a reference for that Mahler's result? $\endgroup$
    – Somnium
    Commented Nov 1, 2022 at 20:41
  • 1
    $\begingroup$ @Somnium Added a ref. $\endgroup$
    – Will Sawin
    Commented Nov 1, 2022 at 23:54
  • 1
    $\begingroup$ The state of art is arxiv.org/abs/1912.06345 . $\endgroup$
    – Emil Jeřábek
    Commented Nov 2, 2022 at 6:22
  • 1
    $\begingroup$ @EmilJeřábek Yes, although the advantage of Mahler's result is that it's totally explicit (no "$q$ sufficiently large"), which seems to be a requirement of the question. Probably the later results can be made totally explicit also but this hasn't been done. $\endgroup$
    – Will Sawin
    Commented Nov 2, 2022 at 11:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .