# Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe formula, there is a spigot algorithm for quickly computing in terms of any natural number $n$ expressed in binary the $n^{th}$ binary digit of $\pi$ after the decimal place in polynomial time. Combining information from the Wikipedia articles Computational complexity of mathematical operations and Fürer's algorithm, I figured out that there exists an algorithm that computes every digit of $\pi$ in order within the time $O(n (log(n))^2 2^{(2 log * n)})$ where $log*n$ is the super root of $n$ to the base 10. I also think that according to this answer, there is an algorithm that for any natural number $n$ computes with the binary notation of $n$ as input, the $n^{th}$ binary digit of $\pi$ after the decimal place in time $O(n^3(log(n))^3)$ of the number of binary digits of $n$.

I believe both of those algorithms have a decimal analogue. If so, it seems that using the Spigot algorithm for each decimal digit of $\pi$ one at a time is slower than doing other algorithm for computing all of the digits. You might be wondering how it's possible to compute it faster than can be done by using any Spigot algorithm on each digit one at a time. Because the faster method of computation keeps some of the statements it previously computed and uses it to shorten the length of time it takes to compute the next digit to less time than it would have taken using the spigot algorithm. My question is not "Is the asymptotically fastest way to compute all the decimal digits of $\pi$ in order faster than the method of computing all its decimal digits by using the asymptotically fastest spigot algorithm for $\pi$ for each digit one at a time in order?" The reason is because I haven't thought of a proof that an asymptotically fastest algorithm for either task even exists. Here are my 2 questions:

1. Is there an algorithm for computing all the decimal digits of $\pi$ that's asymptotically faster than every method by finding a spigot algorithm for a single decimal digit of $\pi$ and using it on every digit one at a time in order?
2. If not, then is the fastest way to grow a copy of all the decimal digits of $\pi$ up to a certain point bigger and bigger on Earth to use such a spigot algorithm.

In the real world, computers are a certain size so the spigot algorithm might save memory so it might be faster to do it using the spigot algorithm for that reason. On the other hand, the faster method might only require an amount of memory that varies as the log of the number of digits that have so far been computed.

The real meaning of question 2 is quite complex and depends on what people consider feasible to build so I can't figure out a way to explain really clearly what I mean by it, but I believe that even after showing that the answer to question 1 is no, it's still not easy to figure out whether the answer to question 2 is yes or no.

• Take a closer look at your last link. It refers to generating decimal digits. Aug 14 '18 at 2:38
• @YuvalFilmus If give permission for anyone to edit this question into a different but similar question by rewriting it entirely if they think they can make it into a better clearer question that way. This question might turn out to be understandable by some high memory experts with certain knowledge but it might be completely impossible to write a similar question to this one in such a way that way more people can read it and understand it. Aug 14 '18 at 2:49

## 1 Answer

There is no known method to calculate individual decimal digits of pi quickly. And fast methods for calculating the first n digits of pi in base b are considerably faster than using a method to calculate the k-th digit n times.