Learn to code the sum of two polynomials

The use of polynomials is fundamental to the field of computer science. There are various ways of dealing with them in programming. We’ll only discuss a couple of them, focusing on the readers with little background knowledge of programming. The scope of this blog is restricted to single-variable polynomials and the addition operation of two such polynomials.

Let’s dive right in!

We’ll cover:

• Introduction
  • Types of polynomials
  • Usage in computer science
• Using a simple array
  • Sum using arrays
  • Optimization for sparse polynomial
• Using parallel arrays
  • Sum using parallel arrays
• Alternative approaches
• Wrapping up and next steps

Introduction#

A polynomial is a mathematical expression consisting of variables, their coefficients, and their exponents combined using arithmetic operations. Polynomials are fundamental in algebra. They are used in various physics, engineering, computer science, and business fields for modeling real-world events.

Here is a sample polynomial: $f(x) = 5x^2+4x+3$

Remember that:

• The absence of an exponent with $x$ means $x^1$.
• The absence of the variable from a term means $x^0$.

We can also write it as $f(x) = 3x^0+4x^1+5x^2$, where $0$, $1$, and $2$ are the exponents of $x$ and $3$, $4$, and $5$ are their coefficients, respectively. The exponent is noted in increasing order in the second option, which seems more convenient when implementing it in programming.

The above sample is called the quadratic polynomial because its degree is two. The degree of a polynomial is determined from the highest exponent of the variable.

Types of polynomials#

The types of polynomials are termed constant, linear, quadratic, or cubic based on whether their degree is zero, one, two, or three, respectively. The polynomials with the degree above three are generally termed higher-degree polynomials. The addition, subtraction, multiplication, and division operations can be performed on two or more polynomials.

Polynomials can involve multiple variables. They are termed univariate, bivariate, or trivariate based on if the number of variables is one, two, or three. The general term multivariate is used for polynomials involving two or more variables.

The focus of this blog is only on storage and addition of univariate polynomials. Of course, the same techniques can be extended to deal with other types and operations.

Usage in computer science#

Polynomials are important in various subjects of computer science. Following are a few examples that highlight their significance:

• Polynomials are used in relation to the time complexity of algorithms in the form of Big O notation. For example, $O(n^2)$ is an upper bound on the time complexity of some sorting algorithms.

• Polynomials are essential in scientific computing. For example, they are used to find the relationship between a goal and the set of points through interpolation.

• Polynomials are also used in error detection and correction codes. For instance, the popular cyclic redundancy check (CRC) uses polynomials to detect errors in data transmission.

• Polynomials are fundamental in computer graphics for designing smooth curves and surfaces.

• Polynomials are used in numerical methods for solving equations, integrating functions, and approximating complex functions.

• Polynomials are also useful in machine learning. They are used to find the relationship between variables through regression.

• Polynomials are used in cryptography, including public keys and digital signatures.

Understanding how to store polynomials and perform operations on them is important for programmers.

Using a simple array#

A univariate polynomial can be stored using a simple array. Considering the array index as the exponent of the variable, the coefficients can be stored as values for the corresponding exponent. The following text and diagram illustrate the polynomial representation in the program output and as an array in the memory.

The following code stores the sample polynomial:

In the above code:

• We declare an array or a list of coefficients. Its size is one more than the degree of the polynomial stored in it. If the degree of the polynomial is two, then the array size is three.
• We use a loop to display each term:
  • First, we write the value of the array element.
  • Then, we write a string “x”.
  • At the end, we write the index.

We had to convert the numeric values to strings for concatenation during the display in Python and Ruby. There are other ways of doing the same task.

Sum using arrays#

Now, we are ready to perform the addition of two polynomials. We achieve this by summing the corresponding elements of two arrays in the following code, taking $f(x)=5+8x+6x^3$ as the first operand and $g(x)=4+x^2$ as the second. The coefficients of $x^2$ and $x^1$ are $0$ in $f(x)$ and $g(x)$, respectively.

In the above code:

• We declare two arrays, f and g, to store two polynomials.
• The size of both arrays is the same, and the missing terms are stored as having a 0 coefficient.
• We display the sum of corresponding elements of both arrays using a loop.

The size of the larger array is also used for the other array.

We can store the sum of the two polynomials in a third variable, as shown in the following code:

In the above code:

