2
$\begingroup$

Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are

$$x^2-2x+3, \text{and } x-5$$

then the result of multiplication will be

$$x^3-7x^2+13x-15.$$

My question is that how to read the two algebraic quantities, find out the result of multiplication and print the result in c++. I need hints and is there something to learn to multiply the two or more algebraic quantities by programming. If so,what is that?

$\endgroup$
4
$\begingroup$

Your algebraic quantities are polynomials in one variable. Multiplying two polynomials is an important computational problem with many applications. You can store a polynomial in two ways:

  • store the coefficients, that is for $p(x)=3x^2-x+3$ you store $(3,-1,3)$
  • store enough samples, that is for $p(x)=3x^2-x+3$ you might store three values like $p(0)=3,p(1)=5,p(-1)=7$ (if your highest exponent is $k$ you need $k+1$ samples)

To multiply two polynomials you can do the following. Assume the coefficients of the first polynomial $A(x)$ are named $a_i$ and of the second $B(x)$ they are named $b_i$, then the coefficients for $A(x)B(x)$ are the coefficients $c_i$ with $$c_k= \sum_{(i,j)\colon i+j=k} a_ib_j$$

Without tricks this takes $O(n^2)$ time.

Another possibility is to multiply the samples (if they are taken at the same positions). The problem here is, that the product has a higher degree. That means that you need more samples than you needed for the original polynomials. So you had to record more samples in the beginning. What is even more severe is that it is not easy to evaluate the polynomials on arbitrary positions if you only have the samples. So the multiplacation goes fast in $O(n)$ time if you have enough samples, but the evaluation might need $O(n^2)$ time per se.

But here is the thing. You can change from one representation to the other in only $O(n \log n)$ by a famous algorithm called fast Fourier transform (FFT). In a nutshell you pick you sample points very clever and then you divide and conquer. Using FFT you can multiply and evaluate polynomials in time $O(n\log n)$. If you dont care so much about speed, just use the coefficient representation and the formula above.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.