Coding Challenge for Vieta's Formulas

07122018, 11:15 PM
(This post was last modified: 07132018 06:37 PM by Namir.)
Post: #1




Coding Challenge for Vieta's Formulas
I am interested in coding general cases of the Vieta's formulas (check the Wikipedia article to see these formulas in a highlevel language like VBA, Python, Matlab, and C++. The target is to have a function that sums up the squares of the LHS  RHS of each Vieta formula:
F(X,a) = (LHS1  RHS1)^2 + (LHS2  RHS2)^2 + ... + (LHSn  RHSn)^2 Where: LHS1 = sum(X(i)) for i = 1 to n RHS1 =  a(n1)/a(n)) LHS2 = ((X(1)*X(2) + X(1)*X(3) + ... + X(1)*X(n)) + ((X(2)*X(3) + X(2)*X(4) + ... + X(2)*X(n)) + ... + X(n1)*X(n) RHS2 = a(n2)/a(n)) .... LHSn = product(X(i)) for i = 1 to n RHSn = (1)^n * a(0)/a(n) The parameters are the array X() which represents the guesses for the roots, and array a() that represents the polynomial coefficients. The Wikipedia article designates a(n) as the coefficient for x^n and a(0) as the constant term. Good luck to us all!! Namir 

07132018, 03:34 AM
Post: #2




RE: Coding Challenge for Vieta's Foummulas
.
Hi, Namir 5:30 am here so just a couple quick observations: (07122018 11:15 PM)Namir Wrote: F(X,a) = (LHS1  RHS1)^2 + (LHS2  RHS2)^2 + ... + (LHSn  RHSn)^2 1) without loss of generality you can consider a(n) to be 1. If it's not, simply divide all other coefficients by it before doing anything else. 2) there's a typo in your RHSn, (1)^2 is obviously wrong. Regards. V. . 

07132018, 06:19 AM
(This post was last modified: 07132018 06:38 PM by Namir.)
Post: #3




RE: Coding Challenge for Vieta's Formulas
1) Yes a(n) can be 1.
2) Error corrected. Thanks! Namir 

07132018, 11:50 AM
(This post was last modified: 07132018 06:36 PM by Namir.)
Post: #4




RE: Coding Challenge for Vieta's Foumulas
The Vieta formulas are related to the Elementary symmetric polynomial. Check the Wikipedia link.
The solution to my challenge lies in the ability to generate highlevel programming language code for the Elementary Symmetric Polynomials. 

07132018, 02:46 PM
Post: #5




RE: Coding Challenge for Vieta's Foummulas
.
G'day, Namir: Just a question: (07122018 11:15 PM)Namir Wrote: The parameters are the array X() which represents the guesses for the roots, and array a() that represents the polynomial coefficients As you say X() represents the guesses for the roots, which might be complex, then we must assume X() is a complex array, right ? Also, you say the array a() represents the coefficients. Are they assumed to be complex in the general case or are you considering just polynomials with real coefficients ? Finally, pretty please, correct that "Foummulas" (sic) in the thread title, it's a real eyesore. XD Regards. V. . 

07132018, 06:35 PM
(This post was last modified: 07132018 07:42 PM by Namir.)
Post: #6




RE: Coding Challenge for Vieta's Formulas
(07132018 02:46 PM)Valentin Albillo Wrote: . Yes both arrays X() and a() can be complex and the mathematical operations work with complex numbers. For programming languages like Matlab, the operations and functions automatically handle real and complex numbers. For other languages (not sure about Python) one may have to use complex operators and functions just to be sure that the math expressions can handle real and complex numbers. 

07142018, 12:50 AM
Post: #7




