Multiplication of Single Variable Polynomial : Algorithm and Program

Multiplication of single-variable polynomials is a basic but important operation in algebra. To multiply two polynomials, you take each term from the first polynomial and multiply it by every term of the second polynomial. After multiplying, you get several new terms, some of which may have the same power of the variable. The next step is to combine like terms by adding their coefficients to simplify the result.

This method ensures that every possible combination of terms from the two polynomials is accounted for, giving the correct product. In programming, especially in C, this process can be implemented using arrays or structures to store the terms, loops to perform the multiplication, and additional steps to combine like terms. A C program can then take input for the polynomials, perform the multiplication, and display the final simplified result.

Why Multiplication of Single Variable Polynomial is required ?

Multiplication of single-variable polynomials is important because it helps in solving many mathematical and real-world problems. For example:

1. Algebraic calculations: It is used to simplify expressions and solve equations.
2. Engineering and physics: Polynomial multiplication is used in signal processing, control systems, and modeling physical phenomena.
3. Computer algorithms: It is essential in coding problems, computer graphics, and simulations where combining polynomial terms is required.
4. Predicting outcomes: It helps in calculating combined effects when two factors (represented by polynomials) interact.

Algorithm for Polynomial Multiplication

1. Initialize Resultant Polynomial:
   • Start with an array (or another data structure) to store the result. Initialize all elements to zero. The size of this array should be large enough to hold the highest possible degree, which is the sum of the degrees of the two input polynomials.
2. Iterate Through Both Polynomials:
   • Loop through each term of the first polynomial.
   • For each term in the first polynomial, loop through each term of the second polynomial.
3. Multiply and Add Terms:
   • In each iteration of the nested loop, multiply the coefficients of the current terms from both polynomials.
   • Calculate the new degree by adding the exponents of these terms.
   • Add the result to the corresponding position (based on the calculated degree) in the resultant polynomial array.
4. Combine Like Terms:
   • As the multiplication proceeds, some terms might have the same degree. Ensure that these like terms are combined by adding their coefficients.
5. Result:
   • The final array represents the resultant polynomial after multiplication.

Polynomial Multiplication Example:

• P(x)=5x²+3x+7 (Degree 2)
• Q(x)=6x+2 (Degree 1)

Steps for Multiplication:

1. Initialize the Resultant Polynomial:
   • The degree of the resultant polynomial will be the sum of the degrees of P(x) and Q(x), which is 2 + 1 = 3.
   • So, the resultant polynomial R(x) will have a degree of 3 and needs 4 terms (including the constant term).
2. Multiply Each Term of P(x) by Each Term of Q(x):
   • Multiply 5x² (from P(x)) by each term in Q(x): 5x²*6x=30x³ and 5x²*2=10x².
   • Multiply 3x (from P(x)) by each term in Q(x): 3x*6x=18x² and 3x*2=6x.
   • Multiply 7(from P(x)) by each term in Q(x): 7*6x=42x and 7*2=14.
3. Combine Like Terms:
   • Collect terms with the same degree: 30x³ (no other x³ terms), 10x²+18x² (combine x² terms), 6x+42x (combine x terms), and 14 (constant term).
4. Write the Resultant Polynomial:
   • R(x)=30x³+10x²+18x²+6x+42x+14
   • Simplify: R(x)=30x³+28x²+48x+14

Polynomial Multiplication Program

#include <stdio.h>

#define MAX_DEGREE 100  

// Multiply two Polynomials
void polynomialMultiplication(int polynomial1[], int polynomial2[], int degree1, int degree2, int result[]) {
    // Initialize the result array
    for (int i = 0; i <= degree1 + degree2; i++) {
        result[i] = 0;
    }

    // Multiplication of first polynomial with each term of second polynomial
    for (int i = 0; i <= degree1; i++) {
        for (int j = 0; j <= degree2; j++) {
            result[i + j] += polynomial1[i] * polynomial2[j];
        }
    }
}

// Function to print the polynomial
void printPolynomial(int polynomial[], int degree) {
    for (int i = degree; i >= 0; i--) {
        if (polynomial[i] != 0) {
            printf("%dx^%d ", polynomial[i], i);
            if (i != 0) printf("+ ");
        }
    }
    printf("\n");
}

int main() {
    // Polynomial P(x) = 5x^2 + 3x + 7
    int polynomial1[] = {7, 3, 5}; // Degree 2
    int degree1 = 2;

    // Polynomial Q(x) = 6x + 2
    int polynomial2[] = {2, 6}; // Degree 1
    int degree2 = 1;

    int result[MAX_DEGREE];

    polynomialMultiplication(polynomial1, polynomial2, degree1, degree2, result);

    printf("Resultant polynomial after multiplication:\n");
    printPolynomial(result, degree1 + degree2);

    return 0;
}

Output

Resultant polynomial after multiplication:
30x3 + 28x2 + 48x1 + 14x0

Explanation of Polynomial Multiplication Program

This C program is designed to perform the multiplication of two single-variable polynomials and print the resultant polynomial. Let’s go through the program step by step:

Preprocessor Directive and Constants:

#include <stdio.h>
#define MAX_DEGREE 100

The above program includes the standard input-output library stdio.h to use functions like printf and scanf. It also defines a constant MAX_DEGREE to set the maximum degree of the polynomial that the program can handle, ensuring that arrays or data structures used to store the polynomial have a fixed, manageable size.

Multiplication Function:

void polynomialMultiplication(int polynomial1[], int polynomial2[], int degree1, int degree2, int result[]) {
    // Initialize the result array
    for (int i = 0; i <= degree1 + degree2; i++) {
        result[i] = 0;
    }
    // Multiplication of first polynomial with each term of second polynomial
    for (int i = 0; i <= degree1; i++) {
        for (int j = 0; j <= degree2; j++) {
            result[i + j] += polynomial1[i] * polynomial2[j];
        }
    }
}

The above function polynomialMultiplication is used to multiply two polynomials. It first initializes an array result to store the coefficients of the resulting polynomial. Then, it goes through each term of the first polynomial (polynomial1) and multiplies it with every term of the second polynomial (polynomial2), adding the products to the correct positions in the result array. This way, all terms are combined correctly to form the final multiplied polynomial.

Printing Function:

void printPolynomial(int polynomial[], int degree) {
    for (int i = degree; i >= 0; i--) {
        if (polynomial[i] != 0) {
            printf("%dx^%d ", polynomial[i], i);
            if (i != 0) printf("+ ");
        }
    }
    printf("\n");
}

The above function printPolynomial is used to display the polynomial in a readable format. It goes through the array that stores the polynomial’s coefficients and prints each term that has a non-zero coefficient, along with its corresponding degree, so the polynomial can be easily understood.

Main Function:

int main() {
    int polynomial1[] = {7, 3, 5}; // Degree 2
    int polynomial2[] = {2, 6}; // Degree 1
    int result[MAX_DEGREE];
    polynomialMultiplication(polynomial1, polynomial2, degree1, degree2, result);
    printf("Resultant polynomial after multiplication:\n");
    printPolynomial(result, degree1 + degree2);
    return 0;
}

The main function initializes two arrays, polynomial1 and polynomial2, representing the polynomials P(x) = 5x² + 3x + 7 and Q(x) = 6x + 2. It then calls polynomialMultiplication to multiply these two polynomials and stores the result in the result array. Finally, it calls printPolynomial to display the resulting polynomial in a readable format.

Time & Space Complexity

Time Complexity

Space Complexity