Talk:Machin-like formula

Efficiency

The Efficiency section ignores that the time needed for multiplication and division often increases with the size of the multiplier or divisor. As some of the times shown are not so different for the different series, it is easily possible that some that are claimed faster are actually slower. (Not to mention the additional time debugging some series.) Gah4 (talk) 09:10, 29 October 2015 (UTC)[reply]

This page focuses on the theoretical efficiency of these formulae, not the actual complexities in implementing them in pi-calculating programs. If you wish to discuss these topics, I suggest you create a separate page, or expand on the "Approximations of Pi" page. — Preceding unsigned comment added by 202.212.253.67 (talk) 01:03, 10 February 2017 (UTC)[reply]

I suppose so. At the time, I was doing it on an IBM 360/20, one of the slower machines one would ever try. In most cases, there is a discontinuity in the time when the divisor gets bigger than a machine dependent value, usually related to the machine word size. In my case, the divisor could only be up to 15 decimal digits. Even more, though, for the 360/20 the time for doing division depends on the number of decimal digits in the divisor. A quick calculation showed that one that the theory showed would be faster, was going to be slower on the machine I had available. Gah4 (talk) 02:15, 10 February 2017 (UTC)[reply]

Note

Note that the origin is called C in the diagram. The letter O in the diagram refers to the point (1,1). — Preceding unsigned comment added by 86.134.223.175 (talk) 08:16, 7 July 2016 (UTC)[reply]

Other Formula by Euler

Wikipedia itself notes elsewhere another formula for π/4 attributed to Leaonard Euler:

π/4 = 5 atan(1/7) + 2 atan(3/79) Computing π

I guess it also matches the schema and could be further of historical interest. Jan Burse (talk) 21:17, 15 February 2017 (UTC)[reply]

I believe that this particular formula is indeed of some historical interest and I would encourage you to add it. It's only since the dawn of the computer age that anybody sets $a_{n}$ to anything other than one. The formula you have cited is a rare exception, and is therefore noteworthy.

There are two equations frequently attributed to Euler:

{\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}}

{\frac {\pi }{4}}=5\arctan {\frac {1}{7}}+2\arctan {\frac {3}{79}}

The former has an estimated runtime of 7.0588, and the latter has an estimated runtime of 2.7646 . The latter is clearly faster. Does that make it better? We already cite the former version. Shouldn't we also cite the version that is known to be better?

There are other web pages that list thousands of formula variations. I maintain that the Wikipedia page should limit itself to just a handul of variations, those that are somehow noteworthy. I believe that the equation you have cited qualifies for this.

The question is, where should it go? I'm thinking right next to equation 5, but that's up to you.

I have often wondered why the Wikipedia page doesn't cite the following equation:

3{\frac {\pi }{4}}=5\arctan {\frac {1}{2}}+\arctan {\frac {3}{79}}

It too is a rare exception, and is therefore noteworthy. Shouldn't we have at least one example where $c_{0}$ is something other than one? If I might answer my own question, it's because this equation is merely a trivial re-combination of two other well known equations:

{\frac {\pi }{4}}=2\arctan {\frac {1}{2}}-\arctan {\frac {1}{7}}

{\frac {\pi }{4}}=5\arctan {\frac {1}{7}}+2\arctan {\frac {3}{79}}

The former is Hermann's. The latter is the version of Euler that you have cited.

I would like to see the community discuss this issue more. What equations are noteworthy enough to be added to the Wikipedia page? We should come to a concensus as to what the rules are. Permit me to propose:

1. The equation is of some historical significance. Or,

2. At the time the equation was discovered, it was the fastest equation known.

The problem with the latter is that brought up by Gah4. Many of the equations we have cited are theoretically very fast, but due to the extreme size of $b_{n}$ they require the use of synthetic arithmetic. Smwolfe (talk) 18:52, 18 February 2017 (UTC)[reply]

just for fun I compared the different formulas in a finite sum approximation of integ 1/(1+x^2) dx, the Euler one is also better than the plain one:

sum_k=0^(n-1) (4.0 1/(1+(k/n)^2) 1/n) at n=128

= 3.14939

sum_k=0^(n-1) (20.0 1/(1+(1/7 k/n)^2) 1/7 1/n + 8.0 1/(1+(3/79 k/n)^2) 3/79 1/n) at n=128

= 3.14182

Jan Burse (talk) 20:48, 29 July 2019 (UTC)[reply]

Since the Ruby programming language in their BigDecimal package uses the classical

machin formula, here a comparison with Euler, using Lehmer's measure after the ~~>:

{\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}

~~> 3.07736791...

{\frac {\pi }{4}}=5\arctan {\frac {1}{7}}+2\arctan {\frac {3}{79}}

~~> 2.26560388...

