Tag Archives: multiply

Polynomial Arithmetic

Polynomial Arithmetic Image

With students beginning to attend classes across the nation, I wanted to focus the site towards some of the things they’re going to be addressing. This latest page publicize some scripts that I wrote to help with polynomial arithmetic. Originally I wrote these as homework exercises for a class in programming, but I have found them useful ever since – both in teaching mathematics classes like college algebra, which spends a lot of attention on polynomials, and in my research life. Its funny (and sad) the number of simple errors that a person (mathematician or not) can make when performing simple arithmetic, so I found it very useful to have a calculator more advanced than the simple scientific calculators that are so easily available.

I’m not going to spend a lot of time discussing the importance of polynomials, or trying to justify their need. I will bring up some problems that I’d like to address in the future, that deal with polynomials. The first is finding the roots of the characteristic polynomial of a matrix. This is useful in research because these roots are the eigenvalues of the matrix and can give many properties of the matrix. There are also some data analysis tools like Singular Value Decomposition and Principal Component Analysis where I will probably build out from this initial set of instances.

The user interface for the scripts I’ve written generate two polynomials and ask the user what is to be done with those polynomials. The options are to add the two, subtract polynomial 2 from polynomial 1, multiply the two, divide polynomial 1 by polynomial 2, and divide polynomial 2 by polynomial 1. There is also the option to make the calculations more of a tutorial by showing the steps along the way. Users who want new problems can generate a new first or second polynomial and clear work.

For addition and subtraction, the program works by first ensuring that both polynomials have the same degree. This can be achieved by adding terms with zero coefficient to the lower degree polynomial. Once this has been accomplished, we simply add the terms that have the same exponent.

For multiplication, the program first builds a matrix A, where the element ai, i+j on row i and column i+j of the matrix A is achieved by multiplying the ith term of the first polynomial by the jth term of the second polynomial. If an was not given a value in the matrix, then we put a value of zero in that cell. Once this matrix is formed, we can sum the columns of the matrix to arrive at the final answer.

The division of two polynomials works first by dividing the first term of the numerator by the first term of the denominator. This answer is then multiplied by the denominator and subtracted from the numerator. Now, the first term in the numerator should cancel and we use the result as the numerator going froward. This process is repeated as long as the numerator’s degree is still equal to or greater than the denominator’s degree.

Check out the latest page on polynomial arithmetic and let me know what you think.

The Euclidean Algorithm

I remember being in school and learning about fractions. In particular, I remember the problems we had when trying to add and subtract fractions. This problem also presented itself when we tried to multiply fractions, although we still received partial credit if we couldn’t reduce fractions to their lowest terms.

What I’m referring to is the problem of finding the Greatest Common Divisor (GCD) of two numbers. The GCD of two numbers is the largest number that divides into both numbers with a remainder of zero each time. This problem has many applications, but for most of us we can relate to it because of our frustrations with fractions.

The algorithm that I’m writing about and have written a script for is called the Euclidean Algorithm, which solves precisely this problem. To be more precise, the Euclidean Algorithm finds the greatest common divisor between two integer numbers.

There are different versions of the algorithm, but the one I have implemented finds the GCD by subtracting the smaller number from the larger number, and if the result is greater than 0, the procedure repeats itself with the two lower numbers. Otherwise, the result (the GCD) is the final number that was greater than 0.

Lets see an example:
Consider the number 9 and 21.
21 – 9 = 12. 12 is greater than 0, so we repeat the procedure with 9 and 12.
12 – 9 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 9.
9 – 3 = 6. 6 is greater than 0, so we repeat the procedure with 3 and 6.
6 – 3 = 3. 3 is greater than 0, so we repeat the procedure with 3 and 3.
3 – 3 = 0. 0 is not greater than 0, so can exit the loop portion of the algorithm.
Since 3 was the last positive number that we arrived at in this procedure, we see that the GCD of 9 and 12 is 3.

To learn more and see more examples, check out My Script on The Euclidean Algorithm.