Viète à grande Vitesse or Accelerated Viète (kind of)
|
06-18-2024, 08:05 PM
Post: #1
|
|||
|
|||
Viète à grande Vitesse or Accelerated Viète (kind of)
.
In an earlier post I presented both an HP-42S/Free42 program and a correction factor to the Viète's formula for \(\pi\). Starting with Viète's formula \(\frac2\pi = \frac{\sqrt 2}2 \cdot \frac{\sqrt{2+\sqrt 2}}2 \cdot \frac{\sqrt{2+\sqrt{2+\sqrt 2}}}2 \cdots\) we isolate \(\pi\), limit the expression to n terms and add a correction factor c₁ to it: \(\pi \approx \frac {2^{n+1}}{ \sqrt 2 \cdot \sqrt{2+\sqrt 2} \cdot \sqrt{2+\sqrt{2+\sqrt 2}} }\cdot c_{1}\) The correction factor c₁ is \(c_{1} = 1 + \frac {\pi^{2}}{96\times 4^{n-1}}\) Instead of \(\pi\) we use its approximate value obtained after the evaluation of the first n terms in the formula, which is enough to improve the original result. For example, when n = 3 \(\pi \approx \frac {2^{4}}{ \sqrt 2 \cdot \sqrt{2+\sqrt 2} \cdot \sqrt{2+\sqrt{2+\sqrt 2}} }\) \(\pi \approx 3.12144515227\) At this point we can use the approximate value of \(\pi\) thus obtained to improve it a bit more: \(\pi \approx 3.12144515227 \cdot c_{1}\) \(\pi \approx 3.12144515227 \cdot \left(1 + \frac {3.12144515227^{2}}{96\times 4^{2}}\right)\) \(\pi \approx 3.14124564095 \) Or, on the HP-42S: Code:
3 XEQ "VWπ" -> Y: 3.12144515227 X: 3.14124564095 As we can see, despite the initial poor \(\pi\) approximation this correction factor has provided two extra correct digits compared to the ones obtained with the plain Viète's formula. That's nice, but it can be better. Why not find a second correction factor? Indeed, again the errors form a geometric progression, except that now the ratio is 16 rather than 4. The second correction factor is easy to find, we only need to compute the first element of the GP. This leads to \(c_{2} = 1 + \frac {3\cdot\pi^{4}}{10240\times 16^{n-1}}\) Now we have \(\pi \approx \left(\frac {2^{n+1}}{ \sqrt 2 \cdot \sqrt{2+\sqrt 2} \cdot \sqrt{2+\sqrt{2+\sqrt 2}} }\cdot c_{1}\right)c_{2}\) Let's check this out on Free42 and on the HP-42S: Code:
20 XEQ "VV" -> Z: 3.141592653588618236614208590772408 Y: 3.141592653589793238462642196715985 X: 3.141592653589793238462643383279502 On the HP-42S: 1 XEQ "VV" -> Z: 2.82842712475 Y: 3.06412938514 X: 3.14326223323 2 XEQ "VV" -> Z: 3.06146745894 Y: 3.13619104715 X: 3.14174642842 3 XEQ "VV" -> Z: 3.12144515227 Y: 3.14124564095 Z: 3.14159565930 4 XEQ "VV" -> Z: 3.13654849054 Y: 3.14157081551 X: 3.14159270299 5 XEQ "VV" -> Z: 3.14033115695 Y: 3.14159128636 X: 3.14159265437 9 XEQ "VV" -> Z: 3.14158772526 Y: 3.14159265356 X: 3.14159265359 I haven't investigated this any further, but it looks like we have something here. Most likely a third correction factor can be determined, and a fourth, and a fifth... If they follow a pattern than this might make for a viable method for calculation \(\pi\) to many digits. Take, for instance, the integer constants that appear in the first two correction factors, 96 and 10240. They can be written as 96 = 8² + 2⁵ and 96² + 2¹⁰, respectively. Task for another day... |
|||
06-18-2024, 08:47 PM
Post: #2
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
This seems very clever and effective - well done!
But, how do you come across these formulae for the correction factors? |
|||
06-18-2024, 10:08 PM
Post: #3
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-18-2024 08:47 PM)EdS2 Wrote: But, how do you come across these formulae for the correction factors? I made a table of the differences of the ratios between exact values and approximate values, expressed as dn=1/(?/~ ?). For example, d1=1/(?/sqrt(8)-1) = 9.031732. d1: 9,0317319891191 d2: 38,208549402779 d3: 154,92964119279 d4: 621,81742804044 … d10: 2.549.830,3750 d11: 10.199.323,600 Then I noticed dn/dn-1 ~ tends to 4 d2/d1= 4,230478655568072 d3/d2= 4,230478655568072 … d11/d10= 4,00000082358416 there’s an expression for the digits following 4.0000000…, for example, d20/d19= 4,000000000003141723513 (~pi) d21/d18= 4,00000000000078543086 (~pi/4) But I haven’t used that information. This clearly shows that dn form, in the limit, a geometric progression, ratio r = 4. Then dn=a1.r^(n-1) and d1=dn/(r^(n-1) Thus, in order to calculate the required dn for each n terms of the Vieta’s formula we choose to determine we only have to find the first theoretical term of the GP with maximum accuracy , r as we know is 4. In order to do so, we choose r in the end of the table, but not so far as the results become unreliable. Let’s try d1 = d26/(4^25) = = 9,7268336296644254929 and d1=d21/(4^20) = = 9,72683362966378941226 The we can say a1 = 9,72683362966 is accurate to twelve significant digits. At first I tried to find an approximation, a fraction or a continued fraction would do, but I couldn’t find any pattern. Then, when trying another approximation I divided 16 by 9.72683362966 and immediately recognized the result, 1.6693406685 = pi^2/6. Then I did 9.72683362966*pi^2 = 96 and bingo! I should have tried a constant identifier like W|A, but I wasn’t expecting such result. No time lost with the second constant, though. Not exactly a scientific method, but it works. (DECIMAL POINT IS COMMA – sometimes point also) |
|||
06-18-2024, 10:58 PM
(This post was last modified: 06-20-2024 05:03 PM by Albert Chan.)
Post: #4
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-18-2024 08:05 PM)Gerson W. Barbosa Wrote: Starting with Viète's formula pi/2 * cos(pi/4) * cos(pi/2^3) * cos(pi/2^4) ... = c = 1 + ε // n cosines We can run a few numbers for ε, and guess the pattern. lua> x = pi/2; c = x lua> for n=0,8 do print(c-1); x=x/2; c=c*cos(x) end 0.5707963267948966 0.11072073453959153 0.026172152977030905 0.006454542799563923 0.0016081890839749757 0.00040170815496543 0.0001004058641838057 2.5100142951428595e-05 6.274953049389964e-06 Looks like ε shrink by factor of 4, same rate as x^2 shrink. Let's get the ratio. lua> x = pi/2; c = x lua> for n=0,8 do print(x^2/(c-1)); x=x/2; c=c*cos(x) end 4.322734720679006 5.571226361829378 5.892238552264333 5.973024486623593 5.99325393013848 5.998313345647833 5.9995783278496555 5.999894581396108 5.999973645268348 Assuming number converged to 6, we get formula for ε ε = c-1 = x^2/6 = (pi/2/2^n)^2 / 6 This get the first correction. Same process get the others, but likely need more precision. (06-18-2024 08:05 PM)Gerson W. Barbosa Wrote: The correction factor c₁ is |
|||
06-19-2024, 02:50 AM
(This post was last modified: 06-19-2024 03:10 AM by Gerson W. Barbosa.)
Post: #5
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
The next correction factor appears to be
\(c_{3} = 1 - \frac {\pi^{6}}{229376\times 64^{n-1}}\) 14 XEQ “VV” ENTER ENTER 6 y^x 64 ENTER 13 y^x 229376 * / +/- 1 + * This returns \(\pi\) to 34 digits on Free42. Plain Viète would need at least 57 iterations to get nearly the same result. That’s about a four-time speed-up. — Or, programmatically, Code:
14 XEQ “VV3f” -> 3.141592653589793238462643383279503 |
|||
06-19-2024, 11:29 AM
Post: #6
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
Isn't using the correction factors (that use pi) to calculate pi a bit of cheating?
Namir |
|||
06-19-2024, 11:34 AM
Post: #7
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
How abou twequick the integers 2 in the Vietes formula to be 2+eps where eps is a small value?
Namir |
|||
06-19-2024, 11:45 AM
(This post was last modified: 06-19-2024 11:46 AM by Namir.)
Post: #8
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
And that number would be 2.007373545 to make use of the equation in your first thread. I used SOLVE in an HP-41CX emulaor.
|
|||
06-19-2024, 12:22 PM
Post: #9
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of) | |||
06-19-2024, 12:43 PM
Post: #10
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
Thanks, Gerson and Albert, for your explanations.
I'm trying to understand in what way these processes are justified - they are evidently very effective. Is there a leap of faith or an element of guessing going on? Is it perhaps the case that there's infinite variety of terms (or factors) which would be valid - so long as a term tends to zero or a factor tends to one, perhaps, as in both cases that makes it valid. So we're in a search space where we're mainly seeking simplicity. Simpler is better. But also, some choices will make for a better acceleration - what's the measure of that? Why is it valid to look at numbers which seem to be converging on an integer, and then choose that integer? Perhaps this is obvious! I ask not in a spirit of attacking, of course, but a spirit of trying to understand. This seems to be a branch of experimental mathematics. |
|||
06-19-2024, 09:11 PM
(This post was last modified: 06-20-2024 10:34 AM by Gerson W. Barbosa.)
Post: #11
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-19-2024 02:50 AM)Gerson W. Barbosa Wrote: The next correction factor appears to be (Updated) Actually, \(c_{3} = 1 + \frac {9\pi{'}^{6}}{1146880\times 64^{n-1}}\) It is better to rewrite it as \(c_{3} = 1 + \frac{9}{280}\left(\frac{\pi{'}}{2^{n+1} }\right)^6 \) This is more compact and takes advantage of the \(2^{n+1}\) factor available at loop exit. Notice that \(\pi{'}\) is always the \(\pi \) approximation returned by the Viète's formula after n iterations, not the actual constant or approximations thereof obtained from previous correction factors. While apparently that does not affect the quality of the approximations, it seems to disturb the computation of the next correction factors. For example, the Viète approximations are always by default, so are the ones obtained with the first correction factor. But the results returned by my 68-byte program earlier in this thread are in excess (a change in that behavior is an indication that the accuracy limit has been reached). The replacement 62-byte program below fixes that. The 39-byte program, with only one correction factor is correct. Likewise, the first and second correction factors can be rewritten as \(c_{1} = 1 + \frac{1}{6}\left(\frac{\pi{'}}{2^{n+1} }\right)^2 \) \(c_{2} = 1 + \frac{3}{40}\left(\frac{\pi{'}}{2^{n+1} }\right)^4 \) By the way, the former is the reason of the small size of the aforementioned 39-byte program. Hopefully subsequent numerators and denominators follow a predictable pattern, but we would need at least a couple of them. I guess more than 34-digit precision is required for that, though. These are mostly conjectures. Suggestions and contributions are strongly appreciated. Code:
Input: n (number of iterations) Output: T: Viète (\(\pi{'}\)) Z: Viète (\(\pi{'}\)) Y: Viète with one correction factor X: Viète with two correction factors Edited to fix a few typos (n+2 in all exponents of 2 in the denominators, not n-1). Sorry! |
|||
06-20-2024, 01:08 AM
Post: #12
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
I think the weakness in the above calcularions is that we know what pi is ahead of time and we are trying to calculate it using Vietes method or a modification. But the logic is ... we already kow pi!! If we did not know pi then we would not know where the cutoff point is where the decimal places are accurate and where they are not. It becomes a trial and error with NO END IN SIGHT!
Namir |
|||
06-20-2024, 02:25 AM
Post: #13
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-20-2024 01:08 AM)Namir Wrote: I think the weakness in the above calcularions is that we know what pi is ahead of time and we are trying to calculate it using Vietes method or a modification. But the logic is ... we already kow pi!! If we did not know pi then we would not know where the cutoff point is where the decimal places are accurate and where they are not. It becomes a trial and error with NO END IN SIGHT! Hello, Namir, I do understand you point. It’s easy now, when \(\pi\) is known to billions — one trillion, perhaps? — of digits to “improve” on classical formulae and methods to compute the constant. Even I, a non-mathematician, was able to find a continued-fraction to correct the Gregory-Leibniz-Madhava series with help of the double-precision of the wp34s and, more recently, with help of Free-42 34-digit precision, an equivalent to the Wallis Product. When I was done with the correction factor to Gregory-Leibniz series (then I wasn’t aware of Madhava’s work in the 14th century yet) I googled to see if mine was a known result. That’s when I first knew about Madhava. The Wikipedia article on him (Madhava of Sangamagrama) read “it’s not known how Madhava found his two correction terms [for the atan(1) series]. I immediately noticed they were the first two convergents of the continued fraction I had found by myself. I couldn’t help editing the Wikipedia article accordingly. My reaction to it was my remark in post #103 of that old thread: “This appears to be quite an ancient game!”. Much to much surprise, I recently ran into this Mathlodger YouTube video: https://youtu.be/ypxKzWi-Bwg?si=ohtqR3iTAQkLYSo6 He presents a feasible method that Madhava may have used. It’s based upon the then already known to him 355/113 approximation, which provides only only eight decimal digits of \(\pi\). Yet that was enough for him to derive a continued-fraction correction term to it. I, in contrast, had 33 four decimal digits at my disposal and infinitely greater calculation capacity. But I digress. I just wanted to make clear that this is a method even ancient mathematicians sometimes resorted to, it seems. Best regards, Gerson. |
|||
06-20-2024, 06:01 AM
Post: #14
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
That's a great update Gerson, thanks!
|
|||
06-20-2024, 06:34 PM
(This post was last modified: 06-20-2024 09:21 PM by Albert Chan.)
Post: #15
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-18-2024 10:58 PM)Albert Chan Wrote:(06-18-2024 08:05 PM)Gerson W. Barbosa Wrote: Starting with Viète's formula With n cosines, cos denominator goes from 2^2 to 2^(n+1) If we have infinite cosinse, LHS is just 1 1 = c * cos(pi/2^(n+2)) * cos(pi/2^(n+3)) * cos(pi/2^(n+4)) ... // infinite cosines (06-04-2024 08:44 PM)Albert Chan Wrote: cos(pi*z/2) = (1-(z/1)²) * (1-(z/3)²) * (1-(z/5)²) * (1-(z/7)²) ... cos(pi*z/2^2) = (1-(z/1)²/4¹) * (1-(z/3)²/4¹) * (1-(z/5)²/4¹) * (1-(z/7)²/4¹) ... cos(pi*z/2^3) = (1-(z/1)²/4²) * (1-(z/3)²/4²) * (1-(z/5)²/4²) * (1-(z/7)²/4²) ... cos(pi*z/2^4) = (1-(z/1)²/4³) * (1-(z/3)²/4³) * (1-(z/5)²/4³) * (1-(z/7)²/4³) ... ... 1/4 + 1/4² + 1/4³ + ... = 1/4 / (1-1/4) = 1/3 Multiply all factors columnwise, ignore tiny z^4 or higher terms product(cos(pi*z/2^k, k=2 .. inf) ≈ (1-(z/√3/1)²) * (1-(z/√3/3)²) * (1-(z/√3/5)²) ... = cos(pi*z/2/√3) Let z = 1/2^n, we have: cos(pi/2^(n+2)) * cos(pi/2^(n+3)) * cos(pi/2^(n+4)) ... ≈ cos(pi/2^(n+1)/√3) cos(x) = 1 - x^2/2! + x^4/4! - x^6/6! + ... → 1/cos(x) ≈ 1 + x^2/2, if x is small c = 1 + ε ≈ 1/cos(pi/2^(n+1)/√3) ≈ 1 + (pi/2^(n+1)/√3)^2 / 2 = 1 + (pi/2^(n+1))^2/6 QED |
|||
06-20-2024, 11:05 PM
(This post was last modified: 06-20-2024 11:31 PM by Gerson W. Barbosa.)
Post: #16
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
The fourth correction factor is
\(c_{4} = 1 + \frac {1009\pi{'}^{6}}{132120576\times 64^{n-1}}\) This yields 3 digits per iteration: \(n:=34\) \(\pi{'}:=2^{n+1}\sin\left(\frac{\pi}{2^{n+1}}\right)\) \(\pi \approx \pi{'} \left[1+\frac{1}{6}\left(\frac{\pi{'}}{2^{n+1} }\right)^2\right] \left[1+\frac{3}{40}\left(\frac{\pi{'}}{2^{n+1} }\right)^4\right] \left[1+\frac{9}{280}\left(\frac{\pi{'}}{2^{n+1} }\right)^6\right] \left[1+\frac{1009}{40320}\left(\frac{\pi{'}}{2^{n+1} }\right)^8\right]\) \(\pi \approx 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067980\) \(\pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982\) A few more examples: .n --+----------------------------------- 01|3.139025807656737529448186707575969 02|3.141588876770281188291810937232831 03|3.141592649505441766349789100995753 04|3.141592653585701859810681899937124 05|3.141592653589789217508450492218366 06|3.141592653589793234529689331204790 07|3.141592653589793238458801082733272 08|3.141592653589793238462639630660448 09|3.141592653589793238462643379614745 10|3.141592653589793238462643383275924 11|3.141592653589793238462643383279499 12|3.141592653589793238462643383279503 Notice that the fractions in the first three factors follow a pattern: 3ⁿ⁻¹/(2ⁿ×COMB(2n+1, n)). But then unfortunately that simple pattern is lost. 16×COMB(9,4) = 2016 was of help in my search for the fourth correction factor, 40320 is exactly 20 times that value. Anyway, the first three factors suffice for a small HP-42S program, perhaps using only the stack and the Horner method. Work not totally wasted, I think. Edited to include a missing closing parentheses in the last paragraph. |
|||
06-21-2024, 02:05 AM
(This post was last modified: 06-23-2024 04:59 PM by Albert Chan.)
Post: #17
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-20-2024 11:05 PM)Gerson W. Barbosa Wrote: \(\pi{'}:=2^{n+1}\sin\left(\frac{\pi}{2^{n+1}}\right)\) This look like taylor series of asin(x) coefficients. If true, above coefficients are all correct! XCas> taylor(asin(x)/x,x,9,polynom) 1 + 1/6*x^2 + 3/40*x^4 + 5/112*x^6 + 35/1142*x^8 Indeed it is! (pi'/2^(n+1)) = sin(pi/2^(n+1)) correction = asin(pi'/2^(n+1)) / (pi'/2^(n+1)) = pi / pi' --> pi' * correction = pi Update: I had thought this is an approximation. Turns out it is an identity |
|||
06-21-2024, 10:27 AM
Post: #18
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
Using x/asin(x) coefficients, we may divide by correction instead of multiply
\(\displaystyle \pi \approx \frac{\pi{'}}{ \left[1-\frac{1}{6}\left(\frac{\pi{'}}{2^{n+1} }\right)^2\right] \left[1-\frac{17}{360}\left(\frac{\pi{'}}{2^{n+1} }\right)^4\right] \left[1-\frac{9}{280}\left(\frac{\pi{'}}{2^{n+1} }\right)^6\right] \left[1-\frac{37579}{1814400}\left(\frac{\pi{'}}{2^{n+1} }\right)^8\right]}\) |
|||
06-21-2024, 08:12 PM
Post: #19
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
(06-21-2024 10:27 AM)Albert Chan Wrote: Using x/asin(x) coefficients, we may divide by correction instead of multiply That's interesting, only the 3ⁿ⁻¹/(2ⁿ×COMB(2n+1, n)) pattern for the first three factors is lost. Viète produces 0.6 digits per iteration and each additional correction factor adds another 0.6 digits per iteration to that count. Viète computed \(\pi\) to 9 digits, so he needed at least fifteen square root extractions, not a time consuming task with pencil and paper. I take he kept a record of all intermediate results. A few more simple operations and the first factor could be found and he would double his resusts. But that would be too boring a task compared to the neat result he had achieved. A continued-fraction correction would soon form a pattern, but these seem to be possible only when the original series or product has sublinear convergence rate, not the case. Anyway, for me that has been a good exercise, even if the result is somewhat irrelevant for this millenium. Thank you for your interest and contributions! |
|||
06-23-2024, 03:00 AM
Post: #20
|
|||
|
|||
RE: Viète à grande Vitesse or Accelerated Viète (kind of)
\(\pi \approx \pi{'} \left[1+\frac{1}{6}\left(\frac{\pi{'}}{2^{n+1} }\right)^2\right]\left[1+\frac{3}{40}\left(\frac{\pi{'}}{2^{n+1} }\right)^4\right]\left[1+\frac{9}{280}\left(\frac{\pi{'}}{2^{n+1} }\right)^6\right] \)
Stack-only HP-42S/Free42 program. Only the first three correction factors, but the same program structure can be used for more factors, if available, using this Horner scheme. Code:
1 XEQ "Vh"-> 3.134123880889906682717559819775012 [ (4765631√2)/2150400 ] 14 XEQ "Vh"-> 3.141592653589793238462643383279502 |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 2 Guest(s)