Lehmer defined a measure

where the may be either integers or rational numbers in a Machin-like formula for . When the are integers, Lehmer’s measure can be used to determine the computational efficiency of the given Machin-like formula for . However, because the computations are complicated, it is unclear if Lehmer’s measure applies when one or more of the are rational. In this article, we develop a new algorithm for a two-term Machin-like formula for as an example of the unconditional applicability of Lehmer’s measure. This approach does not involve any irrational numbers and may allow calculating rapidly by the Newton–Raphson iteration method for the tangent function.

1. Introduction

In 1706, the English astronomer and mathematician John Machin discovered a two-term formula for [1–3]

(1)

that was later named in his honor. This formula for appeared to be more efficient than any others known by that time. In particular, due to the relatively rapid convergence of the right-hand side of (1), he was able to calculate 100 decimal digits of [1]. Nowadays, identities of the form

(2)

where and are either integers or rational numbers, are called the Machin-like formulas for . Consequently, a two-term Machin-like formula for is given by

(3)

If in equation (3) the constants and are some positive integers and , then the unknown value can be found as [4, 5]

(4)

Furthermore, since we assumed that and are positive integers, from equation (4) it immediately follows that must be either an integer or a rational number.

In 1938, Lehmer [6] introduced a measure (see also [7])

(5)

showing how much computational effort is required for a specific Machin-like formula for . In particular, when is small, then less computational effort is required and, consequently, the computational efficiency of this formula is higher. Lehmer’s measure is smaller if there are fewer summation terms and the constants are larger in magnitude. For more efficient computation, the constants should be larger by absolute value, since it is easier to approximate the arctangent function as its argument tends to zero (see [7] for more details).

It is also important to emphasize that in the same paper [6] Lehmer presented a few Machin-like formulas where some of the are not integers but rational numbers. This signifies that Lehmer assumed that his measure (5) remains valid whether the are integers or rational numbers.

In 2002 Kanada [8], using the following self-checking pair of Machin-like formulas for ,

and

computed more than 1 trillion digits of . These two examples show that the Machin-like formulas have colossal potential in the computation of decimal digits of .

In 1997, Chien-Lih showed a remarkable formula [9]

with . According to Weisstein [10], this Lehmer’s measure is the smallest known value for the consisting of integers only. Later Chien-Lih [11] showed how Lehmer’s measure can be reduced even further by using an Euler type of identity in an iteration for generating the two-term Machin-like formulas like (3) such that and are rational numbers.

In [12], we derived the following simple identity (see also [13])

(6)

where and , and described how using this identity, another efficient method for generating the two-term Machin-like formula for

(7)

with small Lehmer’s measure can be developed. In this approach, the constant can be chosen as a positive integer such that

(8)

and, in accordance with equation (4), the constant in equation (7) can be found from

(9)

It is not reasonable to solve equation (9) directly to determine the rational number , as its solution becomes tremendously difficult with increasing integer . However, this problem can be effectively resolved by using a very simple two-step iteration procedure discussed in the next section. Therefore, our approach in generating the two-term Machin-like formula (7) for with small Lehmer’s measure is much easier than Chien-Lih’s method [11].

Wetherfield [7] provides a detailed explanation clarifying the significance of Lehmer’s measure that shows how much computation is required for a given Machin-like formula for when all the constants . However, it is unclear if this paradigm is also applicable when at least one number is rational. More specifically, the problem that occurs in computing the two-term Machin-like formula for in Chien-Lih’s [11] and our [4] iteration methods is related to the rapidly growing number of digits in the numerators and denominators of or . This occurs simultaneously with an attempt to decrease Lehmer’s measure. As a result, the subsequent exponentiation in conventional algorithms makes computing the decimal digits of inefficient. Therefore, the applicability of Lehmer’s measure for a Machin-like formula for for the case is questionable. For example, Lehmer’s measure may be small, say less than 1. This means that less computational work is needed to calculate . However, due to the large number of digits in the numerators and denominators in or , a computer performs more intense arithmetic operations that make the runtime significantly longer. Consequently, we ask, Is Lehmer’s measure still applicable when at least one constant from the set is not an integer but a rational number?

Motivated by an interesting paper in regard to equation (7) that was recently published [14], we further develop our previous work [4, 5]. In this article, we propose a new algorithm showing how unconditional applicability of Lehmer’s measure for the two-term Machin-like formula (7) for can be achieved. We also describe how linear and quadratic convergence to can be implemented.

2. Preliminaries