Jan Burse (talk) 01:39, 30 August 2022 (UTC)[reply]

The one-term formula

The reasoning on the article page seems to indicate that using the well-known single-term formula

π/4 = arctan 1

would take infinitely long to compute, since a₁/b₁ is 1 in this case, which implies that its logarithm, which stands in the denominator, is zero.

The Taylor/Maclaurin series becomes then

arctan 1 = 1 - 1/3 + 1/5 - 1/7 + 1/9 ...

a series which of course converges, albeit slowly, but I wouldn't say infinitely slowly.

Maybe the article ought to mention this particular Machin-like formula (where c₀ = c₁ = a₁ = b₁ = N = 1) as a "worst case" against which all other cases should be compared. — Tonymec (talk) 23:36, 4 August 2017 (UTC)[reply]

The problem is that the power series for arctan 1 is at the edge of convergence ( $\arctan(1+\epsilon )$ does not converge). The rough estimate for the correct digits uses an estimate against a geometric series, which doesn't work in this case. So it is not infinitley slow, but in an totally different speed class (the error is less than 1/2N after N Terms, compared to (a/b)^2N if a/b<1).LamaMaddam (talk) 14:42, 12 March 2020 (UTC)[reply]

I haven't thought about it for a while, but I think the number of digits is O(log N). I suspect that the article should mention it, but I also believe that is isn't a Machin-like formula. That is, for the same reason that 1 isn't a prime number. Reminds me, when I first learned about the harmonic series not converging, I started a sum on my HP25C (so you can figure out when that was) and let it run a few days. Gah4 (talk) 15:00, 12 March 2020 (UTC)[reply]

At the very beginning of the article, it says "Machin-like formulas have the form … where … a_n < b_n". Given this as the definition, arctan(1/1) would not be considered a valid formula. Smwolfe (talk) 16:09, 12 March 2020 (UTC)[reply]

Efficiency: missing penalty for huge numerators

As far as I can see the fraction ${\frac {10^{33}\cdot a_{n}}{10^{33}\cdot b_{n}}}$ is estimated to perform exactly the same way as the fraction ${\frac {a_{n}}{b_{n}}}$ , namely $\propto \ln {\frac {b_{n}}{a_{n}}}.$ It's true that the number of required terms for achieving a certain accuracy is exactly the same, but the calculation of ${\Bigl (}{\frac {3000000000000000000000000000000000000001}{73000000000000000000000000000000000000001}}{\Bigr )}^{999999}$ involves about 30 times as many decimal digits compared to ${\Bigl (}{\frac {3}{73}}{\Bigr )}^{999999}$ . –Nomen4Omen (talk) 17:23, 18 December 2020 (UTC)[reply]

It is not so easy to figure out the times. In the case of a power series expansion, the important calculation is from one term to the next, which in the cases shown is mostly dividing by

{b_{n}^{2}}

. If that fits in a machine word, then the division is fairly simple. If

{a_{n}}

is not one, then at each step you also multiply by

{a_{n}^{2}}

. Also, as I previously noted, on some machines the speed of multiply and divide are dependent on the actual numbers. (Many special-case multiply by zero, for example.) Note even more, that the calculations are most often done in binary, unless the machine is faster in decimal. (The IBM 360/20 has decimal divide but not binary divide.) Gah4 (talk) 22:56, 18 December 2020 (UTC)[reply]

I agree: It is not so easy to figure out the times. And even if we concentrate on really big machines and calculations which blast the size of the machine word – i.e. concentrate on algorithms for multiple word integers –, it is not so easy. But also in this case the number of digits of an operand (its „length“) should contribute (about linearly?, quadratically?) to the running time – and I cannot see this to be reflected in the considerations of the §, because

{a_{n}}

is ALWAYS accompanied by

{b_{n}},

either in the form

{\tfrac {a_{n}}{b_{n}}}

or

{\tfrac {b_{n}}{a_{n}}}

or

\ln {b_{n}}-\ln {a_{n}},

and never in the form

{a_{n}}\cdot {b_{n}}

or

\ln {a_{n}}+\ln {b_{n}}.

–Nomen4Omen (talk) 11:20, 19 December 2020 (UTC)[reply]

OK, first, calculations are always done in fixed point. Integers after moving the radix point appropriately. Now you want to do arithmetic on multiple word values. To add such values, go right to left, add, if there is overflow add one to the value to the left. (Like you learn in first grade, except the digits are now much bigger.) For divide by a value that fits in a machine word: start on the left and divide. Replace the value with the quotient. Put the remainder to the left of the next word to the right and continue to the right. This, in the general case, requres a divide with a double length dividend. Most hardware provides this, most high-level languages do not. Doing it in a high-level language, then, requires one to use a "word" size half the available size. In any case, as long as the divisor fits into the appropriate size, such as a machine word, it is easy to do, and linear in the number of words in the multiple word value. Gah4 (talk) 19:44, 19 December 2020 (UTC)[reply]

