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

Question

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

Answer 1

($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)$}$\;\;\;$.
To avoid that general trick, one should probably impose a sublinear space bound.