As mentioned, the number of summation terms in equation (2) should be reduced in order to minimize Lehmer’s measure. Since at there is only one Machin-like formula for ,

(10)

we consider the case . We attempted to find a method that can be used to generate a two-term Machin-like formula for with small Lehmer’s measure. Equation (7) provides an efficient way to do this.

In fact, the original Machin formula (1) for appears quite naturally from the equations (7), (8) and (9) at . Specifically, equation (8) provides

Substituting into equation (9) results in

Consequently, at we get the constants , and in equation (7). Since the arctangent function is odd (), the constants for equation (3) can be rearranged as , , and . This corresponds to the original Machin formula (1) for .

Theorem 2.1.

The proof for Theorem 2.1 can be found in [10].

Lemma 2.2

Proof

As we can see from the four cases given in Theorem 2.1, the largest possible value for is and it occurs at (see the example above). Therefore, for any integer at integer , the constant in the equation (7) cannot be an integer. □

Theorem 2.3.

Proof

This is the simplest kind of Ramanujan nested radical and its proof is straightforward. Let . Then

Squaring both sides,

and solving results in two possible solutions, and . Since for any positive index the value is always positive, we exclude the solution . □

Lemma 2.4.

Proof

The proof follows immediately from Theorem 2.3 since

Lemma 2.5.

Proof

Using equation (8) that defines by the floor function, the limit can be rewritten as

(11)

By definition, the fractional part given by the difference

is positive and cannot be greater than 1. Therefore, the limit (11) can be rewritten in the form

Lemma 2.6

We have that .

(12)

Proof

Equation (9) is too hard to work with directly, so we start with the limit (11) from Lemma 2.5. Since the limit is 1, the limit of the ratio of the reciprocals of its numerator and denominator must also be 1,

(13)

From Theorem 2.3 and Lemma 2.4,

and

(14)

Since both the numerator and denominator in (13) tend to zero as tends to infinity and since as , we can rewrite (13) as

or

(15)

Since equation (6) is valid for an arbitrarily large integer , (15) implies that

(16)

However, we also have

(17)

since equation (7) is also valid at an arbitrarily large integer . Comparing the limits (16) and (17), we get

(18)

Equation (18) is valid if and only if

so , which is (12). □

Lemma 2.7.

Proof

The limit (14) implies that

(19)

From (12) and (19) we conclude that as , both and tend to infinity. Thus, according to equation (5), Lehmer’s measure for the two-term Machin-like formula (7) for tends to zero with increasing . □

Theorem 2.8

Proof

There is only one single-term Machin-like formula (10) for such that the constants and are both integers. Therefore, in equation (6), at any integer the argument of the arctangent function cannot be represented as the reciprocal of an integer; that is, is not an integer. Therefore,

and

This implies

or

or

(20)

We make (20) into an equality by adding a negative error term such that

Defining the constant in accordance with equation (9), we find the error term to be

(21)

Since is negative, the constant is also negative. □

3. Iteration Methods

3.1 Arctangent Function

Since in equation (7) the constant is an integer, the first arctangent function term can be computed by any existing method. For example, we can use Euler’s formula for the arctangent function

(22)

Chien-Lih used this formula to develop his iteration method for generating the two-term Machin-like formula for [11] and later he found an elegant derivation of this formula [15].

We derived another series expansion of the arctangent function [5, 12]:

(23)

It interesting that generalizing the derivation method that was used to get equation (23), we can find by induction the identity

where is the order of arctan function expansion; that yields simple approximations like

and

since .

The representation (23) of the arctangent function is not optimal for algorithmic implementation, since it deals with complex numbers. Fortunately, as we showed in [4], this series expansion can be significantly simplified to

(24)

where the expansion coefficients are computed by iteration:

Both series expansions (22) and (24) converge rapidly and need no undesirable irrational numbers to compute . However, the computational test we performed shows that the series expansion (24) converges more rapidly by many orders of magnitude than Euler’s formula (22) (see Figures 2 and 3 in [4]). Therefore, the series expansion (24) is more advantageous and can be taken to compute the first arctangent function term from the two-term Machin-like formula (7) for .

The second arctangent function term in equation (7) should not be computed by straightforward substitution of the constant into equation (24). As mentioned, computing with a ratio of numbers with many digits should be avoided. Instead, the second arctangent function term in equation (7) can be computed by Newton–Raphson iteration.

3.2 Rational

Once the value of the integer is chosen, it is not difficult to determine the integer by using equation (8) with the help of Mathematica. However, determining the second constant with (9) is very hard with increasing , as already mentioned. To overcome this, we proposed a different method [4]. We define the very simple two-step iteration for ,

