Algorithm C++ programming Coding Mathematical Algorithms

C++ Programming – Program to add two polynomials

C++ Programming - Program to add two polynomials - Mathematical Algorithms - Addition is simpler than multiplication of polynomials. We initialize result

Given two polynomials represented by two arrays, write a function that adds given two polynomials.

Example:

Input:  A[] = {5, 0, 10, 6} 
        B[] = {1, 2, 4} 
Output: sum[] = {5, 10, 30, 26, 52, 24}

The first input array represents "5 + 0x^1 + 10x^2 + 6x^3"
The second array represents "1 + 2x^1 + 4x^2" 
And Output is "6 + 2x^1 + 14x^2 + 6x^3"

Addition is simpler than multiplication of polynomials. We initialize result as one of the two polynomials, then we traverse the other polynomial and add all terms to the result.

add(A[0..m-1], B[0..n01])
1) Create a sum array sum[] of size equal to maximum of 'm' and 'n'
2) Copy A[] to sum[].
3) Travers array B[] and do following for every element B[i]
          sum[i] = sum[i] + B[i]
4) Return sum[].

The following is C++ implementation of above algorithm.

C++ Program
// Simple C++ program to add two polynomials
#include <iostream>
using namespace std;
 
// A utility function to return maximum of two integers
int max(int m, int n) {  return (m > n)? m: n; }
 
// A[] represents coefficients of first polynomial
// B[] represents coefficients of second polynomial
// m and n are sizes of A[] and B[] respectively
int *add(int A[], int B[], int m, int n)
{
   int size = max(m, n);
   int *sum = new int[size];
 
   // Initialize the porduct polynomial
   for (int i = 0; i<m; i++)
     sum[i] = A[i];
 
   // Take ever term of first polynomial
   for (int i=0; i<n; i++)
       sum[i] += B[i];
 
   return sum;
}
 
// A utility function to print a polynomial
void printPoly(int poly[], int n)
{
    for (int i=0; i<n; i++)
    {
       cout << poly[i];
       if (i != 0)
        cout << "x^" << i ;
       if (i != n-1)
       cout << " + ";
    }
}
 
// Driver program to test above functions
int main()
{
    // The following array represents polynomial 5 + 10x^2 + 6x^3
    int A[] = {5, 0, 10, 6};
 
    // The following array represents polynomial 1 + 2x + 4x^2
    int B[] = {1, 2, 4};
    int m = sizeof(A)/sizeof(A[0]);
    int n = sizeof(B)/sizeof(B[0]);
 
    cout << "First polynomial is \n";
    printPoly(A, m);
    cout << "\nSecond polynomial is \n";
    printPoly(B, n);
 
    int *sum = add(A, B, m, n);
    int size = max(m, n);
 
    cout << "\nsumuct polynomial is \n";
    printPoly(sum, size);
 
    return 0;
}

Output:

First polynomial is
5 + 0x^1 + 10x^2 + 6x^3
Second polynomial is
1 + 2x^1 + 4x^2
Sum polynomial is
6 + 2x^1 + 14x^2 + 6x^3

Time complexity of the above algorithm and program is O(m+n) where m and n are orders of two given polynomials.

READ  C - Programming Tree Traversals (Inorder, Preorder and Postorder)

About the author

Wikitechy Editor

Wikitechy Editor

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

X