<p>What is the smallest function $t(n)$ such that there exists an algorithm which prints the binary digits of $\pi$, with the time spent between printing digit $n - 1$ and digit $n$ being $O(t(n))$?</p>

<p>Since the $n$th bit of $\pi$ <a href="http://numbers.computation.free.fr/Constants/Algorithms/nthdecimaldigit.pdf" rel="nofollow">can be computed in $O(n \log^3 n)$ time</a> by itself, we can trivially take $t(n)$ to be $n \log^3 n$. But we can hope that $t(n)$ can be much smaller, since we get to "reuse" all of the computations which gave us the previous bits. In fact, I don't see how to rule out $t(n) = 1$.</p>

<p>Also, what is the name of this "mode" of computation, where we are listing out the terms of an infinite sequence? It's a little like streaming, but backward...</p>

<cc.complexity-theory><ds.algorithms>
Algorithms for printing the digits of pi, minimizing the time spent between digits
William Hoza
# Algorithms for printing the digits of pi, minimizing the time spent between digits

(Asked by: username_0 on 2015-07-07)

What is the smallest function $t(n)$ such that there exists an algorithm which prints the binary digits of $\pi$, with the time spent between printing digit $n - 1$ and digit $n$ being $O(t(n))$?

Since the $n$th bit of $\pi$ [can be computed in $O(n \log^3 n)$ time](http://numbers.computation.free.fr/Constants/Algorithms/nthdecimaldigit.pdf) by itself, we can trivially take $t(n)$ to be $n \log^3 n$. But we can hope that $t(n)$ can be much smaller, since we get to "reuse" all of the computations which gave us the previous bits. In fact, I don't see how to rule out $t(n) = 1$.

Also, what is the name of this "mode" of computation, where we are listing out the terms of an infinite sequence? It's a little like streaming, but backward...

**Tags:** cc.complexity-theory, ds.algorithms


---

## 0 answers

