# Intuitive explanation of Bailey-Borwein-Plouffe $\pi$ extraction formula?

First, I should clarify, I'm not a mathematician. I don't study maths at college, so my knowledge of maths is sketchy at best.

I've been looking with interest at the Bailey-Borwein-Plouffe formula for calculating the nth digit of $\pi$, and I've been trying to work out how to code this in Visual Basic, with little success. I've been looking everywhere to try and understand the formula, but no one seems to provide simple or intuitive explanations - it seems rather niche, I guess. I'm also a little confused at the nature of the formula. I understand that it's a spigot algorithm, which apparently either calculates a sequence of decimals or extracts an nth-digit, but the Wikipedia page is confusing me, it seems to be describing both kinds of algorithm and I'm not sure what the direct formula does.

Would anyone be willing to try and explain the formula with a worked example, for example if $n = 4$? And am I right in thinking that using this formula correctly with $n$ as $4$ would return $5$, the fourth decimal digit?

-

for intuition look at the way they use factorial base for $e = \sum_{n=1}^\infty \frac{1}{n!}$ here, $\pi$ is similar but less simple.

-
That doesn't really help me much... I'm not a maths student, remember. I don't understand the use of e, or the significance of the factorial base. – Leo King Feb 28 '13 at 22:28
I don't know what to say.. why are you asking this question? what do you actually want – user58512 Feb 28 '13 at 22:35
Well eventually I want to set up a Visual Basic code using the BBP formula to calculate an nth digit of pi but first I want to understand in more detail how the formula works... I'd really appreciate it if you were able to show what the formula is doing using a worked example :) – Leo King Feb 28 '13 at 23:39

"Spigot algorithm" appears to be somewhat vague, possibly referring to any of three different classes of algorithms:

1. Any algorithm which can compute successive digits, storing only a constant amount of state information. The possibly first spigot algorithm for π from Rabinowitz and Wagon is in this class; it seems that they coined the term "spigot algorithm" to describe this algorithm.
2. An algorithm which can compute arbitrarily many successive digits, storing only a constant amount of state information. The improved spigot algorithm for π from Gibbons is in this class; it seems that he coined the term "streaming algorithm" to emphasize the improvement.
3. An algorithm which can compute any arbitrary digit, without any state information. The BBP formula corresponds to an algorithm in this class; many sources refer to this class as "digit extraction algorithms".

The algorithm corresponding to the BBP formula is a spigot algorithm, but it is more than just a spigot algorithm, it is a digit extraction algorithm. Most search results for "spigot algorithm" are about the algorithm for π from Rabinowitz and Wagon, which is not a digit extraction algorithm.

If I understand correctly, all digit extraction algorithms correspond to BPP-type formulas, which have this form: $$\alpha = \sum_{k=1}^{\infty}{\frac{f(k)}{b^k}}$$

Each term of this sum has a factor of $b^{-k}$, so this sum basically takes the values of $f(k)$ and uses them as the fractional digits of $\alpha$ in base $b$. The hard part of finding a digit extraction algorithm is finding the $f(k)$ to make a BPP-type formula.

The original BPP formula for π has $b=16$, so it has an $f(k)$ that generates hexadecimal digits, not decimal digits. Plouffe is said to have derived a digit extraction algorithm for arbitrary bases, but I did not find any explicit expression of it and did not understand the one description I did find. It is not a BPP-type formula, but presumably can be used to derive BPP-type formulas.

While the BPP formula allows calculation of an arbitrary digit in less time than would be needed to calculate all preceding digits, the time per digit is higher. To calculate a sequence starting with the nth digit, it would be faster to use a non-extractor spigot for digits after the nth digit.

The non-extractor spigots are not so base-specific. Because they have some running state, you can essentially keep a running base conversion and get the output in whatever base you want. The Rabinowitz and Wagon algorithm seems to use the factorial number system, which effectively requires a number system conversion for any fixed base.

I'm not sure how "intuitive" they are, but I found two explanations of the Rabinowitz and Wagon algorithm that don't appear to require an extensive mathematical background:

An implementation (in C) is given in this answer.

-

The story began many years ago in 1974 when I wanted to find a formula for the n'th digit of Pi. I was studying rational and irrational numbers. With my calculator I was computing inverses of primes and could easily find a way to compute those inverses in base 10 to many digits using congruences and rapid exponentiation. Since it appeared impossible to do the same for Pi, I wanted then to find a simple formula f(n) that could compute the n'th digit of Pi. I had that idea for 20 years. Simon Plouffe

There is an algorithm of Fabrice Bellard, a refinement of Plouffe's algorithm, that computes the nth digit of $\pi$ in any number base.

I know this is not exactly what you asked for, but if the purpose of your question was to create an algorithm I think this is the answer.

-