7
$\begingroup$

Can we evaluate any single decimal digit of pi even we skip to evaluate the digit before it?

1 Answers 1

5

Yes; see for example the Wikipedia page on calculating pi, particularly the "digit extraction" section (to which I linked).

  • 0
    Even the digit is in binary,it is awesome!2011-07-22
  • 2
    This answer should say "yes, if by 'digit' you mean bit". Note that OP asked for **decimal digit** and as far as I know, that's an unsolved problem...2011-07-22
  • 7
    @R..: If you'll see the Wikipedia page, Plouffe derived an algorithm to obtain the $n$th digit of $\pi$ in *arbitrary base*, subsequently improved by Bellard to work in $O(n^2)$.2011-07-22
  • 0
    Cool, I'd glanced at the linked section but just missed the very end.2011-07-22
  • 2
    For searching purposes: it's the so-called *spigot* algorithm.2011-07-22
  • 0
    An $O(n^2)$ algorithm to compute the $n$th digit could possibly cheat, by secretly computing *all* the previous digits as an intermediate step. For instance, imagine that it writes down the $k$th digit, given all previous ones, in $O(k)$ additional time. Do we know that this isn't the case with this particular (arbitrary base) algorithm?2011-07-22
  • 2
    @Srivatsan: The Wikipedia page includes a link to the paper by Bellard. You can check the description of the algorithm there.2011-07-22
  • 0
    There is currently no fast algorithm (record breaking) to obtain decimal digits.2016-03-21