Polynomial Addition using Arrays

Polynomial  Addition

We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents. 

Each term of a polynomial (like 3x23x^2, 5x15x^1, −7x0-7x^0) can be stored in a structure having two parts:

  • coefficient (like 3, 5, -7)

  • exponent (like 2, 1, 0)

An array of such structures represents the whole polynomial.

Structure Definition (Example in C) 
struct Term {
    int coeff;    // Coefficient of the term
    int expo;     // Exponent of the term
};

And then you can declare:


struct Term poly1[10], poly2[10], polyResult[20];
to represent polynomials.

Algorithm to Add Two Polynomials

Assumption:
Both polynomials are sorted in decreasing order of exponents.

Steps:

  1. Initialize three pointers (indexes):
    i = 0 for first polynomial (poly1),
    j = 0 for second polynomial (poly2),
    k = 0 for result polynomial (polyResult).

  2. Repeat while both i and j are within their respective array sizes:

    • If poly1[i].expo == poly2[j].expo:

      • Add their coefficients.

      • Store the sum and the common exponent in polyResult[k].

      • Increment i, j, and k.

    • Else if poly1[i].expo > poly2[j].expo:

      • Copy poly1[i] to polyResult[k].

      • Increment i and k.

    • Else:

      • Copy poly2[j] to polyResult[k].

      • Increment j and k.

  3. Copy any remaining terms from poly1 (if any) to polyResult.

  4. Copy any remaining terms from poly2 (if any) to polyResult.

  5. Done.

Example

Suppose:

Polynomial 1:

5x3+4x2+2x05x^3 + 4x^2 + 2x^0

Polynomial 2:

5x2+5x1+5x05x^2 + 5x^1 + 5x^0

Represented as Arrays:
poly1    poly2
(5, 3) (5, 2)
(4, 2)    (5, 1)
(2, 0)(5, 0)

Step-by-step Addition:

StepCompareActionResult Term
13 vs 23 > 2 → copy (5,3) from poly1        (5,3)
22 vs 2Equal → add 4+5=9, exponent=2(9,2)
30 vs 10 < 1 → copy (5,1) from poly2(5,1)
40 vs 0Equal → add 2+5=7, exponent=0(7,0)

Final polyResult:

coeff    expo
5    3
9    2
5        1
7    0

Resulting Polynomial:

5x3+9x2+5x1+75x^3 + 9x^2 + 5x^1 + 7


C Program- Polynomial Addition using arrays

#include <stdio.h>

struct Term {
    int coeff;
    int expo;
};

void addPolynomials(struct Term poly1[], int n1, struct Term poly2[], int n2, struct Term polyResult[], int *nResult) {
    int i = 0, j = 0, k = 0;

    while (i < n1 && j < n2) {
        if (poly1[i].expo == poly2[j].expo) {
            polyResult[k].coeff = poly1[i].coeff + poly2[j].coeff;
            polyResult[k].expo = poly1[i].expo;
            i++;
            j++;
            k++;
        }
        else if (poly1[i].expo > poly2[j].expo) {
            polyResult[k] = poly1[i];
            i++;
            k++;
        }
        else {
            polyResult[k] = poly2[j];
            j++;
            k++;
        }
    }

    // Copy remaining terms of poly1
    while (i < n1) {
        polyResult[k] = poly1[i];
        i++;
        k++;
    }

    // Copy remaining terms of poly2
    while (j < n2) {
        polyResult[k] = poly2[j];
        j++;
        k++;
    }

    *nResult = k; // Total number of terms in result
}

void displayPolynomial(struct Term poly[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%dx^%d", poly[i].coeff, poly[i].expo);
        if (i != n - 1) {
            printf(" + ");
        }
    }
    printf("\n");
}

int main() {
    struct Term poly1[] = { {5, 3}, {4, 2}, {2, 0} };
    struct Term poly2[] = { {5, 2}, {5, 1}, {5, 0} };
    struct Term polyResult[20];
    int nResult;

    int n1 = 3; // Number of terms in poly1
    int n2 = 3; // Number of terms in poly2

    printf("First Polynomial: ");
    displayPolynomial(poly1, n1);

    printf("Second Polynomial: ");
    displayPolynomial(poly2, n2);

    addPolynomials(poly1, n1, poly2, n2, polyResult, &nResult);

    printf("Sum of Polynomials: ");
    displayPolynomial(polyResult, nResult);

    return 0;
}

Output
First Polynomial: 5x^3 + 4x^2 + 2x^0
Second Polynomial: 5x^2 + 5x^1 + 5x^0
Sum of Polynomials: 5x^3 + 9x^2 + 5x^1 + 7x^0

Note: Modify the code by adding a new function to  read the polynomial.

Polynomial Addition with modified code - avoiding  the terms with coefficient 0
#include <stdio.h>

struct Term {
    int coeff;
    int expo;
};

