|Reaching The Unreachable - Pi Squared And Catalan's Constant|
|Written by Mike James|
|Sunday, 04 August 2013|
You may have heard the reports of computing Pi to millions of digits, but you might not know that there are other related constants that are much more difficult to compute. Now we are getting closer to being able to compute these values as well - and it isn't a matter of more computing power.
A recent paper explains how computations that were thought to be out of reach are now within our grasp. Computing Pi seems to be a relatively easy occupation by comparison with computing constants that seem very similar - take Pi squared, for example. It's just Pi raised to the power of two and we can get the digits of Pi fairly easily, but Pi squared isn't so easy.
To put things into context we are not taking about working out the thousandth or the millionth digits, but trillions. Pi is already known to five million million digits but Catalan's constant, for example, has only been computed to 31 thousand million digits. A lot, but nowhere near the ten trillion digits of Pi squared just achieved.
The secret to this boost in performance is a slight cheat. Back in 1997 a remarkable formula was uncovered - the Bailey, Borwein and Plouffe, or BBP, formula. This gave the digits of Pi starting from an arbitrary digit position without having to calculate the digits up to that position. So if you want to compute the ten trillionth digit of Pi you can - without having to compute the earlier digits first.
This is remarkable. Pi is an irrational, its expansion in any base goes on forever and it never becomes periodic or transcendental, it isn't the root of any polynomial, and yet its digits have so much structure that you can compute the kth digit without having to calculate the first, second, third and all the way up to k-1.
What is surprising is the way that the BBP formula was found. A BBP type formula for the binary digits of log 2 was discovered. The idea was born that there might be a formula of the same type for Pi. The method employed to try and find one made use of a computer and the PSLQ integer relation detection algorithm to find an exact relationship between Pi and an integer combination of constants with similar series expansions to log 2. After months of searching the BBP formula for Pi was found.
The original BBP formula gave the kth digit of Pi in a hexadecimal expansion. A computer search started for BBP formulae in other bases, but according to a theorem proved in 2004 it seems that the only useful BBP formulas for Pi have to be in a base that is a power of 2.
The BBP formula for Pi has been used to compute the digits starting from the one quadrillionth digit and it has been used to check more conventional calculations.
Since 1997 the same search technique has been used to find BBP formulas for other constants - Pi squared, Pi cubed, Catalan's constant and more. Catalan's constant is interesting because it is one of the simplest constants defined by a series that hasn't been proven to be irrational or transcendental - although both seem likely.
Using the BBP formulas for these constants, IBM's BlueGene/P system was set to work computing the base 64 digits of Pi squared starting at the 10 trillionth digit, base 729 digits of Pi squared starting at the 10 trillionth digit and base 4096 digits of Catalan's constant starting at the 10 trillionth position. Each computation took between 10 and 30 days of time on BlueGene.
A “random” walk on a million digits of Catalan’s constant
Well, if you have to ask you probably aren't going to be impressed by the answers. Experimental maths provides an opportunity to observe the behavior of digit sequences and propose conjectures that could be the subject of proofs given sufficient time. In this particular case, the nature of the BBP formulas themselves is a clue as to the regularities of the constants.
"For these reasons there is continuing interest in the theory of BBP-type constants, since, as mentioned, there is an intriguing connection between BBP-type formulas and certain chaotic iterations that are akin to pseudo random number generators.
And the paper finishes with an interesting conjecture:
Conjecture 2. There is no BBP formula for e. Moreover, there is no way to extract individual digits of e significantly more rapidly than by computing the first n digits.
To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin, or sign up for our weekly newsletter.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Monday, 05 August 2013 )|