<p>I (only) learned today about the following fact:</p>
<blockquote>
<p>The <span class="math-container">$n$</span>-th binary digit of <span class="math-container">$\pi$</span> is computable without calculating all the previous digits.</p>
</blockquote>
<p>This apparently has been discovered in 1995, and follows from the <a href="https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula" rel="noreferrer">Bailey—Borwein—Plouffe formula</a>:
<span class="math-container">$$
\pi = \sum_{n=0}^\infty \frac{1}{16^n}\left(\frac{4}{8n+1}-\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right)
$$</span>
This in turn leads to <a href="https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula#BBP_digit-extraction_algorithm_for_%CF%80" rel="noreferrer">an <span class="math-container">$O(n\log n)$</span>-time algorithm</a> to compute the <span class="math-container">$n$</span>-th digit of the hexadecimal expansion of <span class="math-container">$\pi$</span> (and so also of the binary one), interestingly <em>without computing the intermediate ones</em>. (Interestingly too, it's apparently unknown how to do that for the base-10 expansion.)</p>
<p>My question, out of sheer curiosity, is whether anything better is known? Either deterministically or in a randomized fashion, what is the fastest algorithm known for the task <em>&quot;given <span class="math-container">$n$</span> as input, compute the <span class="math-container">$n$</span>-th digit of the binary expansion of <span class="math-container">$\pi$</span>&quot;</em>? (Also, is there any lower bound?)</p>
<p>Also, is there any interesting application/implication?</p>

CC BY-SA 4.0
2020-12-11T02:01:35.483Z
BBP might only be $n\log^3 n$. See the comments here https://cstheory.stackexchange.com/q/39855/129
Joshua Grochow
CC BY-SA 4.0
2020-12-11T02:03:40.740Z
I don't think these answer it, but they're related and might be of interest: https://cstheory.stackexchange.com/q/31932/129 and https://cstheory.stackexchange.com/q/21787/129
Joshua Grochow
CC BY-SA 4.0
2020-12-11T02:39:25.480Z
Mumble mumble something about Hartmanis-Stearns real-time computability Conjecture mumble mumble
Joshua Grochow
CC BY-SA 4.0
2020-12-11T03:04:43.350Z
Interesting... why is Wikipedia stating $O(n\log n)$ if the original paper has a larger bound? That seems sloppy.
Clement C.
CC BY-SA 4.0
2020-12-11T04:00:50.950Z
See also https://rjlipton.wordpress.com/2010/07/14/making-an-algorithm-an-algorithm-bbp/ and https://cs.nyu.edu/exact/doc/pi-log.pdf. The latter fixes a purported gap in BBP and argues that the $n$th bit can be computed in logspace.
Huck Bennett
CC BY-SA 4.0
2020-12-11T07:09:03.300Z
Note that using standard methods that *do* compute the intermediate digits, you can compute the first $n$ digits of $\pi$ all at once in time $O(M(n)\log n)=O(n(\log )^2)$. In contrast, BBP needs about that time to compute a *single* digit. Thus, it has a rather abysmal performance *timewise*. In terms of complexity, the only advantage of the BBP is with respect to *space*: you can compute the $n$th digit in space $O(\log n)$ (whereas the traditional methods require space $O(n)$).
Emil Jeřábek
CC BY-SA 4.0
2020-12-11T07:27:54.607Z
Thanks for all the clarifications!
Clement C.
CC BY-SA 4.0
2020-12-11T07:35:46.200Z
I should perhaps stress that the existence of a $O(\log n)$-space algorithm does not require the BBP algorithm either, there are other methods. In particular, $\pi$, and other functions and constants expressible by sufficiently nice Taylor series for that matter, can be computed (that is, approximated) in uniform $\mathrm{TC}^0$, and therefore in log-space. (However, the algorithm obtained this way would require a lot of time, albeit still polynomial.)
Emil Jeřábek
CC BY-SA 4.0
2020-12-11T07:40:02.607Z
So, the main 'feature' of the BBP algorithm (or its "corrected" variants, following Huck's comment) is really the fact that it does not compute previous digits? Is there no other advantage to it?
Clement C.
CC BY-SA 4.0
2020-12-13T23:47:31.917Z
I believe so, but you have to admit that being able to compute digits arbitrarily far out wihtout computing the previous digits is an amazing "feature". And the space advantage of BBP pointed out by @EmilJeřábek can well be of practical value.
kodlu
<time-complexity>
Computing the $n$-th bit of the binary representation of $\pi$
Clement C.
# Computing the $n$-th bit of the binary representation of $\pi$

(Asked by: username_0 on 2020-12-10)

I (only) learned today about the following fact:

> The $n$-th binary digit of $\pi$ is computable without calculating all the previous digits.

This apparently has been discovered in 1995, and follows from the [Bailey—Borwein—Plouffe formula](https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula):
$$
\pi = \sum\_{n=0}^\infty \frac{1}{16^n}\left(\frac{4}{8n+1}-\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right)
$$
This in turn leads to [an $O(n\log n)$-time algorithm](https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula#BBP_digit-extraction_algorithm_for_%CF%80) to compute the $n$-th digit of the hexadecimal expansion of $\pi$ (and so also of the binary one), interestingly *without computing the intermediate ones*. (Interestingly too, it's apparently unknown how to do that for the base-10 expansion.)

My question, out of sheer curiosity, is whether anything better is known? Either deterministically or in a randomized fashion, what is the fastest algorithm known for the task *"given $n$ as input, compute the $n$-th digit of the binary expansion of $\pi$"*? (Also, is there any lower bound?)

Also, is there any interesting application/implication?

**Tags:** time-complexity
> **Comments:**
> **username_1**: BBP might only be $n\log^3 n$. See the comments here https://cstheory.stackexchange.com/q/39855/129  
> **username_1**: I don't think these answer it, but they're related and might be of interest: https://cstheory.stackexchange.com/q/31932/129 and https://cstheory.stackexchange.com/q/21787/129  
> **username_1**: Mumble mumble something about Hartmanis-Stearns real-time computability Conjecture mumble mumble  
> **username_0**: Interesting... why is Wikipedia stating $O(n\log n)$ if the original paper has a larger bound? That seems sloppy.  
> **username_2**: See also https://rjlipton.wordpress.com/2010/07/14/making-an-algorithm-an-algorithm-bbp/ and https://cs.nyu.edu/exact/doc/pi-log.pdf. The latter fixes a purported gap in BBP and argues that the $n$th bit can be computed in logspace.  
> **username_3**: Note that using standard methods that *do* compute the intermediate digits, you can compute the first $n$ digits of $\pi$ all at once in time $O(M(n)\log n)=O(n(\log )^2)$. In contrast, BBP needs about that time to compute a *single* digit. Thus, it has a rather abysmal performance *timewise*. In terms of complexity, the only advantage of the BBP is with respect to *space*: you can compute the $n$th digit in space $O(\log n)$ (whereas the traditional methods require space $O(n)$).  
> **username_0**: Thanks for all the clarifications!  
> **username_3**: I should perhaps stress that the existence of a $O(\log n)$-space algorithm does not require the BBP algorithm either, there are other methods. In particular, $\pi$, and other functions and constants expressible by sufficiently nice Taylor series for that matter, can be computed (that is, approximated) in uniform $\mathrm{TC}^0$, and therefore in log-space. (However, the algorithm obtained this way would require a lot of time, albeit still polynomial.)  
> **username_0**: So, the main 'feature' of the BBP algorithm (or its "corrected" variants, following Huck's comment) is really the fact that it does not compute previous digits? Is there no other advantage to it?  
> **username_4**: I believe so, but you have to admit that being able to compute digits arbitrarily far out wihtout computing the previous digits is an amazing "feature". And the space advantage of BBP pointed out by @EmilJeřábek can well be of practical value.  

---

## 0 answers

