October 29th
Today I learned the spigot algorithm for hexadecimal digits of $\pi.$ We begin with the formula\[\pi=\sum_{k=0}^{\infty}\frac1{16^k}\left(\frac4{8k+1}-\frac2{8k+4}-\frac1{8k+5}-\frac1{8k+6}\right).\]This is a computational result found by computer and whose proof I've read but is quite unexciting. For those who care, check here .
Now, let's say we want the $n$th hexadecimal digit after the hexadecimal point. This is equivalent to computing $\floor{16^n\pi}\pmod{16}.$ For this, we actually look at \[\floor{16\left\{16^{n-1}\pi\right\}},\]which is the same value, but we moved the modulo into the fractional part. This is nice because we can write\[\left\{16^{n-1}\sum_{k=0}^\infty\frac1{16^k(8k+\ell)}\right\}=\left\{\sum_{k=0}^{n-1}\frac{16^{n-1}\pmod{8k+\ell}}{8k+\ell}+\sum_{k=n}^\infty\frac1{16^{n-1-k}(8k+\ell)}\right\}\]because fractional parts allows us to ignore most of that $16^{n-1}.$ The spigot speed-up is to to note that we can actually opt to compute $16^{n-1}\pmod{8k+\ell}$ using modular exponentiation instead of computing $16^{n-1},$ implying that the entire process of computing this sum is merely $O(n\log n).$
The second sum is supposedly small, and we can compute digits until we're confident that it can't affect current digits. This can't really be theoretical guaranteed because there's always a change we hit some long string of $9$s and need to continually hit more digits from each of the sums, but this is quite unlikely assuming $\pi$ normal.
So we can quickly approximate\[\left\{\sum_{k=0}^\infty\frac{16^{n-1}}{16^k(8k+\ell)}\right\}.\]Noting that\[\left\{16^{n-1}\pi\right\}=\left\{\left\{\sum_{k=0}^\infty\frac{4\cdot16^{n-1}}{16^k(8k+1)}\right\}-\left\{\sum_{k=0}^\infty\frac{2\cdot16^{n-1}}{16^k(8k+4)}\right\}-\left\{\sum_{k=0}^\infty\frac{16^{n-1}}{16^k(8k+5)}\right\}-\left\{\sum_{k=0}^\infty\frac{16^{n-1}}{16^k(8k+6)}\right\}\right\}\]means that we can quickly approximate $\left\{16^{n-1}\pi\right\},$ which lets us quickly extract individual nibbles.
Honestly I'm pretty unimpressed by this algorithm, but it does qualify as "spigot'' in that we got to ignore the nibbles before $n$ in our computation. However, we still have a few sums to worry about, and while we can be pretty sure in practice that these sums will not give us unbounded run times, it still makes me uncomfortable. So it goes.