Like Tree1Likes
  • 1 Post By Nominal Animal

Polynomials by roots

This is a discussion on Polynomials by roots within the C Programming forums, part of the General Programming Boards category; I'm working on a function that asks the user for how many roots they have, that then sets the size ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    2

    Polynomials by roots

    I'm working on a function that asks the user for how many roots they have, that then sets the size an array for them to be stored in. From there I need to plug those roots in (up to x^4) and graph the polynomial. I already have a similiar on that sets up by coefficients.... I guess I'm just lost on how to code the formula for the roots.

    Let's say the user enters in -1 2 -3 4... Would my best bet be to alter them by multiplying by -1 right then and there... say maybe

    for (root_count=0; root_count<array_size; root_count++)
    printf("Enter a root:");
    scanf("%f",-1* array[root_count]);

    Can Something like be done or would I have to set up another loop to pull them back out and alter them?

    If that does work, from there I need some serious help with the loop to output what is to be graphed. I think what I would want to do is ask the user for the range and set up a while loop saying while in set range, x=range, and plug in x values from start to end in whatever the formula is...

    Am I on the right track? And if someone has a formula already written out for getting ax^4+bx^3+cx^2+dx+constant from the roots that would be cool if you shared it.

    Thank you.

  2. #2
    qny
    qny is offline
    Registered User
    Join Date
    Sep 2012
    Posts
    355
    Quote Originally Posted by joeirv View Post
    And if someone has a formula already written out for getting ax^4+bx^3+cx^2+dx+constant from the roots that would be cool if you shared it.
    formula is (x - root1) * (x - root2) * (x - root3) * (x - root4).

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    2
    Haha it's that easy? My professor made it sound like we would have to go in and come up with some algebraic expression that would do it. He must have just been refering to printing it out on the screen to show the user what the polynomial is.

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,261
    The formula that qny gave is an algebraic expression.
    Right 98% of the time, and don't care about the other 3%.

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    2,553
    Quote Originally Posted by qny View Post
    formula is (x - root1) * (x - root2) * (x - root3) * (x - root4).

    The FOIL method might help figure out how to code this.

    FOIL method - Wikipedia, the free encyclopedia

    Its the method I would try to use; it might not work.

    If that fails reading up on this might be necessary
    Binomial theorem - Wikipedia, the free encyclopedia

    Tim S.
    Last edited by stahta01; 10-07-2012 at 06:24 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  6. #6
    Registered User
    Join Date
    Oct 2011
    Posts
    838
    Consider a cubic polynomial:
    Code:
    C3 x3 + C2 x2 + C1 x + C0
    = x3 C3
    + x2 C2
    + x1 C1
    + x0 C0
    The best way to store polynomials is by stuffing the coefficients Cn in an array, in increasing order so that C0, the constant, is the first element in the array. For any polynomial order or degree degree, you have degree+1 coefficients and degree roots.

    Obviously, you can now work with polynomials of any degree, as long as you have an array large enough for the coefficients.

    What happens when you multiply a polynomial by (x - a)?
    Code:
    ( C3 x3 + C2 x2 + C1 x + C0 ) ( x - a )
    
    = C3 x3 x - a C3 x3
    + C2 x2 x - a C2 x2
    + C1 x x  - a C1 x
    + C0 x    - a C0
    
    = x4   C3
    + x3 ( C2 - a C3 )
    + x2 ( C1 - a C2 )
    + x1 ( C0 - a C1 )
    + x0 (    - a C0 )
    Ah ha! Multiplying by x simply shifts all coefficients up by one place. Multiplying the original polynomial by a constant is just multiplying all the coefficients by that same constant.

    So, each new coefficient is the same as the next lower coefficient in the original polynomial, minus the same coefficient in the original polynomial multiplied by a: Ci ⇐ Ci-1 - a Ci.

    Since the highest coefficient is only multiplied by x, we need to handle highest and lowest coefficients separately. In other words, for multiplying a polynomial coeff[] of degree degree by (x - a) , we only need (pseudocode):
    Code:
    coeff[degree + 1] = coeff[degree]
    
    for i from degree down to 1
        coeff[i] = coeff[i - 1] - coeff[i] * a
    
    coeff[0] = -coeff[0] * a
    
    degree = degree + 1
    To construct a polynomial from the known roots, just start with the first degree polynomial describing the initial root,
    Code:
    degree = 1
    coeff[1] = x
    coeff[0] = -root0
    and multiply by each (x - rootk) as outlined above.

    If you go by the FOIL method, you find that you'll get the exact same results, and a very similar algorithm -- both need a nested loop, outer loop going over the roots, and inner loop updating the polynomial coefficients. I find the way I show here easier to understand, implement, and extend.

    If you are interested in this, I'd recommend next looking at how to add two polynomials of different degree together (yes, it is very, very simple!), and how to multiply two polynomials together (which is more complex, but if you remember how to do it on paper, it should prove rather straightforward).
    stahta01 likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 05-17-2011, 12:34 AM
  2. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  3. polynomials
    By Emeighty in forum C++ Programming
    Replies: 4
    Last Post: 08-18-2008, 08:52 AM
  4. Roots??
    By -JM in forum C++ Programming
    Replies: 7
    Last Post: 07-05-2005, 10:37 AM
  5. polynomials
    By spinner in forum C Programming
    Replies: 2
    Last Post: 04-10-2003, 06:23 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21