Multiplication of Single Variable Polynomial : Algorithm and Program

Multiplication of single-variable polynomials is a fundamental operation in polynomial algebra. The process involves multiplying each term of one polynomial by each term of the other and then combining like terms. Here’s a detailed explanation of the algorithm followed by a C program to demonstrate it.

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.

Certainly! Let’s go through the steps of multiplying two single-variable polynomials step by step with an example. We’ll use the polynomials P(x)=5x^2+3x+7 and Q(x)=6x+2 for our demonstration.

Polynomial Multiplication Example:

• P(x)=5x^2+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^2 (from P(x)) by each term in Q(x): 5x^2*6x=30x^3 and 5x^2*2=10x^2.
   • Multiply 3x (from P(x)) by each term in Q(x): 3x*6x=18x^2 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^3 (no other x3 terms), 10x^2+18x^2 (combine x2 terms), 6x+42x (combine x terms), and 14 (constant term).
4. Write the Resultant Polynomial:
   • R(x)=30x^3+10x^2+18x^2+6x+42x+14
   • Simplify: R(x)=30x^3+28x^2+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:
30x^3 + 28x^2 + 48x^1 + 14x^0

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

• Includes the standard input-output library for functions like printf.
• Defines a constant MAX_DEGREE to set the maximum degree of the polynomial that the program can handle.

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 function polynomialMultiplication multiplies two polynomials.
• It initializes an array result to store the coefficients of the multiplied polynomial.
• It then iteratively multiplies each term of the first polynomial (polynomial1) with each term of the second polynomial (polynomial2) and accumulates the products in the appropriate position in the result array.

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");
}

• This function printPolynomial prints the polynomial in a readable format.
• It iterates through the array containing the polynomial coefficients, printing each non-zero term along with its degree.

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 polynomial arrays (polynomial1 and polynomial2) representing P(x)=5x2+3x+7 and Q(x)=6x+2, respectively.
• It then calls polynomialMultiplication to multiply these polynomials and stores the result in result.
• Finally, it calls printPolynomial to print the resultant polynomial.

Hope this tutorial helped you to understand the multiplication of two polynomial with the help of algorithm and program.