6
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.