$\pi$

Generating $\pi$

Reading about how one can calculate $\pi$ with a computer programm, I stumbled on the Paper Unbounded Spigot Algorithms for the Digits of Pi by Jeremy Gibbons (from 2005). In this Paper he's dealing with a special kind of algorithms for computing $\pi$. These are so called spigot algorithms. They are called this because they can yield digits while they are still computing. In this way the output comes like droplets from a spigot. Gibbons specializes even further to unbounded spigot algorithms. He describes them as follows:

"No commitment need be made in advance to the number of digits to be computed; given enough memory, the programs will generate digits ad infinitum."

One such algorithm he provides is the following one written in Haskell:

pi = g(1,0,1,1,3,3) where
    g(q,r,t,k,n,l) = if 4*q+r-t < n*t
    then n : g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)
    else g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)

I translated the code into Python and rewrote it as an iterative algorithm. Due to the features of spigot algorithms it's very natural to implement it as a generator function:

def pi():
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4 * q + r - t < n * t:
            yield n
            q, r, t, k, n, l = 10 * q, 10 * (r - n * t), t, k, (10 * (3 * q + r)) // t - 10 * n, l
        else:
            q, r, t, k, n, l = q * k, (2 * q + r) * l, t * l, k + 1, (q * (7 * k + 2) + r * l) // (t * l), l + 2

Using this one can as an trivial example print the digits while they are generated:

for d in pi(): print(d, end="")

Note that this code doesn't print the ".", it prints 31415...

This very plump translation can be optimized to run faster. First one can remove the useless assignments:

def pi():
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4 * q + r - t < n * t:
            yield n
            q, r, n = 10 * q, 10 * (r - n * t), (10 * (3 * q + r)) // t - 10 * n
        else:
            q, r, t, k, n, l = q * k, (2 * q + r) * l, t * l, k + 1, (q * (7 * k + 2) + r * l) // (t * l), l + 2

Secondly some assignments can be done after another saving memory and increasing the speed:

def pi():
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4 * q + r - t < n * t:
            yield n
            r, n = 10 * (r - n * t), (10 * (3 * q + r)) // t - 10 * n
            q *= 10
        else:
            t *= l
            n = (q * (7 * k + 2) + r * l) // t
            r = (2 * q + r) * l
            q *= k
            k += 1
            l += 2

Cry$\pi$tography

A funny application for this generator is to search for a specific number like 42 (at the 92th and 93th digit of $\pi$), 161 (at the 1610th to 1612th digit of $\pi$), 1337 (at the 4813th to 4816th digit of $\pi$), 666 (at the 2440th to 2442th digit of $\pi$), 1323 (at the 2677th to 2680th digit of $\pi$) or ones birthday in the digits of $\pi$.

With this method one can encrypt numbers (and by first encoding letters to number also text) into pi. The cipher in this case is the number of the digits of $\pi$ which form the number one wants to store.

For example 15 decodes to 3,2 meaning: Start at the 3th digit, take two digits.
3.141592...
About the counting: The initial 3 in front of the "." is the 0th digit.

One can implement this Algorithm as follows:

def piSearch(number: int|str):
    searchDigits = str(number)

    curr = []
    for i, d in enumerate(pi()):
        curr.append(str(d))
        if len(curr) > len(searchDigits):
            curr.pop(0)

        if "".join(curr) == searchDigits:
            return i - len(searchDigits) + 1

Note that this is dealing with the digits as string. This allows searching for e.g. "007" which is thereby not mistaken as "7".

Here you can try this kind of encryption:

Although JavaScript has arbitrary precision arithmetic in form of the BigInt for practical purposes BigInt is limited by most JS-engines. Hence it might happen this tool stops working at some point depending on your browser.

By generating pi up to the place one got by encrypting it one can decrypt it again. This is even more simple then the encryption:

def piGet(index: int, digitsCount: int):
    res = ""
    for i, d in enumerate(pi()):
        if i >= index:
            res += str(d)
            if len(res) >= digitsCount:
                return res

Here you can try it yourself:

The same limitation is holds for this one.