6

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: $$ \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 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?

Clement C.
  • 4,461
  • 29
  • 51
  • 3
    BBP might only be $n\log^3 n$. See the comments here https://cstheory.stackexchange.com/q/39855/129 – Joshua Grochow Dec 11 '20 at 02:01
  • 3
    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 Dec 11 '20 at 02:03
  • Mumble mumble something about Hartmanis-Stearns real-time computability Conjecture mumble mumble – Joshua Grochow Dec 11 '20 at 02:39
  • Interesting... why is Wikipedia stating $O(n\log n)$ if the original paper has a larger bound? That seems sloppy. – Clement C. Dec 11 '20 at 03:04
  • 3
    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 Dec 11 '20 at 04:00
  • 6
    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 Dec 11 '20 at 07:09
  • Thanks for all the clarifications! – Clement C. Dec 11 '20 at 07:27
  • 4
    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 Dec 11 '20 at 07:35
  • 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. Dec 11 '20 at 07:40
  • 2
    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 Dec 13 '20 at 23:47

0 Answers0