Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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? –  Emmad Kareem May 6 '12 at 23:31
    
Ok just added one. –  pajamas 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. –  Emmad Kareem 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. –  pajamas 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. –  pajamas May 6 '12 at 23:47
show 2 more comments

2 Answers

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);
end
share|improve this answer
add comment

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
add comment

Your Answer

 
discard

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.