where

and

Then

(25)

For , the second arctangent term in (7) deals only with a rational number . As increases, the number of digits in the numerator and denominator of the constant increases. For example, at , equation (8) yields

and using (25) we find

Consequently, the two-term Machin-like formula (7) for is generated as

Lehmer’s measure for this two-term Machin-like formula for is .

However, if we take , then

and using (25) we get

The corresponding two-term Machin like formula for is

for which Lehmer’s measure is only . Such a large number of digits in the numerator and denominator in the second arctangent function may look unusual. However, some formulas for obtained from the Borwein integrals involving the sinc function can also result in ratios of integers with a large number of digits. For example, Bäsel and Baillie reported a formula for that uses a quotient with 453,130,145 digits in the numerator and 453,237,170 digits in the denominator [16]; you can download a file with all the digits of the constant from [17].

As we can see from these examples, Lehmer’s measure decreases with increasing . However, that occurs simultaneously with a rapid increase in the number of digits in the numerator and denominator of the constant . As a result, taking powers of such fractions becomes very slow. This raises the doubt that Lehmer’s measure (5) is indeed relevant for a given Machin-like formula for when at least one coefficient is rational.

To resolve this problem, we considered applying the Newton–Raphson iteration [18]. Specifically, we showed that each consecutive iteration doubles the number of correct digits in the second term of the arctangent function in equation (7). This method is based on the iteration formula:

(26)

such that

The most important advantage of (26) is that the rational number is not involved in the computation of the trigonometric functions. As we can see from (26), is no longer problematic because it is not taken to a power, nor is it the argument of sine or tangent, which consumes most of the runtime. Instead, it is only applied in a single subtraction. This single subtraction (that can be implemented by changing the precision) takes a negligibly small amount of time as compared to the time to compute or .

To reduce the number of trigonometric functions from two to one, it is convenient to put equation (26) into the form

(27)

using the elementary trigonometric identities

and

The tangent function can be found, for example, by using the equation

representing the ratio based on the Maclaurin series expansions for the sine and cosine functions. Alternatively, we can use the series expansion

where is a Bernoulli number. There are several other ways to compute the tangent, like continued fractions [19, 20] or Newton–Raphson iteration again [21]. Perhaps the argument reduction method for the tangent function can also be used to improve accuracy, but we did not implement that, to keep the algorithm as simple as possible.

3.3 Tangent Function

Equation (27) is based on the Newton–Raphson iteration method. However, this iteration formula contains the tangent function. We showed [18] that once the first arctangent term is computed, the number of correct digits in can be doubled at each consecutive step of the iteration as with the Newton–Raphson iteration method. To approximate the tangent function with high accuracy, we can apply the Newton–Raphson iteration again [21]. The derivation of the iteration-based equation for the tangent function is not difficult. Let .

Using the Newton–Raphson iteration formula

where

we get

(28)

such that

Substituting into (28) yields

(29)

The iteration-based expansion of the series (24) for the arctangent function converges very rapidly. Therefore, we can apply it to compute the arctangent function in equation (29).

4. Implementation

4.1 Linear Convergence

The series expansion (24) of the arctangent function can be computed as follows.

Next we define the nested radicals consisting of square roots of 2.

This computes the constants and for the two-term Machin-like formula (7) for at .

For the constant , we use the iteration-based formula (25) instead of equation (9).

Define a function for the Lehmer’s measure corresponding to a two-term Machin-like formula (7) for .

Here is Lehmer’s measure for the case .

The accuracy improves with each iteration, so we do not need to use the highest accuracy at each step. At , the Newton–Raphson iteration-based formula (29) gives 4 to 5 correct digits of the tangent function at each step. Therefore, it is reasonable to use the argument in , where is taken to minimize rounding or truncation errors.

Recall that . As an initial guess for the Newton–Raphson iteration, we choose , since this is close to the actual value of the tangent function .

This sets up the recurrence for as defined in (29).

This part of the program, which computes the tangent function, takes most of the runtime. It uses the Newton–Raphson iteration built on the basis of the series expansion (24) of the arctangent function (see (29)).

This sets up the Newton–Raphson iteration formula (27).

The next part of the program invokes the value and performs just a few arithmetic operations. As mentioned, the numerator and denominator of contain many digits, but they are not involved in computing the tangent function. Only a minor part of the time is needed to subtract this number (see equation (27)). Consequently, Lehmer’s measure applies unconditionally.

The table shows how the values of the arctangent function gain digits at each iteration step.

