Math formula that only works in some base systems
February 4, 2022 5:50 PM Subscribe
The Bailey–Borwein–Plouffe formula can calculate any digit of pi without working out the previous digits... but it only works in Base 2 and Base 16. Why?
I was reading about this formula on Futility Closet, and I think it has exposed my ignorance about base systems. I had assumed that it was a trivial matter to convert between base systems, that they were all just different ways to represent the same underlying numbers. But it seems that this is not true for formulae - that there are some that work only in Base 16, etc. - and I'm frankly stumped about why.
Is there some inherent quality or property of Base 16 / Base 2 that makes this formula possible for those systems, but not for Base 10? Or have we just not found the Base 10 equivalent of the BBP formula yet?
I was reading about this formula on Futility Closet, and I think it has exposed my ignorance about base systems. I had assumed that it was a trivial matter to convert between base systems, that they were all just different ways to represent the same underlying numbers. But it seems that this is not true for formulae - that there are some that work only in Base 16, etc. - and I'm frankly stumped about why.
Is there some inherent quality or property of Base 16 / Base 2 that makes this formula possible for those systems, but not for Base 10? Or have we just not found the Base 10 equivalent of the BBP formula yet?
I got curious and took a look at Simon Plouffe's website, where he has a paper: "it is possible to obtain an explicit expression of the nth digit of π in decimal or in binary" (emphasis mine). I don't know enough to understand the paper, but it sounds like the process is unwieldy and would take an unreasonable amount of computation to get very far into pi. I can't tell whether it's a practical obstacle or a fundamental one!
posted by moonmilk at 7:43 PM on February 4, 2022
posted by moonmilk at 7:43 PM on February 4, 2022
My link to the David H. Bailey paper above is messed up - here is the correct link: A Compendium of BBP-Type Formulas for Mathematical Constants by David H. Bailey.
posted by flug at 8:06 PM on February 4, 2022
posted by flug at 8:06 PM on February 4, 2022
Best answer: Here is the paper where they show how to use the Bailey-Borwein-Plouffe formula to calculate the nth digit of pi without having to calculate and store all the previous digits, and using possibly a lot of computation time but very little memory or storage space: On the Rapid Computation of Various Polylogarithmic Constants by Bailey, Bornstein, and Plouffe.
If I understand it correctly (and I warn you - I very well might be missing things) a lot of the cleverness of that method lies in the fact that the Bailey-Borwein-Plouffe formula has that 1/16k term naturally built into it.
So what they do when calculating say the 500 billionth digit of pi, in simplified form, is they keep calculating thousands and thousands of steps of the infinite sum until they reach the required degree of accuracy. But the trick is, at each step of the calculation they always keep the fractional part and can simply discard the integer part.
The integer part is the portion you would need to calculate the 1st through (approximately) 499,999,999,999th digit of pi. So if you were to keep all that data, it is a HUGE thing to store and even a HUGER thing to keep doing arithmetic on at each step.
Instead, you just discard all that and keep only the fractional portion - which you can do using a simple floating point number.
That is super small and super easy to calculate with.
For example, a typical floating point number, say a double precision floating point, is represented using 8 bytes. Whereas storing the first 500 billion digits of pi would require roughly 500 GB of storage space. When google did this a while ago they used 3 terabytes of storage space, whereas the 500 billionth digit could be calculated via the BBP method using literally a few dozen bytes of storage.
So that is the trick of quickly & easily calculating the nth digit without requiring a lot of storage - you can simply discard all those extra digits and then, because of the 1/16k term this automatically gives you a hexadecimal digit at the point you are looking.
(By the way it doesn't just automatically give you that one exact hex digit - it can be set up to give you like a few digits on either side of your target digit. But you're only keep track of a relative handful of digits right at your target point, not the thousands and millions and billions of digits preceding it.)
By contrast, this Plouffe paper from 1997 and the 2022 Plouffe paper that moonmilk linked provide ways to calculate decimal digits of pi but they are fundamentally different in their approach. They are more like clever ways to use certain algorithms to ensure that your pi estimate is accurate to the nth decimal (or other base) digit and then use other clever methods to extract that nth decimal digit from the result.
But (again **IF** I understand the thrust of them correctly) they are not methods that have decimal or some other number base built into them to the degree that the Bailey-Borwein-Plouffe formula does - again because the BBP formula has that 1/16k term built right into it, and that naturally provides a way of extracting hexadecimal digits. Rather, they are clever methods developed by Plouffe that could extract the nth decimal digit, with possibly reasonable efficiency, from a wide range of formulas for calculating pi.
posted by flug at 9:13 PM on February 4, 2022 [4 favorites]
If I understand it correctly (and I warn you - I very well might be missing things) a lot of the cleverness of that method lies in the fact that the Bailey-Borwein-Plouffe formula has that 1/16k term naturally built into it.
So what they do when calculating say the 500 billionth digit of pi, in simplified form, is they keep calculating thousands and thousands of steps of the infinite sum until they reach the required degree of accuracy. But the trick is, at each step of the calculation they always keep the fractional part and can simply discard the integer part.
The integer part is the portion you would need to calculate the 1st through (approximately) 499,999,999,999th digit of pi. So if you were to keep all that data, it is a HUGE thing to store and even a HUGER thing to keep doing arithmetic on at each step.
Instead, you just discard all that and keep only the fractional portion - which you can do using a simple floating point number.
That is super small and super easy to calculate with.
For example, a typical floating point number, say a double precision floating point, is represented using 8 bytes. Whereas storing the first 500 billion digits of pi would require roughly 500 GB of storage space. When google did this a while ago they used 3 terabytes of storage space, whereas the 500 billionth digit could be calculated via the BBP method using literally a few dozen bytes of storage.
So that is the trick of quickly & easily calculating the nth digit without requiring a lot of storage - you can simply discard all those extra digits and then, because of the 1/16k term this automatically gives you a hexadecimal digit at the point you are looking.
(By the way it doesn't just automatically give you that one exact hex digit - it can be set up to give you like a few digits on either side of your target digit. But you're only keep track of a relative handful of digits right at your target point, not the thousands and millions and billions of digits preceding it.)
By contrast, this Plouffe paper from 1997 and the 2022 Plouffe paper that moonmilk linked provide ways to calculate decimal digits of pi but they are fundamentally different in their approach. They are more like clever ways to use certain algorithms to ensure that your pi estimate is accurate to the nth decimal (or other base) digit and then use other clever methods to extract that nth decimal digit from the result.
But (again **IF** I understand the thrust of them correctly) they are not methods that have decimal or some other number base built into them to the degree that the Bailey-Borwein-Plouffe formula does - again because the BBP formula has that 1/16k term built right into it, and that naturally provides a way of extracting hexadecimal digits. Rather, they are clever methods developed by Plouffe that could extract the nth decimal digit, with possibly reasonable efficiency, from a wide range of formulas for calculating pi.
posted by flug at 9:13 PM on February 4, 2022 [4 favorites]
Best answer: it only works in Base 2 and Base 16. Why?
Short answer: because of the 1/16k factor in the terms of the infinite sum.
Long answer:
The string of digits that we use to express any real number in a positional numbering system is nothing more than a shorthand way of writing out a sum (i.e. an addition expression) whose solution is the number we're trying to express. And if the number we're trying to express is irrational, the only such sum that can express it has to be an infinite series that converges on the number we're trying to express.
Sometimes we even need to use infinite series to express rational numbers: for example, writing 1/3 as 0.333... in base 10. This is just shorthand for Σk=1..∞ (3 × 10-k) and the only reason that the series needs to be infinite is that the denominator of the rational we're trying to express (3) has no factors in common with the numeric base in use (10). 1/3 expressed in base 9 would just be 0.3, which is just shorthand for 3 × 9-1. In this case the numeric base does share a factor with the denominator of the rational we're writing down, so we don't end up needing to do that in the form of an infinite series.
Converting between base systems is trivial in the sense that it's always achievable using only simple arithmetic. The process involves converting the string of digits we started with to the number it represents, then dividing the result by the next smallest power of the new base, then repeatedly writing down the quotient and dividing the remainder by successively smaller powers of the new base until either that remainder drops to zero or we've generated enough digits to be able to specify a new infinite series.
For example, let's try converting 0.1 (base 7) to base 10. We start by solving the implicit sum represented by the starting digit string (0.1) and the base it's written in (7) in order to get the actual number we're trying to convert, which is 1/7. Then we divide that by the next smallest power of our new base (10) which is 10-1. The quotient is 1 and the remainder is 1/7 - 1/10 = 10/70 - 7/70 = 3/70, so we write down the 1 in the column that identifies it as a nultiple of 10-1:
.1
Next, we divide the remainder (3/70) by 10-2 (1/100). The quotient is 4 and the remainder is 3/70 - 4/100 = 30/700 - 28/700 = 2/700, so we write down the 4 in its appropriate column
.14
and go around again: 2/700 ÷ 1/1000. Quotient is 2, remainder is 2/700 - 2/1000 = 20/7000 - 14/7000 = 6/7000.
.142
and go around again: 6/7000 ÷ 1/10000. Quotient is 8, remainder is 6/7000 - 8/10000 = 60/70000 - 56/70000 = 4/70000.
.1428
...
.14285
.142857
.1428571
.14285714
.142857142
.1428571428
.14285714285
and I won't further bore you here but it can be shown that the 142857 group will repeat forever, so we can write 0.1 (base 7) as a repeating decimal using whatever local notation we favour.
But if we're trying to do that with an irrational like pi, we never reach a point at which we can just stop and put a definitive "and so on" on the end of our growing digit string and call it done. With an irrational, we just never get the ability to extrapolate the digits we haven't written down from those that we have, because irrationals always yield digit strings that never feature any endlessly repeating pattern; not in any numeric base. This is a consequence of irrationals not even having a denominator.
And that means that the base conversion process above falls at the first hurdle. With an irrational, we cannot do the very first step of converting from the digit string we're given to the number it represents, because no finite digit string ever can fully specify an irrational number. The closest we can ever get to notating an irrational as a digit string is to notate an approximation to it; and for base conversion purposes, approximations butter no parsnips.
The customary process for notating such approximations involves calculating some rational approximation to the irrational we're trying to notate, and making that approximation good enough that the difference between it and the actual irrational is enough orders of magnitude small enough not to affect any of the digits we'll end up writing down. It frequently occurs that the only practical way to do this is to keep on making successively finer rational approximations, notating each one as a digit string, and stopping only after we've seen the results stabilize at the precision we're after.
Shorcuts like the Bailey–Borwein–Plouffe formula are super cool because the infinite series they use to specify the irrational they represent is of the exact form required for direct generation of successive digits in a digit-string representation of that number - as long as we're content to use a numeric base that factors tidily into the a in the 1/ak term in the formula. In bases that don't, we're back to going the long way round. Which may well be considered trivial, but is still much much longer. And as Wikipedia helpfully points out, there is no known systematic algorithm for finding BBP-type formulae; they have to be discovered experimentally.
Does that help?
posted by flabdablet at 9:26 PM on February 4, 2022 [13 favorites]
Short answer: because of the 1/16k factor in the terms of the infinite sum.
Long answer:
The string of digits that we use to express any real number in a positional numbering system is nothing more than a shorthand way of writing out a sum (i.e. an addition expression) whose solution is the number we're trying to express. And if the number we're trying to express is irrational, the only such sum that can express it has to be an infinite series that converges on the number we're trying to express.
Sometimes we even need to use infinite series to express rational numbers: for example, writing 1/3 as 0.333... in base 10. This is just shorthand for Σk=1..∞ (3 × 10-k) and the only reason that the series needs to be infinite is that the denominator of the rational we're trying to express (3) has no factors in common with the numeric base in use (10). 1/3 expressed in base 9 would just be 0.3, which is just shorthand for 3 × 9-1. In this case the numeric base does share a factor with the denominator of the rational we're writing down, so we don't end up needing to do that in the form of an infinite series.
Converting between base systems is trivial in the sense that it's always achievable using only simple arithmetic. The process involves converting the string of digits we started with to the number it represents, then dividing the result by the next smallest power of the new base, then repeatedly writing down the quotient and dividing the remainder by successively smaller powers of the new base until either that remainder drops to zero or we've generated enough digits to be able to specify a new infinite series.
For example, let's try converting 0.1 (base 7) to base 10. We start by solving the implicit sum represented by the starting digit string (0.1) and the base it's written in (7) in order to get the actual number we're trying to convert, which is 1/7. Then we divide that by the next smallest power of our new base (10) which is 10-1. The quotient is 1 and the remainder is 1/7 - 1/10 = 10/70 - 7/70 = 3/70, so we write down the 1 in the column that identifies it as a nultiple of 10-1:
.1
Next, we divide the remainder (3/70) by 10-2 (1/100). The quotient is 4 and the remainder is 3/70 - 4/100 = 30/700 - 28/700 = 2/700, so we write down the 4 in its appropriate column
.14
and go around again: 2/700 ÷ 1/1000. Quotient is 2, remainder is 2/700 - 2/1000 = 20/7000 - 14/7000 = 6/7000.
.142
and go around again: 6/7000 ÷ 1/10000. Quotient is 8, remainder is 6/7000 - 8/10000 = 60/70000 - 56/70000 = 4/70000.
.1428
...
.14285
.142857
.1428571
.14285714
.142857142
.1428571428
.14285714285
and I won't further bore you here but it can be shown that the 142857 group will repeat forever, so we can write 0.1 (base 7) as a repeating decimal using whatever local notation we favour.
But if we're trying to do that with an irrational like pi, we never reach a point at which we can just stop and put a definitive "and so on" on the end of our growing digit string and call it done. With an irrational, we just never get the ability to extrapolate the digits we haven't written down from those that we have, because irrationals always yield digit strings that never feature any endlessly repeating pattern; not in any numeric base. This is a consequence of irrationals not even having a denominator.
And that means that the base conversion process above falls at the first hurdle. With an irrational, we cannot do the very first step of converting from the digit string we're given to the number it represents, because no finite digit string ever can fully specify an irrational number. The closest we can ever get to notating an irrational as a digit string is to notate an approximation to it; and for base conversion purposes, approximations butter no parsnips.
The customary process for notating such approximations involves calculating some rational approximation to the irrational we're trying to notate, and making that approximation good enough that the difference between it and the actual irrational is enough orders of magnitude small enough not to affect any of the digits we'll end up writing down. It frequently occurs that the only practical way to do this is to keep on making successively finer rational approximations, notating each one as a digit string, and stopping only after we've seen the results stabilize at the precision we're after.
Shorcuts like the Bailey–Borwein–Plouffe formula are super cool because the infinite series they use to specify the irrational they represent is of the exact form required for direct generation of successive digits in a digit-string representation of that number - as long as we're content to use a numeric base that factors tidily into the a in the 1/ak term in the formula. In bases that don't, we're back to going the long way round. Which may well be considered trivial, but is still much much longer. And as Wikipedia helpfully points out, there is no known systematic algorithm for finding BBP-type formulae; they have to be discovered experimentally.
Does that help?
posted by flabdablet at 9:26 PM on February 4, 2022 [13 favorites]
Best answer: To understand better why having a formula that works super neatly in base 16 isn't going to be of much use in base 10, consider the following handful of simple hexadecimal numbers and their decimal equivalents:
0.1 hex is 1/16, which is 0.0625 decimal.
0.01 → 1/256 → 0.00390625
0.001 → 1/4096 → 0.000244140625
0.0001 → 1/65536 → 1.52587890625x10-5 and already we're into results with so many digits that my calculator has resorted to approximations in scientific notation.
The amount of computation involved in decimal conversion of numbers whose hex representations contain only a single nonzero digit clearly grows extremely rapidly with the distance of those nonzero digits from the decimal point. So much so that the entire point and purpose of BBP - calculation of the kth digit of pi in constant time for any given k - is lost if the resulting digits need to be converted to a base that doesn't factor tidily into 16.
Triviality of specification often doesn't convert into low time complexity of computation.
posted by flabdablet at 9:42 PM on February 4, 2022 [2 favorites]
0.1 hex is 1/16, which is 0.0625 decimal.
0.01 → 1/256 → 0.00390625
0.001 → 1/4096 → 0.000244140625
0.0001 → 1/65536 → 1.52587890625x10-5 and already we're into results with so many digits that my calculator has resorted to approximations in scientific notation.
The amount of computation involved in decimal conversion of numbers whose hex representations contain only a single nonzero digit clearly grows extremely rapidly with the distance of those nonzero digits from the decimal point. So much so that the entire point and purpose of BBP - calculation of the kth digit of pi in constant time for any given k - is lost if the resulting digits need to be converted to a base that doesn't factor tidily into 16.
Triviality of specification often doesn't convert into low time complexity of computation.
posted by flabdablet at 9:42 PM on February 4, 2022 [2 favorites]
Sly double February willful misinterpretation:
The Plotting of Beautiful Curves (Euler Spirals and Sierpiński Triangles) - Numberphile - YouTube.
Plotting Pi and Searching for Mona Lisa - Numberphile - YouTube.
Strange things happen differently in different bases.
Any maybe something like this: The Universe of Discourse : Testing for divisibility by 7.
But yeah, what they said.
posted by zengargoyle at 6:46 AM on February 5, 2022 [1 favorite]
The Plotting of Beautiful Curves (Euler Spirals and Sierpiński Triangles) - Numberphile - YouTube.
Plotting Pi and Searching for Mona Lisa - Numberphile - YouTube.
Strange things happen differently in different bases.
Any maybe something like this: The Universe of Discourse : Testing for divisibility by 7.
But yeah, what they said.
posted by zengargoyle at 6:46 AM on February 5, 2022 [1 favorite]
Best answer: I spent some more time looking through the various papers and came up with what may be an easier-to-understand explanation at a little deeper level, of why you can't make a BBP-style formula for pi that will work in ternary, decimal, or any other base except for powers of 2.
The explanation is easier to understand with diagrams and formulas - read the whole thing here.
TL;DR would be:
* You CAN indeed make BBP-style formulas in any base you want, including ternary, decimal, and so on.
* These formulas are even promising in the sense that the results include arrangements of different basic constants such as pi, arctangent of different simple numbers, logarithms of simple numbers, and other closely related values.
* However, all of these elements come in combination with others - ie, pi is added together with some arctan, log, and other values. In order to get the value of pi isolated, you have to combine various BBP-units to cancel the unwanted factors while retaining the ones you want.
* Because of the particulars of the scheme and the math involved, when the base is anything but a factor of 2 you just can't cancel those unwanted extra constants in order to isolate pi.
* This isn't specific to just pi - the whole scheme is just pretty hit-and-miss as to whether it will produce any given value. For example, you can easily make a formulas that produce the arctangent of 1/7, 3/7, 4/7, 5/7, 6/7, and 7/7. But arctan(2/7) is actually impossible to produce!
As a I mentioned above, there are indeed proofs of some of these impossibilities, including the arctan(3/7) example and our example of interest, no pi in any base but a power of 2. The exact details of the proofs are rather hard to explain. They come down to: There are different ways to combine the various elements and in these particular cases, they just don't work out.
But with the info above & tools below you can experiment enough to get a feel for how it all works - and even try to find a base 10 formula for pi if you like!
* Even though you can't get a formula for pi in base 10, you can get some interesting constants in base 10 and other bases - just for example, pi^2 is available in a base-10 friendly BBP formula.
posted by flug at 6:51 PM on February 5, 2022 [3 favorites]
The explanation is easier to understand with diagrams and formulas - read the whole thing here.
TL;DR would be:
* You CAN indeed make BBP-style formulas in any base you want, including ternary, decimal, and so on.
* These formulas are even promising in the sense that the results include arrangements of different basic constants such as pi, arctangent of different simple numbers, logarithms of simple numbers, and other closely related values.
* However, all of these elements come in combination with others - ie, pi is added together with some arctan, log, and other values. In order to get the value of pi isolated, you have to combine various BBP-units to cancel the unwanted factors while retaining the ones you want.
* Because of the particulars of the scheme and the math involved, when the base is anything but a factor of 2 you just can't cancel those unwanted extra constants in order to isolate pi.
* This isn't specific to just pi - the whole scheme is just pretty hit-and-miss as to whether it will produce any given value. For example, you can easily make a formulas that produce the arctangent of 1/7, 3/7, 4/7, 5/7, 6/7, and 7/7. But arctan(2/7) is actually impossible to produce!
As a I mentioned above, there are indeed proofs of some of these impossibilities, including the arctan(3/7) example and our example of interest, no pi in any base but a power of 2. The exact details of the proofs are rather hard to explain. They come down to: There are different ways to combine the various elements and in these particular cases, they just don't work out.
But with the info above & tools below you can experiment enough to get a feel for how it all works - and even try to find a base 10 formula for pi if you like!
* Even though you can't get a formula for pi in base 10, you can get some interesting constants in base 10 and other bases - just for example, pi^2 is available in a base-10 friendly BBP formula.
posted by flug at 6:51 PM on February 5, 2022 [3 favorites]
The exact details of the proofs are rather hard to explain. They come down to: There are different ways to combine the various elements and in these particular cases, they just don't work out.
The stubborn refusal of 2 and 3 to yield any multiplication result but 6, despite the complete generality of the definition of integers, continues to confound and enrage amateur mathematicians as it has already done for generations.
posted by flabdablet at 7:04 PM on February 5, 2022 [1 favorite]
The stubborn refusal of 2 and 3 to yield any multiplication result but 6, despite the complete generality of the definition of integers, continues to confound and enrage amateur mathematicians as it has already done for generations.
posted by flabdablet at 7:04 PM on February 5, 2022 [1 favorite]
Best answer: SELF SERVICE EXPERIMENTAL EXAMPLES
* You can mess around with an editable BBP "unit" formula on Wolfram Alpha to see how it can produce various factors and values, including pi.
Things to try:
- Change the "base" of the formula via the 1/sqrt(x) value (currently set to 10). As discussed above, this is the value that determines which base the formula will work best with - binary, ternary, decimal, hexadecimal, etc.
- Change the power of x in the numerator (currently set to 1; can be anything 0 to 8 - or even larger, but it might get weird)
- Change the multiplier (currently 8 - you can sometimes use this to eliminate or isolate the constants you want)
As you make all these changes, you'll see that the formula produces all kinds of interesting and unexpected values. They're the kinds of thing you would never in a million years guess to be even possible from such a simple formula.
* Here is a full-fledged editable BBP formula that calculates pi, on Wolfram Alpha.
Again Wolfram Alpha will do the calculus and algebra for you, so you can see how the formula generates various arctan, log, square root, pi, and similar values, and how this formula is cleverly arranged so that all of them cancel out except for pi.
- As above, you can experiment with changing integral limits to 1/sqrt(3) or anything else you like, powers of x in the numerator to various values, and multipliers for each integral to different values.
- This formula has combines four BBP units into one larger formula, so you can experiment with using the results of one unit to cancel out unwanted values from another unit - if only you can figure out how!
FINDING THE ANSWERS - THE PSLQ ALGORITHM
Working out exactly how to do that last step is where some really interesting mathematics has happened - particularly the so-called PSLQ algorithm developed by Helaman Ferguson et al, which has been listed in the "Top 10 Algorithms of the Century."
A SIMPLE EXPLANATION WHY THERE IS NO DECIMAL SOLUTION
As to WHY you can't always find a solution to cancel out the unwanted values and retain the one you want, a simple way to explain it is the setup is similar to logic puzzles you often see - where you can set up a grid and eliminate one possibility after another until by a process of elimination you are left with just one answer.
But if you think about it, the published logic puzzles are all specially designed to give one and only one answer.
It would be possible to design a logic puzzle that allowed several correct answers. That is the situation we are in with the BBP formula for hexadecimal digits and pi. There are several possible and working formulas.
But for decimal digits and pi, the puzzle designer messed up and eliminated all possible solutions. So we're just left with nothing.
posted by flug at 7:08 PM on February 5, 2022 [1 favorite]
* You can mess around with an editable BBP "unit" formula on Wolfram Alpha to see how it can produce various factors and values, including pi.
Things to try:
- Change the "base" of the formula via the 1/sqrt(x) value (currently set to 10). As discussed above, this is the value that determines which base the formula will work best with - binary, ternary, decimal, hexadecimal, etc.
- Change the power of x in the numerator (currently set to 1; can be anything 0 to 8 - or even larger, but it might get weird)
- Change the multiplier (currently 8 - you can sometimes use this to eliminate or isolate the constants you want)
As you make all these changes, you'll see that the formula produces all kinds of interesting and unexpected values. They're the kinds of thing you would never in a million years guess to be even possible from such a simple formula.
* Here is a full-fledged editable BBP formula that calculates pi, on Wolfram Alpha.
Again Wolfram Alpha will do the calculus and algebra for you, so you can see how the formula generates various arctan, log, square root, pi, and similar values, and how this formula is cleverly arranged so that all of them cancel out except for pi.
- As above, you can experiment with changing integral limits to 1/sqrt(3) or anything else you like, powers of x in the numerator to various values, and multipliers for each integral to different values.
- This formula has combines four BBP units into one larger formula, so you can experiment with using the results of one unit to cancel out unwanted values from another unit - if only you can figure out how!
FINDING THE ANSWERS - THE PSLQ ALGORITHM
Working out exactly how to do that last step is where some really interesting mathematics has happened - particularly the so-called PSLQ algorithm developed by Helaman Ferguson et al, which has been listed in the "Top 10 Algorithms of the Century."
A SIMPLE EXPLANATION WHY THERE IS NO DECIMAL SOLUTION
As to WHY you can't always find a solution to cancel out the unwanted values and retain the one you want, a simple way to explain it is the setup is similar to logic puzzles you often see - where you can set up a grid and eliminate one possibility after another until by a process of elimination you are left with just one answer.
But if you think about it, the published logic puzzles are all specially designed to give one and only one answer.
It would be possible to design a logic puzzle that allowed several correct answers. That is the situation we are in with the BBP formula for hexadecimal digits and pi. There are several possible and working formulas.
But for decimal digits and pi, the puzzle designer messed up and eliminated all possible solutions. So we're just left with nothing.
posted by flug at 7:08 PM on February 5, 2022 [1 favorite]
This thread is closed to new comments.
Just for example pi squared has both a binary and a ternary formula.
So it is possible to express some constants in different bases, not powers of 2 only. My guess would be that the bases that will work have something to do with the characteristics of the polynomial they use to generate the formula, but I don't understand the specifics well enough to say exactly what.
This paper by Borwein, Borwein, and Galway shows that what they call "Level 1 BBP-type formulas" for pi only exist for base 2 and powers of 2.
Note that this still allows for the possibility of Level 2, Level 3, and so on, formulas. These are a bit more complex but still the same type of thing. As far as I know, no one has discovered such formulas for any different base than 2 (or powers of 2) but no one has proven it impossible, either.
I haven't parsed the Borwein-Borwein-Galway paper carefully enough to figure out if there is some way to explain it in relatively simple English, but maybe someone can? That is probably more or less the answer you are looking for.
posted by flug at 6:50 PM on February 4, 2022 [1 favorite]