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?

  • 3
    $\begingroup$ BBP might only be $n\log^3 n$. See the comments here cstheory.stackexchange.com/q/39855/129 $\endgroup$ Dec 11, 2020 at 2:01
  • 3
    $\begingroup$ I don't think these answer it, but they're related and might be of interest: cstheory.stackexchange.com/q/31932/129 and cstheory.stackexchange.com/q/21787/129 $\endgroup$ Dec 11, 2020 at 2:03
  • 3
    $\begingroup$ See also rjlipton.wordpress.com/2010/07/14/… and 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. $\endgroup$ Dec 11, 2020 at 4:00
  • 6
    $\begingroup$ 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)$). $\endgroup$ Dec 11, 2020 at 7:09
  • 4
    $\begingroup$ 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.) $\endgroup$ Dec 11, 2020 at 7:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.