Multiplying Two Polynomials

What I have here works only for multiplying a one term polynomial by a multiple term polynomial... and even then it's not formatted correctly. When I perform multiplication with two multiple term polynomials the array answer[] contains the correct products yet they're not lined up. Hopefully an example will make it clearer:

As it is now:

Quote:

---

(5)(2x^3 + 4x^2 + 6x + 3)

---

produces:

Quote:

---

10x^3 + 20x^2 + 30x + 15

---

which is very nnnnice, but this is not enough.



The problem:

Quote:

---

(2x + 3)(2x^3 + 3x^2 + 4x + 5)

---

produces:

Quote:

---

4x^7 + 6x^6 + 8x^5 + 10x^4 + 6x^3 + 9x^2 + 12x + 15

---

and of course what I wish is:

Quote:

---

4x^4 + 12x^3 + 9x^2 + 12x + 15

---

Now I realize this code may be long to some, but my goal in writing is usually to get the functions to properly work then I usually focus on cleanup and code shortening, so please don't flame the length.

Code:

---

.....

  int total;  // total in size of the final output
  int larger, smaller;  // determine the larger - smaller of two polynomials
  int i, j, k; // index advancers
  double *temp, answer[ 1024 ]; //[ (smaller - 1) + larger ]; // final storage

  if ( One.getSize() > Two.getSize() ) {
    larger = One.getSize();  // first poly has more terms
    smaller = Two.getSize(); // second poly has less terms
    double largeArr[ larger ], smallArr[ smaller ];
    for ( k = 0; k < larger; k++ ) {
      largeArr[ k ] = One.getOneCoeff( k );
    }
    for ( k = 0; k < smaller; k++ ) {
      smallArr[ k ] = Two.getOneCoeff( k );
    }
    // perform (1 or 0)*(x^n-.. + x + C)
    if ( smaller < 2 ) {
      for ( j = 0; j < larger; j++ ) {
        answer[ j ] = smallArr * largeArr[ j ];
      }
    } else { // otherwise perform multiple term multiplication 
      k = 0; // set outside because it can't be reset inside
      for ( i = 0; i < smaller; i++ ) {
        for ( j = 0; j < larger; j++, k++ ) {
          answer[ k ] = largeArr[ j ] * smallArr[ i ];
        } 
      }
    }
  } else if ( One.getSize() < Two.getSize() ) {
    larger = Two.getSize();  // second poly has more terms
    smaller = One.getSize(); // first poly has less terms
    double largeArr[ larger ], smallArr[ smaller ];
    for ( int k = 0; k < larger; k++ ) {
      largeArr[ k ] = Two.getOneCoeff( k );
    }
    for ( int k = 0; k < smaller; k++ ) {
      smallArr[ k ] = One.getOneCoeff( k );
    }
    // perform (1 or 0)*(x^n-.. + x + C)
    if ( smaller < 2 ) {
      for ( j = 0; j < larger; j++ ) {
        answer[ j ] = smallArr * largeArr[ j ];
      }
    } else { // otherwise perform multiple term multiplication
      k = 0; // set outside because it can't be reset inside
      for ( i = 0; i < smaller; i++ ) {
        for ( j = 0; j < larger; j++, k++ ) {
          answer[ k ] = largeArr[ j ] * smallArr[ i ];
        } 
      }
    }
  } else {
    larger = One.getSize();  // first poly has more terms
    smaller = Two.getSize(); // second poly has less terms
    double largeArr[ larger ], smallArr[ smaller ];
    for ( int k = 0; k < larger; k++ ) {
      largeArr[ k ] = One.getOneCoeff( k );
    }
    for ( int k = 0; k < smaller; k++ ) {
      smallArr[ k ] = Two.getOneCoeff( k );
    }
    // perform (1 or 0)*(x^n-.. + x + C)
    if ( smaller < 2 ) {
      for ( j = 0; j < larger; j++ ) {
        answer[ j ] = smallArr * largeArr[ j ];
      }
    } else { // otherwise perform multiple term multiplication 
      k = 0; // set outside because it can't be reset inside
      for ( i = 0; i < smaller; i++ ) {
        for ( j = 0; j < larger; j++ ) {
          answer[ k ] = largeArr[ j ] * smallArr[ i ];
        } 
      }
    }
  }

.....

---

I was able to perform the multiplications above without much thought... but for multiple term polynomials I'm at a loss... my best guess is the need for some dynamic allocation of some sort because if you have for example, Poly1 = 4 terms, and Poly2 = 2 terms, well then you have (size1 - 1) * size2 total terms in the end. Obviously this number grows as there are more terms input, so I can't just do a nested structure of for loops up to a finite count(say 2 or up to 5) of terms. Any pointers or suggestions are highly welcomed.

Thank you.

I don't know if you can absolutely say this: (size1 - 1) * size2

Code:

---

(x^2 + x) * (x^3 + x + 1)

x^5 + x^3 + x^2 + x^4 + x^2 + x

x^5 + x^4 + x^3 + 2x^2 + x

---

But you can say the number will not be greater than the (largest exponent of the first + the largest exponent of the second + 1) so you can make an array of that size. (The plus-one to account for the x^0). And then, to simplify things for yourself more you can make a temp array of size (largest exponent of the first * the largest exponent of the second), and multiply out all the coefficients, and store them in the smaller final product array.

Occam's magic shaver at work here...

Code:

---

A = degree a polynomial, B = degree b polynomial
result = array[a + b + 1]

for each x in A
    for each y in B
        result[degree(x) + degree(y)] += coef(x) * coef(y)

---

Quote:

---

Originally Posted by jafet

Occam's magic shaver at work here...

Code:

---

A = degree a polynomial, B = degree b polynomial
result = array[a + b + 1]

for each x in A
    for each y in B
        result[degree(x) + degree(y)] += coef(x) * coef(y)

---

---

Thank you jafet...
However, Im having trouble deciphering your pseudocode... I get most of it, except what you mean by degree - mainly because you point it out in two separate lines. What is meant by degree(x) or degree(y)? Shouldn't that be A(x) + B(y) ? and are you implying I need to make the fuction coef() and pass index advancers?

Degree is the largest exponent in the polynomial - for example, the degree of 5x^7 + 3x^2 + 1 is 7. You can define the degree of the zero polynomial to be 0.

Edit: Sorry, that's wrong, you have to define the degree of the zero polynomial to be minus infinity. That's necessary in order for the degree of the product to be equal to the sum of the degrees.

Edit: http://en.wikipedia.org/wiki/Degree_of_a_polynomial

robatino, thank you - yes, I am aware of what a degree is. My question is how it is applied in the context of jafet's example. It resembles a type on one line, then it looks as if it acts as a function on the next.

Ok, here is what I was able to do based somewhat on Jafet's example and it works for me:

Code:

---

for ( int i = One.getSize() - 1; i >= 0; i-- )
    for ( int j = Two.getSize() - 1; j >= 0; j-- )
      matrixThree[ 0 ][ i + j ] = matrixOne[ 0 ][ i ] * matrixTwo[ 0 ][ j ];

---

Example input for poly One:
2 5 3

Example input for poly Two:
3 2 1 4

Abstractly, think:

Code:

---

6  4  2  8
  15 10  5  20
+      9  6  3  12

---

Which correctly yields:
6 19 21 19 23 12
or
6x^5 + 19x^4 + 21x^3 + 19x^2 + 23x + 12


Not sure if this is of any help to anyone, but I figured I'd post it anyway. Jafet, thank you for your time.