Can we evaluate any single decimal digit of pi even we skip to evaluate the digit before it?
Can we evaluate the any single decimal digit of pi even we skip the digit before it?
7
$\begingroup$
algorithms
pi
sequences-and-series
1 Answers
5
Yes; see for example the Wikipedia page on calculating pi, particularly the "digit extraction" section (to which I linked).
-
0Even the digit is in binary,it is awesome! – 2011-07-22
-
2This 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
-
0Cool, I'd glanced at the linked section but just missed the very end. – 2011-07-22
-
2For searching purposes: it's the so-called *spigot* algorithm. – 2011-07-22
-
0An $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
-
0There is currently no fast algorithm (record breaking) to obtain decimal digits. – 2016-03-21