$\displaystyle \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]$
How does the BBP formula for digits of $\pi$ works exactly? Why does it use "interbase" math (hexadecimal and binary)? They don't seem to be related to $\pi$ in any way, which is just the ratio of the circumference and the diameter of a circle.
On
Here is a short implementation in Python:
from decimal import Decimal, getcontext
def pi(precision):
getcontext().prec=precision
return sum(1/Decimal(16)**k *
(Decimal(4)/(8*k+1) -
Decimal(2)/(8*k+4) -
Decimal(1)/(8*k+5) -
Decimal(1)/(8*k+6)) for k in xrange(precision))
print pi(1000)
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).
First note that the BPP formula does not compute the digits of $\pi$ in base 10, but rather base 16 (hexadecimal). Roughly, the factor
$$ \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right) $$
corresponds to the $k$th hexadecimal digit after the decimal place, which is clear enough given that it is sitting next to the factor $1/16^k$.
For everything else, including a rigorous derivation of this formula there is the charming article "The Quest for Pi" by Bailey, Borwein, Borwein and Plouffe.