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 easier words, 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 a hang of how I should operate the system in 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 the most significant result by myself. It is in mathematics, 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 the 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 are 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 went wrong and also 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 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. 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 stuffs 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 proved as real numbers degrade 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, and adding 0.5 to it. I won’t repeat what I said in Sqrt(n). The world record values are trivial to set obviously as long as you have hard drives to store the swap so the world record is soaring as much as Pi. 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 application in economics (compound interest), statistics (normal distribution and probability theory), physics (complex numbers for RLC circuits and countless applications in modern physics) is so vast. The downside is that it is very well-defined in so many ways and proved it was irrational and transcendental so that not many mathematicians take its approximate value significantly. 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. Also a competition of how many hard drives people have, and since it’s a really important mathematical constant your name can be mentioned in 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 very deeply about the Chudnovsky Formula used to calculate Pi. I’ll just add that it was proved that Pi is irrational and transcendental and 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 Taylor series, it requires more computing power but 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 to set a world record, but a spigot algorithm developed under 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 are 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 point this “world record” concept exists and your name & 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 anyways however. Google have previously set a world record of Pi to promote their Cloud Platform, and they paid money to Mr. Yee to use the program proprietorially. The number of digits have soared to an astronomical figure, so it is both a challenge of keeping your system intact preventing any silent errors for almost a year and preparing a stack of hard drives.
Log(n) (Logarithm)
Has similarly vast applications as \(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 are 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 identity of the logarithm and inverse hyperbolic tangent first comes out in calculus. I remember solving this problem on my calculus course. The difficulty of each logarithm value varies, and is considered multiple times harder than Pi of the same number of digits.
It can also be approximated by the arithmetic–geometric mean (AGM) although 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 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 that 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 they are so slow they throttle what the CPU and RAM can process. Refer more Here.
I wish I could go deeper on the binary splitting method but to fully explain from the basics I 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 values itselves are mainly symbolic rather than mathematical, although the algorithms are in rapid research. You will only get your name on Wikipedia for Log(2).
Series Backlinks
I will overview the hardest mathematical constants Apery’s Constant, Catalan’s Constant, Lemniscate, and Euler-Mascheroni Constant in more detail also 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 of algorithms used by y-cruncher: Link. This site has the equations and time complexity of all algorithms.