If I understand you correctly this means an additional factor of

\ln({a_{n}}{b_{n}}).

–Nomen4Omen (talk) 19:50, 19 December 2020 (UTC)[reply]

Well, it might be more like

ceil(\log 4294967296({a_{n}}))ceil(\log 4294967296({b_{n}}))

That is, log base 4294967296. So, as long as

a_{n}

and

b_{n}

aren't so big, there is no extra factor. Gah4 (talk) 00:50, 20 December 2020 (UTC)[reply]

If you mean

\lceil \log _{4294967296}({a_{n}})\rceil +\lceil \log _{4294967296}({b_{n}})\rceil

I agree 100 %. –Nomen4Omen (talk) 10:28, 20 December 2020 (UTC)[reply]

Misattribution of the formula starting with arctan(1/390112)

It was found 1993, not by Hwang Chien-Lih, but by me. See Figure 32.5-C on page 635 in the book "Matters Computational", see https://jjj.de/fxt/#fxtbook. Due to the obvious conflict of interest I will not touch the page. The material in https://jjj.de/arctan/arctanpage.html should still reflect the present state of affairs. - Joerg Uwe Arndt (talk) 11:08, 8 June 2021 (UTC)[reply]

I'm sure you do not mean 1/390122. So I corrected that in the heading.
The text talks about a formula pair. So it may well be that it's you who found the first (and important) part, but Hwang Chien-Lih may have found the pairing. I have tried to separate the 2 formulas. −Nomen4Omen (talk) 15:14, 8 June 2021 (UTC)[reply]

About checking pairs: the checking pair for the 11-term formula is not in my fxtbook, but neither is it in the Gazette article. Finding such pairs for n-term formulas with n>=3 is easy because there are more and more (inverse) arguments for the set of primes used. What I seem to have done (stopping at 10-term relations) is shown in Figure 32.5-E on page 637 in the fxtbook. - Joerg Uwe Arndt (talk) 15:42, 8 June 2021 (UTC)[reply]

I'll also try to enter a reference of yours into the article. −Nomen4Omen (talk) 08:10, 9 June 2021 (UTC)[reply]

Efficiency revisited: missing penalty for huge numerators

Nobody seems to care about this issue, all contributors measure a term $\arctan {\frac {a_{n}}{b_{n}}}$ proportional to ${\frac {1}{\log {\frac {b_{n}}{a_{n}}}}}$ , so Lehmer in Machin-like formula#Lehmer's measure and Smwolfe who entered the section Machin-like formula#Efficiency on 13:02, 10 March 2013‎ (although the latter defines $u_{n}:=3$ if $a_{n}=1$ and $u_{n}:=4$ if $a_{n}\neq 1$ , so there is a tiny penalty). But there exist formulas with huge numerator $a_{n}$ :

It is easy to find for every $b_{1},c_{1}$ a two-term formula

{\frac {\pi }{4}}=c_{1}\arctan {\frac {1}{b_{1}}}+\arctan {\frac {a_{2}}{b_{2}}}

,

namely

\arctan {\frac {a_{2}}{b_{2}}}:={\frac {\pi }{4}}-c_{1}\arctan {\frac {1}{b_{1}}}

.

Depending on $b_{1}\in \mathbb {N} ~,$ $c_{1}\in \mathbb {N}$ can be chosen such that

\left|\arctan {\frac {a_{2}}{b_{2}}}\right|<{\frac {1}{2}}\arctan {\frac {1}{b_{1}}}

.

Furthermore, $b_{1}$ can be chosen sufficiently large, so that ${\frac {1}{b_{1}}}$ and its cost ${\frac {1}{\log {b_{1}}}}$ is infinitesimal. If then the cost of $\arctan {\frac {a_{2}}{b_{2}}}$ is counted proportional to ${\frac {1}{\log {\frac {b_{2}}{a_{2}}}}}~,$ the total cost can be made infinitesimal, because ${\frac {1}{\log {\frac {b_{2}}{a_{2}}}}}<{\frac {1}{\log {b_{1}}}}~.$ –Nomen4Omen (talk) 10:02, 19 October 2021 (UTC)[reply]

New Notable Formula?

Now it makes me think the alternativ Leonhard Euler formula isn't notable, since it doesn't beat John Machine. Just found this gem by Xavier Gourdon, in parenthesis the Lehmer measure (using natural logarithm):

Leonhard Euler: π = 20*atan(1/7)+8*atan(3/79) (0.8196306179594626)

