Thread: 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.

Originally Posted by joeirv

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).

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.

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 C_n in an array, in increasing order so that C₀, 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: C_i ⇐ C_i-1 - a C_i.

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 - root_k) 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).