RE: Coding Challenge for Vieta's Formulas
.
Hi, Namir: This is my entry for your challenge, which fully meets your requirements. I'm not sure if you consider HP71B BASIC a "highlevel" language but this 4liner (199 bytes) delivers the goods in the most efficient, economical way and further, if you don't like 71B BASIC you can convert it to your preferred dialect (VBA, Excel, Maple, Python, HPPPL, even RPL) in 5 minutes flat as it's eminently understandable. Let's see: >LIST 1 DESTROY ALL @ OPTION BASE 0 @ INPUT "Deg: ";N @ COMPLEX A(N),B(N),X(N1) 2 MAT INPUT X,A @ MAT B=ZER @ B(N)=1 @ FOR I=1 TO N @ FOR J=NI TO N1 3 B(J)=B(J+1)B(J)*X(I1) @ NEXT J @ B(N)=B(N)*X(I1) @ NEXT I @ MAT DISP B 4 MAT A=(1/A(0))*A @ MAT B=BA @ DISP "F(X,a) = ";FNORM(B)^2 Notes:
1) Let's see some examples. First a 3rd degree polynomial with 3 real roots (2, 3 and 4): P(x) = 5*x^3 45*x^2 +130*x 120 >RUN Deg: 3 X(0)? 2.1,3.2,3.9 { approximations to the exact roots } A(0)? 5,45,130,120 { coefficients, its roots are 2, 3 and 4 } (1,0) { always 1 } (9.2,0) { x1 + x2 + x3 = 2.1 + 3.2 + 3.9 = 9.2 } (27.39,0) { x1*x2 + x1*x3 + x2*x3 = 2.1*3.2+2.1*3.9+3.2*3.9 = 27.39 } (26.208,0) { x1 * x2 * x3 = 2.1*3.2*3.9 = 26.208 } F(X,a) = 6.847364 { (9.2(9))^2+(27.3926)^2+(26.208(24))^2 = 6.847364 } When the approximate roots finally converge to the exact roots, you get F(X,a) = 0 as it should: >RUN Deg: 3 X(0)? 2,3,4 A(0)? 5,45,130,120 (1,0) (9,0) (26,0) (24,0) F(X,a) = 0 2) Let's see a more complicated example, this time a 6th degree polynomial with 2 real roots and 4 complex roots: P(x) = 5*x^6 45*x^5 +225*x^4 425*x^3 +170*x^2 +370*x 500 >RUN Deg: 6 X(0)? (0.99,1.01),(0.99,1.01),1.02,1.98,(2.99,3.99),(2.99,3.99) { approximations } A(0)? 5,45,225,425,170,370,500 { its roots are (1,+1), 1, 2, (3,+4) } (1,0) { always 1 } (8.92,0) { (0.99,1.01)+(0.99,1.01)1.02+1.98+(2.99,3.99)+(2.99,3.99) = 8.92 } (44.3228,0) (82.261144,0) (30.30225268,0) (75.8316409248,0) (100.425361372,0) { (0.99,1.01)*(0.99,1.01)*(1.02)*1.98*(2.99,3.99)*(2.99,3.99) = 100.425361372 } F(X,a) = 25.1755080455 3) Finally, a 3rd degree polynomial with complex coefficients: (3 complex roots, none are conjugates): P(x) = x^3 +(9 12*i)*x^2 +(21 +64*i)*x +(85 20*i) >RUN Deg: 3 X(0)? (1.1,1.9),(2.9,4.1),(4.9,6.1) { complex approximations } A(0)? 1,(9,12),(21,64),(85,20) { coefficients, its roots are (1,2), (3,4), (5,6) } (1,0) { always 1 } (8.9,12.1) { (1.1,1.9)+(2.9,4.1)+(4.9,6.1) = (8.9,12.1) } (21.6,63.82) { (1.1,1.9)*(2.9,4.1)+(1.1,1.9)*(4.9,6.1)+(2.9,4.1)*(4.9,6.1) = (21.6,63.82) } (83.662,21.038) { (1.1,1.9)*(2.9,4.1)*(4.9,6.1) = (83.662,21.038) } F(X,a) = 3.280088 Bst regards and have a nice weekend. V. . 

07142018, 01:36 AM
(This post was last modified: 07142018 11:05 AM by Namir.)
Post: #8




RE: Coding Challenge for Vieta's Formulas
Most fascinating reading and solution!!! The simplicity of your solution makes me speechless. I have not seen any code, on the Internet, for a general calculations for Vieta's Formulas!
Namir 

07142018, 03:13 PM
Post: #9




RE: Coding Challenge for Vieta's Formulas
I am still shaking my head at the simplicity and elegance of your solution. I have seen anything comparable on the Internet!!
My attempt to solve the challenge would take me thought a complicated and difficult route!! :( Namir 

07212018, 01:10 PM
(This post was last modified: 07212018 01:47 PM by Namir.)
Post: #10




RE: Coding Challenge for Vieta's Formulas
I found a C++ listing that calculates the polynomial coefficnts, given the roots of that polynomial, using the Vieta's Formulas. I checked the code using Visual Studio 2017 Community Edition. The C++ code had a small error in the range of the nested loop (for j = ...). I corrected it and then translated it into Excel VBA. Here is the version that uses Option Base 1 arrays:
Code: Option Explicit The above code uses the following spreadsheet columns (the first row has headings and so value appear as of row 2): 1) Column A has the polynomial coefficients with cell A2 being the coefficient of the higher term. There are N + 1 entries in this column. 2 Column B has N roots, starting with cell B2. 3) Column C has the output array B() which should match the values in the first columns if the roots match the polynomial coefficients. The first value appears in cell C2. 4) Cell B7 displays the value of the Vieta's Formula function. The VBA code is similar to, but not an exact match, to Vallentin's HP71B code. Note that the values in array B() are in reverse order of the values in array A(). 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)