# Algorithms for printing the digits of pi, minimizing the time spent between digits

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 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...

($M(n)$ is "the time required to perform precision $n$ multiplication.") $\:$ By page 10 of this paper,
a precision-$n$ approximation to $\pi$ can be computed in time $\;\; O\Big(\hspace{-0.04 in}M(n)\hspace{-0.02 in}\cdot \hspace{-0.02 in}\log(n)\hspace{-0.04 in}\Big) \;\;\;$.
By the very end of this paper, one can find a rational number $c$ such that for all $n$,
the first $n$ bits of $\pi$ are the first $n$ bits of every precision-$\hspace{-0.03 in}\lfloor (19.9\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)\hspace{-0.04 in}+\hspace{-0.04 in}c\rfloor$ approximation
of $\pi$, so the first $n$ bits of $\pi$ can be computed in time $\;\;\; O\Big(\hspace{-0.04 in}M(n) \cdot \hspace{-0.02 in}\log(n)\hspace{-0.04 in}\Big) \:\:\:\:$.
Thus, if $\Theta$$(M(n)\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)) has a time-constructible function, one can print \pi "with the time spent between printing digit" n\hspace{-0.04 in}-\hspace{-0.05 in}1 "and digit n being" \;\; O\Big(\hspace{-0.05 in}\big(\hspace{-0.02 in}M(n)\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)\hspace{-0.02 in}\big)\big/n\hspace{-0.04 in}\Big) \;\;, \;\; as follows: (Recall that the 0th and 1th bits of \pi are both "1".) \;\;\; Set \: i = 0 \: and \: t_{curr} =1 \: and output "1", then run the following loop forever. \;\;\; Compute [the first 2^{\hspace{.02 in}i+2} bits of \pi] and \big[\hspace{-0.02 in}an integer t_{next} in \Theta \hspace{-0.04 in}\left(\hspace{-0.02 in}M\hspace{-0.04 in}\left(\hspace{-0.02 in}2^i\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{-0.02 in}\right) such that t_{next} is an upper bound on the time it will take to compute t_{next} and those bits of \pi \big]. \: At the start of those computations, output the 2^i\hspace{-0.03 in}-th bit of \pi. Interleaved with those computations, output a bit of \pi approximately t_{curr}\hspace{-0.03 in}\big/\hspace{-0.02 in}2^i steps after outputting the previous bit of \pi. \: At the end of those computations, output the rest of the first 2^{\hspace{.02 in}i+1} bits of \pi, then increment i, set \: t_{curr} = t_{next} \:, \: and go back to the beginning of this loop. With the fastest known integer multiplication algorithm, that would achieve \;\;\; t\hspace{.02 in}(n) \: = \: (\log(n))^{\hspace{.02 in}2}\hspace{-0.05 in}\cdot 8$$\hspace{.02 in}\log^{\hspace{-.02 in}*}$$(n)$$\;\;\;$.