8
$\begingroup$

$\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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I also noted that your name is in binary :) Thanks for the help 'D' $\endgroup$ – AvZ Sep 27 '14 at 17:50
  • 3
    $\begingroup$ This factor does not correspond to any particular digit on any particular decimal or hexadecimal place, which is clear enough given that it is much smaller than $1$ for large $k$. $\endgroup$ – janek37 Feb 18 '18 at 15:33
  • 2
    $\begingroup$ Agree with @janek37. This answer should not be checkmarked. $\endgroup$ – David Diaz Nov 6 '18 at 12:43
2
$\begingroup$

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).

  1. 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.
  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.
  3. 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.
$\endgroup$
0
$\begingroup$

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)
$\endgroup$
  • 3
    $\begingroup$ As nobody has commented on this so far, let me add a warning that this is not how the formula is supposed to be used. If you run this program, then the last digit(s) will usually be wrong. $\endgroup$ – Frunobulax May 12 '18 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.