Recursive definition for multiplication of polynomials

Question

I want to find a base and step case for my definition of the multiplication of polynomials that only uses lists.

Whenever I try to make a definition I either use some input (which shouldn't be done) or I access some elements that are not the first element.

To give a clearer image, for example, the polynomial $3x^2 + 9x + 1$ is represented as $[1, 9, 3]$

So at the end, if I used my definition $[1, 9, 3]$ and $[1, 2]$ should give $[1, 11, 21, 6]$ which is equivalent to $6x^3+ 21x^2 + 11x + 1$ and the same for any two lists (polynomials)

---

Polynomials addition example

Base Cases f: $$f([],[]) = []$$ $$f(s:l,[]) = s :f(l,[])$$

$$f([],s:l) = s:f([],l)$$

Step case f:

$$f(s_a:l_a, s_b:l_b) = (s_a+s_b):f(l_a,l_b)$$

$[]$ is the empty list

---

any help is appreciated

Answer 1

Given two lists (coefficient sequencies) $[a_0,...,a_n]$ and $[b_0,...,b_m]$, you are looking for the list $[c_0,...,c_{n+m}]$, which describes the product of the polynomials given by the initial lists. I think what you are looking for can be derived like this:

\begin{align} \left(\sum_{i=0}^n a_nx^n\right)\cdot\left(\sum_{j=0}^m b_nx^n\right) &= \sum_{i=0}^n\sum_{j=0}^n x^{i+j} a_i b_j\\ &= \sum_{k=0}^{n+m}x^k\underbrace{\sum_{i=0}^k a_ib_{k-i}}_{c_k}. \end{align}

So in the end, the list $[c_0,...,c_k]$ is given by

$$c_k=\sum_{i=0}^k a_ib_{k-i}.$$

Answer 2

The basic idea you're missing, I think, is

$$\left( a + x f(x) \right) \cdot g(x) = a \cdot g(x) + x (f(x) \cdot g(x)) $$

Answer 3

The easiest way for me to think about would be something like that:

$$f([],[])=[],$$ \begin{align} f(s:L_1,L_2)&=s\cdot L_2 + (0:f(L_1,L_2)), \\ f(L_1,s:L_2)&=s\cdot L_1 + (0:f(L_1,L_2)). \end{align}

The multiplication and addition are meant componentwise. If you add lists of different length, then make them equally long by appending zeros. I think there is no way without accessing the "inner" list elements

One problem with this list representation of polynomials is the ambiguity of representing the zero polynomial. All of the following lists will represent the same polynomial:

$$[], [0],[0,0],...,[0,...,0],...$$

and the presented rescursive procedure will distingish them: $f(L,[])=0\cdot L$. More general

$$f(L,[\underbrace{0,...,0}_n])=(0\cdot L):[\underbrace{0,...,0}_n]=[\underbrace{0,...,0}_{n+\text{ length of }L}].$$

And you will have this problem in any multiplication:

\begin{align} 1\cdot 1 \overset{\sim}=f([1],[1])&=f(1:[],[1])\\ &=1\cdot[1]+(0:f([],[1]))\\ &=[1]+(0:[0])\\ &=[1]+[0,0] = [1,0]\overset{\sim}=1 \end{align}

So it would be recommended to trim trailing zeros after any calculation. Alternatively, instead of appending zeros to fix unqual length in list addition, at first, try to trim trailing zeros.