John Machine 1706: π = 16*atan(1/5)+ -4*atan(1/239) (0.8039345246997319)

? Xavier Gourdon 2001 ?: π = 20*atan(29/278)+28*atan(3/79) (0.7481464746474802)

What is the origin of the last formula? I found it here: http://numbers.computation.free.fr/Constants/PiProgram/Pi_Rational.pifast But likely there are other 2 summand formulas with a lower Lehmer mesaure? How would it be notable, other constraint among the summands?

Interesting, looks like the formula 20*atan(29/278)+28*atan(3/79) is from James Thomson, reported 1839, or possibly known already for longer. Also the formula 88*atan(24478/873121)+68*atan(685601/69049993) is found there:

XI. Investigation of a New Series for the Computation of Logarithms ; with a New Investigation of a Series for the Rectification of the Circle. By JAMES Thomson, LL.D., Professor of Mathematics in the University of Glasgow.

in Transactions of the Royal Society of Edinburgh, Band 14,Ausgabe 1

https://books.google.ch/books?id=f0ED_CKR6AsC&lpg=PA223&ots=T9XjaJnuiD&dq=69049993&hl=de&pg=PA223#v=onepage&q=69049993&f=false

Jan Burse (talk) 14:34, 15 November 2022 (UTC)[reply]

Verification of Formula

I am surprised that verification of a formula seems to be a challenge. In order to verify that

4 arctan .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠122/597⁠ - 5 arctan ⁠1/29⁠ = ⁠π/4⁠

we can apply $tan$ to both sides of the equation.
If

tan(4 arctan ⁠ 122 / 597 ⁠ - 5 arctan ⁠ 1 / 29 ⁠) = tan ⁠ π / 4 ⁠ = 1

then for a specific $\in$ (in this case $k = 0$ )

4 arctan ⁠ 122 / 597 ⁠ - 5 arctan ⁠ 1 / 29 ⁠ = ⁠ π / 4 ⁠ + k π

In order to compute $tan(m arctan ⁠ a / b ⁠)$ we consider the binary representation of $m$

\in

compute $tan(2 i arctan ⁠ a / b ⁠)$ for all $0 \leq i \leq n$ by applying

tan(arctan ⁠ a / b ⁠) = ⁠ a / b ⁠

and (recursively)

tan(2 arctan ⁠ a / b ⁠) = ⁠ 2 tan(arctan ⁠ a / b ⁠) / 1-tan²(arctan ⁠ a / b ⁠) ⁠ = ⁠ 2 ⁠ a / b ⁠ / 1- ⁠ a² / b² ⁠ ⁠ = ⁠ 2ab / b²-a² ⁠ = ⁠ 2ab / (b+a)(b-a) ⁠

and determine $tan(n Σ i=0 c i 2 i arctan ⁠ a / b ⁠)$ by applying $tan(x+y) = ⁠ tan x + tan y / 1-tan x tan y ⁠$ .
If

⁠ q 11 / q 12 ⁠ = tan(2 i arctan ⁠ a / b ⁠), ⁠ q 21 / q 22 ⁠ = tan(2 j arctan ⁠ a / b ⁠)

then

tan(2 i arctan ⁠ a / b ⁠ + 2 j arctan ⁠ a / b ⁠) = ⁠ ⁠ q 11 / q 12 ⁠ + ⁠ q 21 / q 22 ⁠ / 1- ⁠ q 11 / q 12 ⁠ ⁠ q 21 / q 22 ⁠ ⁠ = ⁠ q 11 q 22 + q 21 q 12 / q 12 q 22 - q 11 q 21 ⁠

In order to save one multiplication we compute

⁠ q 11 q 22 + q 21 q 12 / q 12 q 22 - q 11 q 21 ⁠

as

⁠ (q 11 +q 12)(q 21 +q 22)-q 11 q 21 -q 12 q 22 / q 12 q 22 -q 11 q 21 ⁠

Many intermediate results can be simplified by dividing numerator and denominator by their greatest common divisor, but integer division is more time consuming than integer multiplication, and the computation of the greatest common divisor is even more time consuming.
In this way, running a simple JAVA program using JAVA's BigInteger class Hwang Chien-Lih's formula from 2004 can be verified in a few seconds.
Even Jörg Uwe Arndt's formula from 1993 with greater coefficients can be verified in less than a minute. D6yn63t8yi (talk) 12:50, 31 March 2024 (UTC)[reply]

These formulas are all trivial to verify using the tangent addition identity:

\tan(a+b)={\frac {\tan a+\tan b}{1-\tan a\,\tan b}}

Or if you prefer,

\tan(\arctan x+\arctan y)=\tan \arctan {\frac {x+y}{1-xy}},

–jacobolus (t) 14:45, 31 March 2024 (UTC)[reply]