Micro-challenge: Special Event

[Thomas Klemm]

(12-24-2022 07:20 PM)Albert Chan Wrote:  BTW, radix can be non-integers too.

This example is from \(\pi\) Unleashed.

Quote:6.1 The spigot algorithm in detail

(…)

But occasionally we come across numbers in which this factor is not constant,
e.g. the numbers which correspond to the expression "2 weeks, 3 days, 4 hours and 5 minutes".
Because the ratio of weeks to days = 1 : 7, days to hours = 1 : 24 and hours to minutes = 1 : 60,
when converting this number to a decimal number (with the unit "weeks"),
three different factors have to be considered, namely 1/7, 1/24 and 1/60.
Hence, to answer the question how many weeks are in the example, we have to calculate the following:

\(
\begin{align}
2 + \frac{1}{7}\left(3 + \frac{1}{24}\left(4 + \frac{1}{60}\left(5\right)\right)\right)
\end{align}
\)

The Spigot algorithm makes it possible to calculate the base-10 representation digit by digit.
In each step, the "digits" are multiplied by 10 and divided by their basis.

Quote:On every division, the remainder is retained and the integer quotient is carried over to the next decimal place.

Here's a Python program that does this:

Code:

def spigot(d, b, n):
    z = []
    for _ in range(n):
        for i in range(len(d)):
            d[i] *= 10
        for i in range(len(d)-1, 0, -1):
            d[i-1] += int(d[i] / b[i])
            d[i] %= b[i]
        z.append(int(d[0] / b[0]))
        d[0] %= b[0]
    return z

Example

Code:

b = [7, 24, 60]
d = [3, 4, 5]

spigot(d, b, 20)

Code:

[4, 5, 2, 8, 7, 6, 9, 8, 4, 1, 2, 6, 9, 8, 4, 1, 2, 6, 9, 8]

Compare this to the calculated value:

Code:

2.45287 698412 698412 69841 …

Keep in mind that the initial digit 2 is omitted.

We can list the intermediate results and see how the calculation becomes periodic:

Code:

[3, 16, 50]
[2, 0, 20]
[6, 3, 20]
[5, 9, 20]
[4, 21, 20]
[6, 21, 20]
[5, 21, 20]
[2, 21, 20]
[0, 21, 20]
[1, 21, 20]
[4, 21, 20]
[6, 21, 20]
[5, 21, 20]
[2, 21, 20]
[0, 21, 20]
[1, 21, 20]
[4, 21, 20]
[6, 21, 20]
[5, 21, 20]
[2, 21, 20]

Calculating Digits of \(\pi\)

Here's the interesting relation to \(\pi\):

\(
\begin{align}
\pi = 2 + \frac{1}{3}\left(2 + \frac{2}{5}\left(2 + \frac{3}{7}\left(2 + \cdots \right)\right)\right)
\end{align}
\)

Thus we can write in this specific basis: \(\pi = 2.2222\cdots\).

We can use the same function to calculate \(\pi\) digit by digit:

Code:

from mpmath import mp

n = 20
N = 10 * n // 3 + 1
mp.dps = n

b = [mp.mpf(2*k+1)/k for k in range(1, N+1)]
d = [2] * N

spigot(d, b, n)

Code:

[11, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6]

Imperial Units

There are many ways to use this algorithm when it comes to converting imperial units:

---

Warning: I've skipped over some details. So I recommend using a proper implementation instead of my Python program if you want to calculate more digits of \(\pi\).