Algorithms and Significance of Major Mathematical Constants: Part 1
Note: this post is appropriate for people with at least a high school mathematics or calculus background, although anyone enthusiastic about mathematics can understand this if Google and Wikipedia are your friends. I am also not a professional mathematician, so this post may include inaccuracies. Also, this post is meant to supplement Mr. Alexander Yee’s y-cruncher in simpler terms, not replace it. You have to see his website for the crucial technical details required to make world records.
If you are interested in actually setting a world record with y-cruncher, read This Post for an in-depth explanation of optimizing the configurations of y-cruncher as well.
I have been following y-cruncher since like 2011, which is 2 years after it was out. I calculated a few hundred million to a billion digits of Pi with my laptop back then. That was nowhere close to the world record even back then, but I got the hang of how I should operate the system as a whole instead of leaving it alone to rapidly overheat and do nothing about it.
It was almost 8 years after that until I set a series of world records, and I see the Euler-Mascheroni Constant as my most significant result. In mathematics, it is the most important mathematical constant that comes out first in calculus related to the integral test, next to Pi and \(e\), as Pi first comes out in elementary school and the definition of \(e = \lim_{n\to\infty} \left( 1 + \frac{1}{n} \right)^n\) in an earlier chapter of high school calculus.
Here, I overview mathematical constants that y-cruncher by Alexander Yee made various world records for.
Difficulties of mathematical constants: (Excerpt from y-cruncher v0.7.8.9506, Mr. Yee thankfully let me post this)
Compute a Constant: (in ascending order of difficulty to compute)
# Constant Value Approximate Difficulty*
Fast Constants:
0 Sqrt(n) 1.46
1 Golden Ratio = 1.618034... 1.46
2 e = 2.718281... 3.88 / 3.88
Moderate Constants:
3 Pi = 3.141592... 13.2 / 19.9
4 Log(n) > 35.7
5 Zeta(3) (Apery's Constant) = 1.202056... 62.8 / 65.7
6 Catalan's Constant = 0.915965... 78.0 / 105.
7 Lemniscate = 5.244115... 60.4 / 124. / 154.
Slow Constants:
8 Euler-Mascheroni Constant = 0.577215... 383. / 574.
Other:
9 Euler-Mascheroni Constant (parameter override)
10 Custom constant with user-defined formula.
*Actual numbers will vary. Radix conversion = 1.00
Note there are more mathematical constants that are defined with custom formula files available with the executable, but they involve more complicated math, so if you really want to set custom formula records, you should eventually know more as you research them.
I will add whether your name can go on Wikipedia if you set a record for this or not, but I just did these computations to test the long-term stability of the high-performance system that I use for other actually production-purpose uses in research that must not have gone wrong, and to assay my system administration competence, and it won’t make you famous just because you had nice hardware and a bunch of hard drives, just in case you are looking at this for such a purpose. I just had spare time when I did world records and I wanted to do a slightly more meaningful thing than the default stress test y-cruncher provided. This is why I upload every world record computation I do to help any mathematicians in the future.
Sqrt(n)
It’s easy to compute. The algorithm is very trivial as it is simply Newton’s Method (\(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\)) to find a closer approximation per step. There is not much issue even compared to radix conversion from decimal to hexadecimal. Mostly, the values used to set records are \(\sqrt{2}\) or \(\sqrt{3}\), the earlier one being more significant. However, the definition is not complex, and so many things have been proved about the square root values such as irrationality, since \(\sqrt{2}\) is simply \(2^{1/2}\) and related calculations can be done by any high school student. The fact that these values are proven to be real numbers degrades the value of research in approximation, and these values likely won’t provide any significant addition to mathematical advances. Only Sqrt(2) will add your name to Wikipedia, and it is a competition of how many hard drives people have.
Golden Ratio
\[\varphi = \frac{1+\sqrt{5}}{2}\]Culturally significant, mathematically not so much? It is \(\sqrt{5}\) divided by 2, with 0.5 added to it. I won’t repeat what I said in Sqrt(n). The world record values are obviously trivial to set as long as you have hard drives to store the swap, so the world record is soaring as much as Pi’s. It is also a competition of how many hard drives people have, and your name won’t be on Wikipedia unless you make your own table on the document and the moderators approve it.
e (Base of the Natural Logarithm)
\[e = \sum\limits_{n = 0}^{\infty} \frac{1}{n!} = \frac{1}{1} + \frac{1}{1} + \frac{1}{1\cdot 2} + \frac{1}{1\cdot 2\cdot 3} + \cdots = \lim_{n\to\infty} \left( 1 + \frac{1}{n} \right)^n\]As I said above, it is widely regarded as the second-most important mathematical constant. In addition to its universal significance in mathematics, its applications in economics (compound interest), statistics (normal distribution and probability theory), and physics (complex numbers for RLC circuits and countless applications in modern physics) are so vast. The downside is that it is very well-defined in so many ways and has been proved irrational and transcendental, so not many mathematicians take its approximate value seriously. However, it has great mathematical value.
The Taylor series definition is used to set the record as it is easy to calculate how many terms are required to ensure the decimal and hexadecimal digits. The world record values are easy to set as long as you have hard drives to store the swap so the world record is soaring over the Golden Ratio. It is also a competition of how many hard drives people have, and since it’s a really important mathematical constant, your name can be mentioned on Wikipedia but will likely be erased when someone else renews it by seeing how the moderators set up the tables.
Pi (π)
Most of you seeing this should be interested in this the most. Former Pi world record holder Dr. Peter Trueb made a blog, and he has explained the Chudnovsky Formula used to calculate Pi in great depth. I’ll just add that it was proved that Pi is irrational and transcendental, and that the Chudnovsky Formula is a great, rapidly converging formula that made Pi computation easier after the Ramanujan–Sato series. But unlike \(e\), which is basically the simplest form of a Taylor series, it requires more computing power, though the bottleneck for world records already went to the swap disk I/O rather than CPU. For all constants, it is required to verify the computation with another mathematically independent algorithm to set a world record, but a spigot algorithm developed less than 30 years ago called the Bailey–Borwein–Plouffe (BBP) formula calculates the last few digits of Pi in hexadecimal and verifies that the computations did not have any errors. It is computationally impractical to calculate all digits in between, but since the last few digits are sufficient to verify the whole series is intact, it is a good and short verification method. Since it is pretty simple, Mr. Alexander Yee does this for you when one sets a record normally.
I guess this is the whole reason this “world record” concept exists, and your name and face will become more famous when you set a world record. Most people who recently set the records for Pi are respected professionals in their own fields, however. Google has previously set a world record of Pi to promote their Cloud Platform, and they paid money to Mr. Yee to use the program proprietarily. The number of digits has soared to an astronomical figure, so it is both a challenge of keeping your system intact and preventing any silent errors for almost a year, and of preparing a stack of hard drives.
Log(n) (Logarithm)
It has applications as vast as those of \(e\). \(log_n (x)\) with a positive base that is not 1 and positive domain is the inverse function of \(n^{x}\), so \(ln(x)\) is the inverse of \(e^{x}\). It is proved that the range of any logarithm function with a positive base that is not 1 and positive domain is real.
The computation is done with a Primary Machin-like Formula that can be auto-generated as a sum of a fraction multiplied by an inverse hyperbolic tangent approximate value (also generated with Taylor series but simpler) as it converges faster than the simple Taylor series of the logarithm. Proving the identity of the logarithm and inverse hyperbolic tangent first comes out in calculus. I remember solving this problem in my calculus course. The difficulty of each logarithm value varies and is considered multiple times harder than Pi at the same number of digits.
It can also be approximated by the arithmetic–geometric mean (AGM) although it is too inefficient to be used for the world record computations. This itself is used in precalculus algebra or olympiads for finding ranges. However, the algorithm of the same principle is actually used for the world record computations of the Lemniscate Constant, coming up on my Second Post.
\[0<\frac{n}{1/x_1+1/x_2+\cdots+1/x_n}\leq\sqrt[n]{x_1x_2\cdots x_n}\leq\frac{x_1+x_2+\cdots+x_n}{n} \leq\sqrt{\frac{x_1^2+x_2^2+\cdots+x_n^2}{n}}\]This is the Root-Mean Square-Arithmetic Mean-Geometric Mean-Harmonic Mean Inequality (RMS-AM-GM-HM) relation (largest to smallest), and we will take the middle 2 relations only.
\[\ln (x) \approx \frac{\pi}{2 M(1,2^{2-m}/x)} - m \ln (2)\]\(M(a,b)\) here or \(agm(a, b)\) generally denotes the arithmetic–geometric mean of \(a\) and \(b\) and is repeatedly calculated by computing the arithmetic mean \(\frac{a+b}{2}\) and geometric mean \(\sqrt{ab}\) and making them the new \(a\) and \(b\). This rapidly converges as there are more steps \(m\) to make more digits.
This method may be presumed to be faster than series expansion because AGM has a time complexity of \(O(n log(n)^2)\) instead of \(O(n log(n)^3)\) of most series with the Big O notation, but because each term of AGM is multitudes more complex (which is the constant in Big O notation) than series and because AGM has bad memory locality, a series expansion incorporating Binary Splitting is faster. This is the same reason AGM algorithms for Pi are not used. Also note that the bottleneck of HPC computations is no longer the CPU. It is the storage. If there is not enough RAM to house all the generated data used for computation, an external swap storage must be used, and it is so slow that it throttles what the CPU and RAM can process. For more information, see Here.
I wish I could go deeper on the binary splitting method, but to fully explain it from the basics I would have to give an example of expanding long expressions, so I replace my explanation with the First Link, Second Link, and Third Link.
Like Sqrt(n), each approximate value is mainly symbolic rather than mathematical, although the algorithms are under active research. You will only get your name on Wikipedia for Log(2).
Series Backlinks
I will overview the hardest mathematical constants Apéry’s Constant, Catalan’s Constant, Lemniscate, and Euler-Mascheroni Constant in more detail, as all of these are constants I made world records for.
If you are interested in actually setting a world record with y-cruncher, read This Post for an in-depth explanation of optimizing the configurations of y-cruncher as well.
More information on algorithms used by y-cruncher: Link. This site has the equations and time complexity of all algorithms.