• The array h stores the sum of f and g.

  The size of all the arrays equals the highest degree among both polynomials.

• The first loop stores the sum of elements to h.

• The second loop displays the terms of h.

Optimization for sparse polynomial#

A polynomial is sparse if it has very few nonzero coefficients compared to its degree. For example, $3x+x^{10}+5x^{20}$ is a sparse polynomial that can be stored as shown below. The box sizes of nonzero values are only adjusted to fit the term text; they have no special meaning.

The use of a simple array demands a lot of space for zero terms in a sparse polynomial. One efficient yet simple way is to use parallel arrays to store a sparse polynomial, as discussed below.

Using parallel arrays#

One space-efficient way to store a sparse polynomial is to use two parallel arrays. One of them is to store the exponent of a term, and the other one is to store the coefficient of the same term. For example, $3x+x^{10}+5x^{20}$ can be stored like so:

The following code stores the sample sparse polynomial:

In the above code:

• We declare two arrays or lists, fe and fc, to store the exponents and coefficients of $f$. Its size should be equal to the number of nonzero terms in the polynomial to be stored.
• We use a loop to display each term:
  • First, we write the element of the coefficient array.
  • Then, we write a string “x”.
  • At the end, we write the element of the exponent array.

Sum using parallel arrays#

The sum of two sparse polynomials is a bit more challenging:

• The nonzero exponents may differ in two polynomials.
• The number of terms in the resulting sum isn’t clear at the start. However, the sum of the size of both arrays is a safe bet.

Let’s take the sum of two sparse polynomials—$f(x)=3x+x^{10}+5x^{20}$ and $g(x)=2+6x^{10}$— stored as two sets of parallel arrays. The following slides illustrate the steps to compute the sum.

In the following code, we’re not storing the result in a new pair of parallel arrays. We are just displaying the sum. In this case, the number of iterations of the loop is not clear at the start because of the first challenge mentioned above.

In the above code:

• We use fe and fc to store the $f$ polynomial.

• We use ge and gc to store the $g$ polynomial.

• We use three counters:

  • f to track the index of fe (and fc).

  • g to track the index of ge (and gc).

  • i to track the total iterations of the loop. It states the number of terms in the resulting polynomial.

• The loop terminates when both polynomials are finished: the condition f < lenf || g < leng becomes false.

• We display the sum of two coefficients if both exponents are the same: fe[f] == ge[g]. Here, we also pretest that both counters are valid.

• Otherwise, we display the term with a smaller exponent from the current terms in both polynomials.

  • We display the current term in $f$ if its exponent is smaller than the exponent of the current term in $g$. Here, we pretest that $f$ has not finished yet.

  • Otherwise, we display the current term in $g$ because either $f$ has finished already or the exponent of the current term in $g$ is smaller than that in $f$.

• After the loop, we display the total number of iterations, which indicates the number of terms in the resulting polynomial.

We can store the sum of the two sparse polynomials in a third polynomial, as shown in the following code:

In the above code:

• The arrays he and hc are used to store the sum of fc and gc for their corresponding exponents stored in fe and ge.

  The resulting arrays should be large enough to store the terms in the union of exponents of both operands. If both polynomials have no common exponent, the resulting arrays should have a size equal to the sum of the sizes of both operands.

• The first loop stores the sum of elements to h when the exponents of both participating terms are equal.
• The second loop displays the terms of h.

Alternative approaches#

So far, we’ve only used the int type values. However, these codes can be easily converted to handle the float or double type values.

The logic of the code demonstrated above can be coded using other components of programming languages. For example, C++ provides the facility of an efficient implementation called vector. Another alternative for dynamic memory allocation is linked-list.

The two arrays to store the sparse polynomial can be better organized with the use of a struct in C++, as shown below:

struct term {
  int exponent, coefficient;
};

Then, a single term array can work as two parallel int arrays, as illustrated above.

An object-oriented approach can provide the benefits of using class in C++.

Wrapping up and next steps#

Polynomials are one of the most important topics in computer science. The storage and sum of polynomials is an interesting programming exercise. We have seen the implementation of polynomials through arrays/lists in various programming languages.

Happy learning, and keep growing!

To continue learning these concepts and more, check out Educative’s Become a C++ Programmer, Become a Java Developer, and Become a Python Developer paths.

Continue learning to code#

• Learn C++
• Learn C#
• Learn JavaScript
• Learn Ruby