I know what the Bailey-Borweim-Plouffe Formula (BBP Formula) is—it's $\pi = \sum_{k = 0}^{\infty}\left[ \frac{1}{16^k} \left( \frac{4}{8k + 1} – \frac{2}{8k + 4} – \frac{1}{8k + 5} – \frac{1}{8k + 6} \right) \right]$— but how exactly do I use it to calculate a given digit of pi?
[Math] How to use the BBP Formula to calculate the nth digit of π
pisequences-and-series
Related Solutions
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.
In the stand-alone version of the programming language Lua, a function that calculates Pi using the plain BBP formula to the desired precision is below. If you do not know the programming language Lua, then there's a good chance you can understand it by ignoring the first and last lines ( the first and last lines are there for programming aesthetics ), thinking of the return as, "the end result is," and knowing that the for is the generic for loop ( i.e. very close to sigma symbol: for variable=initial, final, increment do body with variable set to the current iteration end ).
function( percision )
pi = 0
for k = 0, percision, 1 do
pi = pi + ((16^-k) * ( 4/(8 * k + 1) - 2/(8* k+4) - 1/(8 * k+5) - 1/(8 * k+6) ) )
end
return pi
end
But, there's a great limiting factor with this function: It can only calculate pi to a messily 10 digits ( because stand-alone lua uses Double-precision floating-point format ). So, the real thing this post is about is a Lua function that uses a slightly modified version of the BBP formula. This Modification to the BBP formula by essentially shifting down up the decimal place (please note that in Lua, the range of both functions presented in this post are the same, but this post does show an example of a way to work around difficulties in using the BBP formula and also please note that the, " 1 * shift " in the equation is there to show the modifications in the equation that were made ).
function(percision)
pi = 0
shift = percision ^ 10
for k = 0, percision, 1 do
pi = pi + ((16^-k) * ( (4 * shift )/(8 * k + 1) - ( 2 * shift )/(8* k+4) - ( 1 * shift )/(8 * k+5) - (1 * shift )/(8 * k+6) ) )
end
return pi
end
This basic principle can be applied to calculating Pi for real by making it so that far less decimal digits have to be computed while yielding better precision. However, if you were going to make this for real and you do understand this about hardware then you could save a HUGE amount of computing effort if you programmed it in a low level programming language like c++, and you changed the precision to an exponent of 2 (which could be 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 65536, 131072, 262144, ... ) so that you could then only have to count the number of bits, and multiply that number by the exponent to get the resulting number of bits.
Interbase math is exactly like regular math, it has all of the same properties, except it has a different radix or base, so it displays differently. Basically a core fundamental principle is that whenever the last digit on the number goes past the base number, it overflows into the next slot. For example, in base 8, octal, when you add 1 to 7, it becomes 8 which you carry onto the next slot to get 10 which is in octal, but if you converted it back to base 10 then it would be 8. The reason the BBP formula is so convenient is because when you calculate it in base 10 with a calculator, you get would-be hex gibberish so you have to convert it back to base 10 again. Whereas internal in computer hardware everything is computed in base 2, so the BBP formula actually saves the extra effort of converting PI to base 10 because the BBP formula would produce it pre-made ready to go in base 10 for us all to read.
On a person note, these are my favorite bases because of their algebraic symmetry. The more algebraically symmetrical a base it, the more easier it is to do more complex things because the simplicity of the base allows for easier conversions, more intuitive conventions, and an easier ability to manipulate data (the reason for this is rather complex because it can't really be spoken from fact, rather it can be spoken from experience).
- Base $4$
Because $4 = 2^2$ and the expression $2^2$ is perfectly symmetrical because it consists of 2 terms, each of which are 2. - Base $65536$
I don't like this as much as the other 2 because its not perfectly symmetrical. However, it does have the advantage (unlike the next) of us being able to comprehend it. It can be represented as $65536=2^{2^{2^2}}$ which means it is still very symmetrical because the number of 2 exponents is $4=2^2$, however it is still not pinpoint perfect. - Base $2^{13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096}\approx$
$10^{16144609452111090514334441274226029970131082121399509384912393635887695069756771104231368302164231425136015724934359162600354003567428775844746162570046507.91002177536}$
Even thou this base is currently incomprehensible even if you use all the computers in all the world, and probably never will be comprehensible, it is still nevertheless my favorite base. It can be represented by $4^{4^{4^4}}$ which gives it perfect geometric symmetry because it is 4 exponents of 4 plus the added benefit of $4=2^2$. I mean, I just love this base because you just can't get that kind of flawlessness until you get up into numbers that can't even be expressed by any means other than Knuth mans wonderful arrows.
Best Answer
The basic idea depends on the following easy result:
The $d+n$-th digit of a real number $\alpha$ is obtained by computing the $n$-th digit of the fractional part of $b^d \alpha$, in base $b$ . (fractional part denoted by $\lbrace \rbrace$.)
For instance: if you want to find the $13$-th digit of $\pi$ in base $2$, you must calculate the fractional part of $2^{12} \pi$ in base $2$.
$\lbrace2^{12} \pi\rbrace=0.\color{red} 1\color{blue} {111011}..._2$
hence $13$-th digit of $\pi $ is $\color{red} 1$.
$\pi=11.001001000011\color{red} 1\color{blue} {111011010101}..._2$
Now if we want to compute the $n+1$-th hexadecimal digit of $\pi$
we only need to calculate $\lbrace 16^{n} \pi\rbrace$
you can do this by using $BBP$ formula
$$\pi = \sum_{k = 0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right) $$
$$16^{n} \pi= \sum_{k = 0}^{\infty} \left( \frac{4 \cdot 16^{n-k}}{8k + 1} - \frac{2\cdot 16^{n-k}}{8k + 4} - \frac{ 16^{n-k}}{8k + 5} - \frac{16^{n-k}}{8k + 6} \right)$$
and
$$\lbrace 16^{n} \pi\rbrace=\bigg\lbrace\sum_{k = 0}^{\infty} \left( \frac{4 \cdot 16^{n-k}}{8k + 1} - \frac{2\cdot 16^{n-k}}{8k + 4} - \frac{ 16^{n-k}}{8k + 5} - \frac{16^{n-k}}{8k + 6} \right)\bigg \rbrace$$
Now let $S_j=\sum_{k=0}^{\infty} \frac{1}{16^k(8k+1)}$ then
$$\color{blue}{\lbrace 16^{n} \pi\rbrace=\lbrace 4\lbrace 16^{n} S_1\rbrace-2\lbrace 16^{n} S_4\rbrace-\lbrace 16^{n} S_5\rbrace-\lbrace 16^{n} S_6\rbrace \rbrace}$$
using the $S_j$ notation
$$\lbrace 16^{n} S_j\rbrace=\bigg \lbrace \bigg \lbrace\sum_{k=0}^{n}\frac{16^{n-k}}{8k+j} \bigg \rbrace+\sum_{k=n+1}^{\infty}\frac{16^{n-k}}{8k+j}\bigg \rbrace $$
$$=\bigg \lbrace \bigg \lbrace\sum_{k=0}^{n}\frac{16^{n-k} \mod {8k+j} }{8k+j} \bigg \rbrace+\sum_{k=n+1}^{\infty}\frac{16^{n-k}}{8k+j}\bigg \rbrace$$
Now compute $\lbrace 16^{n} S_j\rbrace$ for $j=1,4,5,6$, combine these four result, then discarding integer parts.
The resulting fraction, when expressed in hexadecimal notation, gives the hex digit of $\pi$ in position $n+1$ .