Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So I have a factored polynomial of the form (z-a)(z-b)(z-c)...(z-n) for n an even positive integer. Thus the coefficient of z^k for 0 <= k < n will be the sum of all distinct n-k element products taken from the set {a,b,...,n} multiplied by (-1)^k, I hope that makes sense, please ask if you need more clarification.

I'm trying to put these coefficients into a row vector with the first column containing the constant coefficient (which would be abc...n) and the last column containing the coefficient for z^n (which would be 1).

I imagine there is a way to brute force this with a ton of nested loops, but I'm hoping there is a more efficient way. This is being done in Matlab (which I'm not that familiar with) and I know Matlab has a ton of algorithms and functions, so maybe its got something I can use. Can anyone think of a way to do this?

Example: (z-1)(z-2)(z-3) = z^3 - (1 + 2 + 3)z^2 + (1*2 + 1*3 + 2*3)z - 1*2*3 = z^3 - 6z^2 + 11z - 6. Note that this example is n=3 odd, but n=4 would have taken too long to do by hand.

Edit: Let me know if you think this would be better posted at TCS or Math Stack Exchange.

share|improve this question
Could you provide an example? – NoChance May 6 '12 at 23:31
Ok just added one. – esproff May 6 '12 at 23:37
So the input is n=3, roots={1,2,3} and you want the output of {1,-6,11,-6}. If not correct please let me know. – NoChance May 6 '12 at 23:41
Ya for n=3 that's correct, above I was explaining how one derives these inputs for arbitrary n and arbitrary complex numbers. I also edited it above to include the alternating sign. – esproff May 6 '12 at 23:45
I was a bit careless, the number of roots is an even positive integer which I foolishly also called n, but a,b,...,n are arbitrary complex numbers. Ok I'll take a look at that answer thanks. – esproff May 6 '12 at 23:47

if you have an array {a,b,c,...,n} then your starting result is {1}

you pop of the front (a) shift a copy of the subresult by 1 (add a 0 at the end) resulting in {1,0} and add the subresult with each element multiplies by a so the new subresult is {1,a}

do it again and you get {1,a,0}+{b*1,a*b}={1,a+b,a*b} again and you get {1,a+b,a*b,0}+{c,c*(a+b),c*a*b}={1,a+b+c,a*c+b*c+a*b,c*a*b} and so on...

share|improve this answer

Have a look at the matlab routine poly.

>> poly([1,2,3])
ans =

     1    -6    11    -6

Or, to be more precise,

n = length(input);
c = [1 zeros(1,n)];
for j = 1:n
    c(2:(j+1)) = c(2:(j+1)) - input(j).*c(1:j);
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.