How to efficiently find coefficients of a polynomial from its roots? [duplicate]

Question

Given are the n roots of a polynomial whose leading coefficient is 1. How do I efficiently find out the coefficients of this polynomial?

Mathematically, I know that if the first coefficient is 1, then sum of product roots taken k at a time will be the k+1-th coefficient of the polynomial.

My code is based on this approach.

In other words, how to optimally find the sum of product of numbers from a list taken k at a time.

int main()
{

    int n, sum;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++) cin >> a[i];
    //for the second coefficient
    sum=0;
    for (int i=0; i<n; i++)
    {
        sum+=a[i];
    }
    cout << sum << endl;
    //for the third coefficient
    sum=0;
    for (int i=0; i<n; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            sum+=a[i]*a[j];
        }
    }
    cout << sum << endl;
}

I have thought of marking the numbers on whether I have taken them into the product or not for the purpose of higher coefficients, but have not written the code for it as it is practically of no use if the degree of polynomial is large.

Answer 1

You need to compute the product of linear factors

(x-z1)·(x-z2)·…·(x-zn)

This can be implemented inductively by repeatedly multiplying a polynomial with a linear factor

(a[0]+a[1]·x+…+a[m-1]·x^(m-1))·(x-zm)

= (-a[0]·zm) + (a[0]-a[1]·zm)·x + … + (a[m-2]-a[m-1]·zm) ·x^(m-1) + a[m-1]·x^m

In place this can be implemented as loop

a[m] = a[m-1]
for k = m-1 downto 1
    a[k] = a[k-1] - a[k]*zm
end
a[0] = -a[0]*zm

This gives a total of n²/2 multiplications and a like number of subtractions for the multiplication of all n linear factors.

Answer 2

First of all in C++ a[n] is a static array, so compiler need to know n during compile time, which is not the case here. So the code is "not correct" in C++. I know it will compile in gcc or other compilers, but it is against C++ standard. See C++ declare an array based on a non-constant variable? What you need here is a dynamic array, using new and delete command, or you can use more safe std::vector class from STL.

Now, the main problem here is that you need k nested loops, if you want to calculate k'th coefficients, (I am assuming 1 is 0th coefficient, not 1st, just convention). So, you need to implement variable no. of nested for loops in your code. I am posting the solution of your problem, in which I used a method to implement variable no. of nested for loops. Hope this will solve your problem.

#include <iostream>
#include <cmath>
#include <vector>  // include vector class

using namespace std;

double coeff(int,const vector<double>& );  // function declaration to to calculate coefficients

int main()
{

  int N = 5; // no. of roots

  // dynamic vector containing values of roots
  vector<double> Roots(N); 
  for(int i = 0 ; i<N ; ++i)
    Roots[i] = (double)(i+1);  // just an example, you can use std::cin


  int K = 2;  // say you want to know K th coefficient of the polynomial

  double K_th_coeff = coeff(K,Roots); // function call

  cout<<K_th_coeff<<endl; // print the value

  return 0;
}


double coeff(int k,const vector<double>& roots)
{

  int size = roots.size(); // total no. of roots

  int loop_no = k; // total no. of nested loops
  vector<int> loop_counter(loop_no+1); // loop_counter's are the actual iterators through the nested loops
  // like i_1, i_2, i_3 etc., loop_counter[loop_no] is needed to maintain the condition of the loops

  for(int i=0; i<loop_no+1; ++i)
    loop_counter[i]=0;   // initialize all iterators to zero


  vector<int> MAX(loop_no+1); // MAX value for a loop, like  for(int i_1=0; i_1 < MAX[1]; i++)... 
    for(int i=0 ; i<loop_no ; ++i)
      MAX[i] = size - loop_no  + i + 1; // calculated from the algorithm

    MAX[loop_no]=2; // do'es no matter, just != 1

    int  p1=0; // required to maintain the condition of the loops

    double sum(0); // sum of all products

    while(loop_counter[loop_no]==0)
    {
      // variable nested loops starts here

      int counter(0);
      // check that i_1 < i_2 < i_3 ....
      for(int i = 1 ; i < loop_no; ++i)
      {
        if(loop_counter[i-1] < loop_counter[i])
          ++counter;
      }


      if(counter == loop_no - 1) // true if i_1 < i_2 < i_3 ....
      {
        double prod(1);
        for(int i = 0 ; i < loop_no ; ++i)  
          prod *= roots[loop_counter[i]];   // taking products

        sum += prod;  // increament
      }


    // variable nested loops ends here...


    ++loop_counter[0];
    while(loop_counter[p1]==MAX[p1])
      {
        loop_counter[p1]=0;
        loop_counter[++p1]++;
        if(loop_counter[p1]!=MAX[p1])
          p1=0;
      }
    }

    return pow(-1.0,k)*sum;   // DO NOT FORGET THE NEGATIVE SIGN

}

I have checked the code, and it is working perfectly. If you want to know how to implement variable no.of nested for loops, just visit variable nested for loops and see BugMeNot2013's answer.