void addPolynomials(struct Term poly1[], int n1, struct Term poly2[], int n2, struct Term polyResult[], int *nResult) {
    int i = 0, j = 0, k = 0,ncoeff;

    while (i < n1 && j < n2) {
        if (poly1[i].expo == poly2[j].expo) {
            ncoeff=poly1[i].coeff + poly2[j].coeff;
            if(ncoeff!=0)
            {
            polyResult[k].coeff = ncoeff;
            polyResult[k].expo = poly1[i].expo;
            k++;
            }
            i++;
            j++;
           }
        else if (poly1[i].expo > poly2[j].expo) {
            polyResult[k] = poly1[i];
            i++;
            k++;
        }
        else {
            polyResult[k] = poly2[j];
            j++;
            k++;
        }
    }

    // Copy remaining terms of poly1
    while (i < n1) {
        polyResult[k] = poly1[i];
        i++;
        k++;
    }

    // Copy remaining terms of poly2
    while (j < n2) {
        polyResult[k] = poly2[j];
        j++;
        k++;
    }

    *nResult = k; // Total number of terms in result
}

void displayPolynomial(struct Term poly[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%dx^%d", poly[i].coeff, poly[i].expo);
        if (i != n - 1) {
            printf(" + ");
        }
    }
    printf("\n");
}

int main() {
    struct Term poly1[] = { {5, 3}, {4, 2}, {2, 0} };
    struct Term poly2[] = { {-4, 2}, {5, 1}, {5, 0} };
    struct Term polyResult[20];
    int nResult;

    int n1 = 3; // Number of terms in poly1
    int n2 = 3; // Number of terms in poly2

    printf("First Polynomial: ");
    displayPolynomial(poly1, n1);

    printf("Second Polynomial: ");
    displayPolynomial(poly2, n2);

    addPolynomials(poly1, n1, poly2, n2, polyResult, &nResult);

    printf("Sum of Polynomials: ");
    displayPolynomial(polyResult, nResult);

    return 0;
}
First Polynomial: 5x^3 + 4x^2 + 2x^0
Second Polynomial: -4x^2 + 5x^1 + 5x^0
Sum of Polynomials: 5x^3 + 5x^1 + 7x^0


Polynomial Addition with modified code - reading the polynomials
#include <stdio.h>

struct Term {
    int coeff;
    int expo;
};

void addPolynomials(struct Term poly1[], int n1, struct Term poly2[], int n2, struct Term polyResult[], int *nResult) {
    int i = 0, j = 0, k = 0, ncoeff;

    while (i < n1 && j < n2) {
        if (poly1[i].expo == poly2[j].expo) {
            ncoeff = poly1[i].coeff + poly2[j].coeff;
            if (ncoeff != 0) {
                polyResult[k].coeff = ncoeff;
                polyResult[k].expo = poly1[i].expo;
                k++;
            }
            i++;
            j++;
        } else if (poly1[i].expo > poly2[j].expo) {
            polyResult[k] = poly1[i];
            i++;
            k++;
        } else {
            polyResult[k] = poly2[j];
            j++;
            k++;
        }
    }

    // Copy remaining terms of poly1
    while (i < n1) {
        polyResult[k] = poly1[i];
        i++;
        k++;
    }

    // Copy remaining terms of poly2
    while (j < n2) {
        polyResult[k] = poly2[j];
        j++;
        k++;
    }

    *nResult = k;
}

void displayPolynomial(struct Term poly[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%dx^%d", poly[i].coeff, poly[i].expo);
        if (i != n - 1) {
            printf(" + ");
        }
    }
    printf("\n");
}

int main() {
    struct Term poly1[20], poly2[20], polyResult[40];
    int n1, n2, nResult;

    // Input first polynomial
    printf("Enter the number of terms in the first polynomial: ");
    scanf("%d", &n1);
    printf("Enter the terms in descending order of exponents (coeff exponent):\n");
    for (int i = 0; i < n1; i++) {
        printf("Term %d: ", i + 1);
        scanf("%d%d", &poly1[i].coeff, &poly1[i].expo);
    }

    // Input second polynomial
    printf("Enter the number of terms in the second polynomial: ");
    scanf("%d", &n2);
    printf("Enter the terms in descending order of exponents (coeff exponent):\n");
    for (int i = 0; i < n2; i++) {
        printf("Term %d: ", i + 1);
        scanf("%d%d", &poly2[i].coeff, &poly2[i].expo);
    }

    // Display input polynomials
    printf("\nFirst Polynomial: ");
    displayPolynomial(poly1, n1);
    printf("Second Polynomial: ");
    displayPolynomial(poly2, n2);

    // Add polynomials
    addPolynomials(poly1, n1, poly2, n2, polyResult, &nResult);

    // Display result
    printf("Sum of Polynomials: ");
    displayPolynomial(polyResult, nResult);

    return 0;
}
Enter the number of terms in the first polynomial: 3
Enter the terms in descending order of exponents (coeff exponent):
Term 1: 3 2
Term 2: 2 1
Term 3: 1 0
Enter the number of terms in the second polynomial: 2
Enter the terms in descending order of exponents (coeff exponent):
Term 1: 2 2
Term 2: 2 0

First Polynomial: 3x^2 + 2x^1 + 1x^0
Second Polynomial: 2x^2 + 2x^0
Sum of Polynomials: 5x^2 + 2x^1 + 3x^0

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more