Thread: Multiplying Two Polynomials

  1. #1
    Drunken Progammer CaptainMorgan's Avatar
    Join Date
    Feb 2006
    Location
    On The Rocks
    Posts
    45

    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:
    (5)(2x^3 + 4x^2 + 6x + 3)
    produces:
    10x^3 + 20x^2 + 30x + 15
    which is very nnnnice, but this is not enough.



    The problem:
    (2x + 3)(2x^3 + 3x^2 + 4x + 5)
    produces:
    4x^7 + 6x^6 + 8x^5 + 10x^4 + 6x^3 + 9x^2 + 12x + 15
    and of course what I wish is:
    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.

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    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.

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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)
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  4. #4
    Drunken Progammer CaptainMorgan's Avatar
    Join Date
    Feb 2006
    Location
    On The Rocks
    Posts
    45
    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?

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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
    Last edited by robatino; 10-30-2006 at 03:18 AM.

  6. #6
    Drunken Progammer CaptainMorgan's Avatar
    Join Date
    Feb 2006
    Location
    On The Rocks
    Posts
    45
    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.

  7. #7
    Drunken Progammer CaptainMorgan's Avatar
    Join Date
    Feb 2006
    Location
    On The Rocks
    Posts
    45
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  2. polynomials
    By Emeighty in forum C++ Programming
    Replies: 4
    Last Post: 08-18-2008, 08:52 AM
  3. adding two polynomials
    By sahil_m in forum C Programming
    Replies: 3
    Last Post: 11-04-2005, 06:24 AM
  4. Polynomials with linked Lists
    By shaheedpak in forum C++ Programming
    Replies: 0
    Last Post: 09-26-2001, 11:10 AM
  5. Generating Polynomials using Linked Lists
    By shaheedpak in forum C++ Programming
    Replies: 0
    Last Post: 09-25-2001, 01:22 PM