Saturday, February 6, 2016

Polynomial processing in Python

These days I have been working on learning Python. I heard again and again that Python is easy to code and one can write something very quickly, so I would like to spend some time on it to get proficient on it. At the same time, I ran into a small problem that I need to solve with my studies in Algebraic Geometry, so I decided to force myself to write this piece of code in Python.

The full source code to the whole program is here on GitHub.

https://github.com/cshung/MiscLab/tree/master/GreatestCommonDivisor

The program has a very simple main driver. It simply compute the GCD of a few polynomials.

from polynomial_module import *

# Problem 8a
print polynomial.polynomial_gcd(
    polynomial.polynomial_gcd(
        polynomial.from_string("x^4 + x^2 + 1"),
        polynomial.from_string("x^4 - x^2 - 2x - 1")),
    polynomial.from_string("x^3 - 1"))

# Problem 8b
print polynomial.polynomial_gcd(
    polynomial.polynomial_gcd(
        polynomial.from_string("x^3 + 2x^2 - x - 2"),
        polynomial.from_string("x^3 - 2x^2 - x + 2")),
    polynomial.from_string("x^3 - x^2 - 4x + 4"))

Needless to say, these are the problems I wanted to solve.

The from_string method implies I wrote a parser for the strings. For the purpose of parsing these strings, I defined a small grammar for these strings and wrote a top-down recursive parser for it.

The GCD method is a simple Euclidean algorithm for computing GCD. In order to manipulate the polynomials in the algorithm, I wrote all four arithmetic operations in polynomial.

In order to make sure we have the precision we wanted, I used rational arithmetic. In Python, all numbers are big integer by default, so if the input has finite precision, the output will have finite precision, and we can always represent it as a fraction, that's why I introduced the rational class for that purpose.

No comments :

Post a Comment