Algorithms and Significance of Major Mathematical Constants: Part 2
NNote: 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.
If you did not read the First Post, it would help to read it first.
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 please don’t start this from scratch for the sake of becoming famous or irrelevantly adding a line to your CV because it isn’t worth it. I just did it 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.
Zeta(3) (Apery’s Constant)
Wikipedia My Post on the World Record
First, the Riemann zeta function \(\zeta(s) =\sum_{n=1}^\infty\frac{1}{n^s}\). This expression converges when the real part of the complex number \(s\) is larger than 1, but can be expanded beyond this range with other series and integral representations. \(\zeta(2) =\sum_{n=1}^\infty\frac{1}{n^2} = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \cdots\) was called the Basel problem, and was proved by Leonhard Euler as being equivalent to \(\frac{\pi^{2}}{6}\).
The values of the Riemann zeta function has been involved in all kinds of unsolved problems in physical (especially in dynamics and quantum), mathematical, and chemical sciences, and thus the approximate values are used in industries and academia all the time.
Now, Apery’s Constant \(\zeta(3) = \sum_{n=1}^\infty\frac{1}{n^3} = \lim_{n \to \infty}\left(\frac{1}{1^3} + \frac{1}{2^3} + \cdots + \frac{1}{n^3}\right)\) has been proved as irrational (but unknown if transcedental) by Roger Apéry in 1978. As much as the Riemann zeta function is involved in unsolved problems of science, the value of Apery’s Constant was involved in insight of many physical and mathematical problems. For example, \(\frac{1}{\zeta(3)}\) is the probability of three positive integers to be relatively prime, is involved in an electron’s gyromagnetic ratio using quantum electrodynamics, random minimum spanning trees in data structures, and the Debye model and the Stefan–Boltzmann law in thermodynamics because of the constant’s nature.
It is a very interesting and significant constant to set a world record, and currently Dr. Ian Cutress has the world record for this as of May 2020.
Rapidly converging series have been found by Dr. Sebastian Wedeniwski in 1998. The series representation is less trivial compared to Pi leading to a higher intensity in computing it, resulting to be one of the more intensive constants. You will get your name on Wikipedia, but the difficulty of computing starts to rapidly elevate because these constants have more properties unknown than known and algorithms are less efficient.
Interesting fact: Dr. Sebastian Wedeniwski, the discoverer of the Wedeniwski (1998) algorithm, was the person behind ZetaGrid, which was one of the largest distributed computing projects of the early 2000s and had the purpose of finding roots of the zeta function to test if there are any counterexamples of the Riemann hypothesis. He is now the Chief Information Officer (executive position) at the Standard Chartered Bank at Singapore after 18 years at IBM, currently in charge of all informational management of the multinational banking group. Mr. Alexander Yee (the person who created y-cruncher) also works at Citadel Securities, a huge hedge fund located in Chicago, after his time at Google. I guess the people from mathematical computing academic diciplines meet in the financial industry.
Catalan’s Constant
\[G = \beta(2) = \sum_{n=0}^{\infty} \frac{(-1)^{n}}{(2n+1)^2} = \frac{1}{1^2} - \frac{1}{3^2} + \frac{1}{5^2} - \frac{1}{7^2} + \frac{1}{9^2} - \cdots\]Related to a lot of identities in integral calculus, it is in relation to important problems in combinatorics such as the trigamma function. There are a lot in integral identities that conclude to a value that leads to Catalan’s constant, and they are all in the Wikipedia link. It is a simple series yet we know almost nothing about its properties including irregularity or transcendentality.
Since the definition itself is a pretty intuitive series expansion, the derived rapid converging series are abundant. The most efficient algorithms were discovered by Khodabakhsh Hessami Pilehrood, Tatiana Hessami Pilehrood and another by Jesús Guillera after 2010. It is slightly harder than Apéry’s constant though the only thing more special over Apery’s constant is that it has binomial coefficients inside the series. You can get your name on Wikipedia as it is important.
Lemniscate Constant
This is a lemniscate. (https://commons.wikimedia.org/wiki/File:Lemniscate_of_Booth.png) It looks like a dumbbell and has been defined by Jakob Bernoulli and first comes out in precalculus.
Cartesian Coordinates: \((x^2 + y^2)^2 = 2a^2 (x^2 - y^2)\)
Polar Coordinates: \(r^2 = 2a^2 \cos 2\theta\)
Let’s start with Gauss’s constant to define the constant related to the lemniscate.
\[G = \frac{1}{\operatorname{agm}\left(1, \sqrt{2}\right)} = 0.8346268\dots\]or
\[G = \frac{2}{\pi}\int_0^1\frac{dx}{\sqrt{1 - x^4}}\]If you don’t know what AGM is, see the Logarithm section of this link.
This can also be expressed with the gamma function, which is a continuous extension of the factorial (\(n! = n \cdot (n-1) \cdot \cdots \cdot 2 \cdot 1\)) function, which originally is a natural number function.
\(\Gamma(n) = (n-1)!\) for any integer \(n\) and \(\Gamma(z) = \int_0^\infty x^{z-1} e^{-x}\,dx, \ \qquad \Re(z) > 0\)
\[G = \frac{\left[\Gamma\left( \tfrac{1}{4}\right)\right]^2}{2\sqrt{ 2\pi^3}}\]Gauss’s constant is transcendental because of this property. It is also related to the Jacobi theta function
Then the first and second lemniscate constants are defined as the following.
\(L_1 = \pi G\), \(L_2 = \frac{1}{2G}\)
The lemniscate constant y-cruncher calculates is actually in long name called arc length of a lemniscate with a=1 (OEIS A064853). It is the length of a lemniscate of which \(a\) in Cartesian or Polar Coordinates is 1.
It is defined as \(s =4\int_0^1\frac{dt}{\sqrt{1-t^4}} = 2L_1 = \frac{\pi}{L_2} = 2 \cdot \pi \cdot G = \frac{\left[\Gamma\left( \tfrac{1}{4}\right)\right]^2}{\sqrt{ 2\pi}}\) and it is arc length of a lemniscate with a=1 when \(a\) is the constant you see up there in the Polar Coordinates notation.
Overall, this is an interesting mathematical constant in geometric algebra, but expect no name on Wikipedia.
The algorithm from here starts to get more complicated rather than simple series you saw until now.
The first and most recent algorithm is the AGM-Pi algorithm. Remember \(G = \frac{1}{\operatorname{agm}\left(1, \sqrt{2}\right)}\). Then \(s = \frac{2\pi}{\operatorname{agm}\left(1, \sqrt{2}\right)}\). So if we calculate \(\pi\) and calculate the AGM value, we can get the arc length of a lemniscate with a=1. It looks simple, and it is actually the easiest one to calculate provided you calculate everyting in the RAM. Remember the AGM algorithm has bad memory locality. If we use HDD swaps, the becomes more serious and becomes slower than the traditional algorithms. I oversaw the note that computations regarding swaps could be slower than traditional algorithms and ended up spending more time by using this algorithm.
A more traditional algorithm changes the integral definition of Gauss’s constant. Recall \(G = \frac{2}{\pi}\int_0^1\frac{dx}{\sqrt{1 - x^4}}\). We can change this to a series expansion using the definition of definite integral to a Riemann sum. We can use the series expansion of the inverse (arc) function of the Lemniscate sine function derived from the definition of Gauss’s constant.
Gauss Formula: \(Lemniscate = 8 ArcSinlemn(\frac{1}{2}) + 4 ArcSinlemn(\frac{7}{23})\)
Sebah’s Formula: \(Lemniscate = 8 ArcSinlemn(\frac{2}{3}) - 4 ArcSinlemn(\frac{7}{137})\)
The first formula is simpler and the second is used to verify if we aren’t using the AGM-Pi algorithm. Because it isn’t a simple series expansion, the difficulty increases.
Euler-Mascheroni Constant
Dreadful. Just dreadful. Three times harder than the next hardest mathematical constant.
\[\gamma = \lim_{n\to\infty}\left(-\ln n + \sum_{k=1}^n \frac1{k}\right) = \int_1^\infty\left(-\frac1x+\frac1{\lfloor x\rfloor}\right) dx\]When \({\lfloor x\rfloor}\) is the floor function.
The area of the blue region converges to the Euler–Mascheroni constant. (Wikipedia)
This comes out predominantly while learning the integral test for convergence.
Third-most mathematical constant and is the hardest. the \(\gamma\) in y-cruncher is the Euler-Mascheroni Constant, and Mr. Alexander Yee first made this program to compute this very constant.
There is no one AGM or series expansion equation to compute this, and it is even more complicated than Gauss Formula or Sebah’s Formula of the lemniscate. I think this was easily harder than Google’s Pi world record (50 times more digits than my Euler-Mascheroni Constant record) if we rule out the fact that they need more hard drives. It took as much as them, and it is as picky to manage as them. I asked Dr. Ian Cutress to verify this, and he got an ECC corrected error that I never saw in one of my own computations. Disk R/W is 1/3 of Google’s record while the digits are 1/50.
There are so many papers that attempt to make the Brent-McMillan algorithm computation easier, both by new algorithms and optimization of existing ones, but it is hard.
The lemniscate constant started becoming a hard computation because it was a rational arithmetic of two different series expansions. Guess what. People failed to find an algorithm better than the one developed in 1980. Because it is the limit between the harmonic series and the natural logarithm, we have to literally subtract the natural logarithm from the equivalent value of the harmonic series. This causes the computation to become three times harder than even the arc length of a lemniscate with a=1.
Brent-McMillan Algorithm:
\[\gamma = \frac{A}{B} - ln(n) + O(e^{-4n})\]where \(O(e^{-4n})\) is the rate of convergence in Big O notation, \(A = \sum_{k=0}^{\infty} (\frac{n^k}{k!})^2 H(k)\), \(B = \sum_{k=0}^{\infty} (\frac{n^k}{k!})^2\), and \(H(n) = \zeta(1) = \sum_{k=1}^{n} \frac{1}{k}\)
Further refined Brent-McMillan Algorithm to increase rate of convergence (note that the rate of convergence is not a square faster because the equation becomes more complicated):
\[\gamma = \frac{A}{B} - \frac{C}{B^2} - ln(n) + O(e^{-8n})\]where \(O(e^{-8n})\) is the rate of convergence in Big O notation, \(A = \sum_{k=0}^{\infty} (\frac{n^k}{k!})^2 H(k)\), \(B = \sum_{k=0}^{\infty} (\frac{n^k}{k!})^2\), \(H(n) = \zeta(1) = \sum_{k=1}^{n} \frac{1}{k}\), and \(C = \frac{1}{4n} \sum_{k=0}^{2n} \frac{((2k)!)^3}{(k!)^4 \cdot (16n)^{2k}}\).
It looks already hard, but it becomes even harder because it is a class of formulae that give better approximations successively, so the series is different based on setting \(n\) depending on the expected precision. Because series \(A\) includes the harmonic series, it is a double summation and makes it very hard to find a Binary Splitting recursion and is significantly more complicated compared to others once found. Series \(A\), \(B\), \(C\) have non-linear irregular convergence behaviour that makes computation trickier and Series \(C\) and \(H\) are divergent. The only other viable algorithm is called Sweeney’s Method, which is easier but slower.
This constant has a bigger presense in mathematics than Catalan’s Constant and appears in as many unsolved problems in mathematics as Apery’s Constant, but while Apery’s Constant was proved as irrational, we know nothing about whether it is algebraic/transcendental or even irrational. This is a short list of some notable problems Euler-Mascheroni Constant appears in, and it also appears related to various definite integrals, digamma function \(\gamma\), which is the derivative of the gamma function \(\Gamma\) (remember we saw this in Gauss’s constant and Lemniscate), and also the Riemann zeta function \(\zeta\) (remember Apery’s constant is \(\zeta(3)\)). So it this constant is a very important intersection in mathematics research, but we don’t know a lot about this. Lots of potential in researching this, but it is too hard to compute. That is why I think me and Dr. Ian Cutress’s endeavour counts toward mathematical advances because there are other constants people can set records cheaper and we still did it.
This record will get your name on Wikipedia as part of the history of known digits.
Series Backlinks
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.
