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](https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula#BBP_digit-extraction_algorithm_for_%CF%80)) 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.



Can we compute the first $n$ digits of $\pi$ in $F(n)$ time?
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 π.](https://www.elibm.org/ft/10012144000) Nederl. Akad. Wetensch.
Proc. Ser. A 56=Indag. Math., 15:30–42, 1953.