This shows the linear rate of convergence to in terms of the number of accurate digits.

After the first two iterations, each of the following iterations adds five correct digits to the approximation of .

The convergence rate increases as Lehmer’s measure decreases, which can be readily confirmed by increasing and readjusting the parameter in this algorithm. No undesirable irrational numbers are needed. Furthermore, since Lehmer’s measure can be made vanishingly small, there is no upper bound in the convergence rate per iteration.

4.2 Quadratic Convergence

Consider a variation of the algorithm based on the Newton–Raphson iterations for the tangent function that can be implemented to get quadratic convergence to . Assume that only decimal digits of are known at the beginning.

We determined experimentally that at , equation (24) provides four or five correct digits of at each successive step. Therefore, it is sufficient to take terms. However, to exclude truncation and rounding errors, we use terms of the arctangent function.

We define to determine the accuracy of computation and for the number of summation terms in approximation (24) of the arctangent function.

The multiplier was found experimentally. When , we restrict its rapid growth to , as we do not need extra accuracy at this stage. We add 10 to exclude truncation and rounding errors. We have taken the initial value .

We use equation (29).

For our choice of , here is the required index.

Once the tangent function is computed, we substitute it into equation (27). The value has double the accuracy of with only one iteration.

The approximate values of the arctangent function by iteration and by the built-in function match to 100 places.

Since we got with double the accuracy, it can now be used to compute with significantly improved accuracy.

This shows that the number of correct decimal digits of doubled from 50 to 101.

More directly, this shows the complete match between the computed approximation of and that provided by Mathematica.

The first arctangent function in the two-term Machin-like formula (7) for can also be found by using the same algorithm based on the Newton–Raphson iteration. Consequently, this method results in quadratic convergence to . However, unlike the Brent–Salamin algorithm (also known as the Gauss–Brent–Salamin algorithm) with quadratic convergence to [2], our approach does not involve any irrational numbers. The number of summation terms in equation (24) and the number of iteration cycles for computation of the tangent function (29) decrease with increasing . This can be confirmed by using the code given here. To the best of our knowledge, this is the first algorithm showing the feasibility of quadratic convergence to without using any irrational numbers.

5. Conclusion

In this article, we presented a new algorithm to compute the two-term Machin-like formula (7) for and showed an example where the condition was not necessary in order to validate Lehmer’s measure (5). Since this algorithmic implementation lets us avoid subsequent exponentiation of the second constant , this approach may be promising for computing more rapidly without using irrational numbers.

Acknowledgments

This work is supported by National Research Council Canada, Thoth Technology, Inc., York University, Epic College of Technology and Epic Climate Green (ECG) Inc. The authors wish to thank the reviewer for useful comments and recommendations. Constructive suggestions from the editor that improved the content of this work are greatly appreciated.

References

