6
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ BBP might only be $n\log^3 n$. See the comments here cstheory.stackexchange.com/q/39855/129 $\endgroup$
    – Joshua Grochow
    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$
    – Joshua Grochow
    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$
    – Huck Bennett
    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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    Dec 11, 2020 at 7:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.