[1]	P. Beckmann, A History of Pi, Boulder, CO: Golem Press, 1971.
[2]	L. Berggren, J. Borwein and P. Borwein, Pi: A Source Book, 3rd ed., New York: Springer, 2004.
[3]	J. Borwein and D. Bailey, Mathematics by Experiment. Plausible Reasoning in the 21st Century, 2nd ed., Wellesley, MA: AK Peters, 2008.
[4]	S. M. Abrarov and B. M. Quine, “An Iteration Procedure for a Two-Term Machin-like Formula for Pi with Small Lehmer’s Measure.” arxiv.org/abs/1706.08835.
[5]	S. M. Abrarov and B. M. Quine, “The Two-Term Machin-like Formula for Pi with Small Arguments of the Arctangent Function.” arxiv.org/abs/1704.02875.
[6]	D. H. Lehmer, “On Arccotangent Relations for ,” The American Mathematical Monthly, 45(10), 1938, pp. 657–664. doi.org/10.2307/2302434.
[7]	M. Wetherfield, “The Enhancement of Machin’s Formula by Todd’s Process,” The Mathematical Gazette, 80(488), 1996, pp. 333–344. doi.org/10.2307/3619567.
[8]	J. S. Calcut, “Gaussian Integers and Arctangent Identities for ,” The American Mathematical Monthly, 116(6), 2009, pp. 515–530. www.jstor.org/stable/40391144.
[9]	H. Chien-Lih, “More Machin-type Identities,” The Mathematical Gazette, 81(490), 1997, pp. 120–121. doi.org/10.2307/3618793.
[10]	E. W. Weisstein. “Machin-like Formulas” from Wolfram MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/Machin-LikeFormulas.html.
[11]	H. Chien-Lih, “Some Observations on the Method of Arctangents for the Calculation of ,” The Mathematical Gazette, 88(512), 2004, pp. 270–278. www.jstor.org/stable/3620848.
[12]	S. M. Abrarov and B. M. Quine, “A Formula for Pi Involving Nested Radicals,” The Ramanujan Journal, 46, 2018, pp. 657–665. doi.org/10.1007/s11139-018-9996-8.
[13]	OEIS. “Decimal Expansion of Pi,” A000796. oeis.org/A000796.
[14]	Wolfram Cloud. “A Wolfram Notebook Playing with Machin-like Formulas.” develop.open.wolframcloud.com/objects/exploration/MachinLike.nb.
[15]	H. Chien-Lih, “An Elementary Derivation of Euler’s Series for the Arctangent Function,” 89(516), 2005, pp. 469–470. doi.org/10.1017/S0025557200178404.
[16]	U. Bäsel and R. Baillie, “Sinc Integrals and Tiny Numbers.” arxiv.org/abs/1510.03200.
[17]	S. M. Abrarov and B. M. Quine, “The Rational Number for the Two-Term Machin-like Formula for Pi Computed by Iteration.” yorkspace.library.yorku.ca/xmlui/handle/10315/33173.
[18]	S. M. Abrarov and B. M. Quine, “Efficient Computation of Pi by the Newton–Raphson Iteration and a Two-Term Machin-like Formula,” International Journal of Mathematics and Computer Science, 13(2), 2018, pp. 157–169. ijmcs.future-in-tech.net/13.2/R-Abrarov.pdf.
[19]	J. Havil, The Irrationals: A Story of the Numbers You Can’t Count On, Princeton, NJ: Princeton University Press, 2012.
[20]	M. Trott. “Continued Fraction Approximations of the Tangent Function” from the Wolfram Demonstrations Project—A Wolfram Web Resource. demonstrations.wolfram.com/ContinuedFractionApproximationsOfTheTangentFunction.
[21]	J.-M. Muller, Elementary Functions. Algorithms and Implementation, 3rd ed., Boston: Birkhäuser, 2016.
S. M. Abrarov, R. Siddiqui, R. Jagpal and B. M. Quine, “Unconditional Applicability of Lehmer’s Measure to the Two-Term Machin-like Formula for Pi,” The Mathematica Journal, 2021. doi.org/10.3888/tmj.23-2.

About the Authors

Sanjar M. Abrarov received a BSc degree in Physics, and CSc and PhD degrees in Physics and Engineering. He is a research scientist at the Algonquin Radio Observatory at Thoth Technology, Inc., Canada, and a senior lecturer at Epic College of Technology, Canada. He is a recipient of the Canadian Astronautics and Space Institute Alouette (2010).

Sanjar M. Abrarov
Thoth Technology, Inc.
Algonquin Radio Observatory
Achray Rd, RR6
Pembroke, Canada, K8A 6W7
abrarov@alumni.yorku.ca
sanjar@thothx.com

Rehan Siddiqui received BSc (Honours) and MSc degrees in Physics, an MEng in Power Engineering, and MSc and PhD degrees in Physics and Astronomy. He is a recipient of the Queen Elizabeth II (2015), Vernon Oliver Stong (2015) and Dr. Ralph Nicholls (2016) graduate scholarships, and of the York University Postdoctoral Fellowship (2017). He is a contract faculty and research associate at York University and a dean at Epic College of Technology, Canada.

Rehan Siddiqui
Dept. Earth and Space Science and Engineering
York University
4700 Keele St.
Toronto, Canada, M3J 1P3
rehanrul@yorku.ca
rehan@epiccollege.ca

Rajinder K. Jagpal received BSc and MSc degrees in Physics, and MSc and PhD degrees in Physics and Astronomy. He is a contract faculty and research associate at York University, Canada, and a director of Epic College of Technology, Canada. He is a recipient of the Canadian Astronautics and Space Institute Alouette (2010).

Rajinder Jagpal
Dept. Physics and Astronomy, York University
4700 Keele St., Toronto, Canada, M3J 1P3
raj@epiccollege.ca

Brendan M. Quine received BSc, PhD and DPhil degrees in Physics. He is an associate professor at York University, Canada, and a director of the Algonquin Radio Observatory at Thoth Technology, Inc., Canada. He is a recipient of the Canadian Astronautics and Space Institute Alouette (2010).

Brendan M. Quine
Dept. Physics and Astronomy
York University, 4700 Keele St.
Canada, M3J 1P3
bquine@yorku.ca