6
$\begingroup$

There's a "formula" for how to multiply polynomials, but is there one for dividing them? There probably is, anyone could deduce one with enough time. Do you know a formula or could provide one? By formula I mean, given $f=\sum^m a_k x^k,g=\sum^n b_k x_k$, a formula for $q,r$ in $f=gq+r$.

(If there's any confusion, no, this is not a question on how to do polynomial division.)

Edit: Since there seems to be so much confusion about what I mean, here's an example: Let $m=4$, $n=2$, $a_m=b_n=1$. Then $f/g=q+r/g$ where

$q=x^2+(a_3-b_1)x+(a_2-b_0-a_3b_1+b_1^2)$

$r=(a_0-a_2b_0+b_0^2+a_3b_0b_1-b_0b_1^2)+(a_1-a_3b_0-a_2b_1+2b_0b_1+a_3b_1^2-b_1^3)x$

This is a general formula: Dividing a general monic quartic by a general monic quadratic will always have this form.

$\endgroup$
  • 3
    $\begingroup$ There's not exactly a formula for it. There's an algorithm you can follow to divide. Its basically just like long division that you do with numbers except this one is with polynomials. Its much easier to give an example than to explain how to do it. I hope someone else will do that in the answer because I'm not exactly sure how I can format that. $\endgroup$ – Pratyush Sarkar Aug 17 '13 at 1:51
  • 1
    $\begingroup$ There are algorithms, but I cannot think of anything one would call a formula, unless you count a recurrence as a formula. $\endgroup$ – André Nicolas Aug 17 '13 at 1:52
  • $\begingroup$ Oops, didn't read your last comment. $\endgroup$ – Pratyush Sarkar Aug 17 '13 at 1:53
  • 1
    $\begingroup$ Seems strange that there shouldn't be a formula. Before I realized how much time it would take I got $f=g(x^{m-n}+(a_{m-1}-b_{n-1})x^{m-n-1}+...)+(\mathrm{remainder})$ with $f,g$ monic. $\endgroup$ – Erik Vesterlund Aug 17 '13 at 6:33
  • $\begingroup$ I don't know if this is what your looking for, but it is a formula. Polynomial division is equivalent to deconvolution. For coefficients in $\mathbb{R}$ or $\mathbb{C}$, as long as $\operatorname{DFT}(\mathbf{b})=\hat{\mathbf{b}}(k)\neq 0$ for all $k$, I think you have $\mathbf{r}=0$ and $\mathbf{q}=\operatorname{DFT}^{-1}\left( { \hat{\mathbf{a}} } \over { \hat{\mathbf{b}} } \right)$. $\endgroup$ – AnonSubmitter85 Aug 17 '13 at 8:18
4
$\begingroup$

This generalization is useless for application but it will lead to a formula for polynomial division. If we have $f/g$ which is $$M(x)=\frac{\sum_{n=0}^{l=m+v}{{a_n}x^{n}}}{\sum_{n=0}^{l=m}{b_n}x^{n}}=\frac{a_0+a_1x+a_2{x^2}...+a_{m+v}{x^{m+v}}}{b_0+b_1x+b_2x^2...+b_mx^m}$$ Just take the taylor series at infinity. Substitute $1/x$ in $x$ then multiply the numerator and denominator by $\frac{1}{x^{m+v}}$ and factor the denominator by $x^v$ to get. $$\left(\frac{1}{x^v}\right)\frac{a_0+a_1x+a_2{x^2}...+a_{m+v}{x^{m+v}}}{b_0+b_1x+b_2x^2...+b_mx^m}=\left(\frac{1}{x^v}\right)L(x)$$

Where $$L(x)=\frac{a_{m+v}+a_{m+v-1}x+a_{m+v-2} {x^2}....+a_{0}{x^{m+v}}}{b_{m}+b_{m-1}x+b_{2}x^2...+b_0x^{m}}$$

Where v is the difference between the highest exponent degrees of a and b.

Then if we take the taylor series of $L(x)$, so the series converges to infinity and substiute $\frac{1}{x}$ for all the $x$'s. $${x^v}\left(L(0)+{1!}L^{1}(0){\frac{1}{x}}+\frac{1}{2!}L^{2}(0){\frac{1}{x^2}}..+\frac{1}{v!}L^{v}(0){\frac{1}{x^v}}\right)$$ $$L(0){x^v}+{1!}L^{1}(0){x^{v-1}}+\frac{1}{2!}L^{2}(0){x^{v-2}}..+\frac{1}{v!}L^{v}(0)$$ So this can be generalized as $$q(x)=\left(\sum_{i={-v}}^{0}\frac{L^{i+v}(0){x^{-i}}}{\left(i+v\right)!}\right)$$

The result this quotoient we can get...

$$\left(\frac{a_{m+v}}{b_m}\right)x^v+\left(\frac{a_{m+v-1}b_{m-1}}{b_m}+\frac{a_{m+v}b_{m-1}}{{b_m}^2}\right)x^{v-1}+\frac{1}{2!}\left(\frac{2{a_{m+v-2}}}{b_m}+\frac{{2}{a_{m+v}}{b_{m-1}}^{2}}{{b_{m}}^{3}}-\frac{{2}{a_{m+v}}{b_{m-2}}}{{b_{m}}^{2}}+\frac{{2}{a_{m+v-1}}{b_{m-1}}}{{b_{m}}^{2}}\right)x^{v-2}+\frac{1}{3!}...$$

Now all you have to do is take the division formula for the remainder $$\frac{a(x)}{b(x)}={q(x)}+\frac{r(x)}{b(x)}$$ $${a(x)}={q(x)}{b(x)}+{r(x)}$$ $${a(x)}-{q(x)}{b(x)}={r(x)}$$ But I can't expand the remainder because too tedious and complicated.

So the complete form is.. $$M(x)=\left(\sum_{i={-v}}^{0}\frac{L^{i+v}(0){x^{-i}}}{\left(i+v\right)!}\right)+\frac{\sum_{n=0}^{l=m+v}{{a_n}x^{n}}-\sum_{i={-v}}^{0}\frac{L^{i+v}(0){x^{-i}}}{\left(i+v\right)!}{\sum_{n=0}^{l=m}{b_n}x^{n}}}{\sum_{n=0}^{l=m}{b_n}x^{n}}$$ It isn't pretty but it is a formula.

$\endgroup$
  • 1
    $\begingroup$ I haven't proofread, but you are right, it is a formula in the sense of the question. $\endgroup$ – André Nicolas Oct 28 '15 at 18:16
  • $\begingroup$ @AndréNicolas Thank You for checking my answer. $\endgroup$ – Arbuja Oct 28 '15 at 20:37
  • $\begingroup$ @ErikVesterlund I found a possible answer. Hopefully, you know of the Taylor series at infinity. $\endgroup$ – Arbuja Oct 29 '15 at 15:42
  • 1
    $\begingroup$ @Arbuja This is nice. I think the only problem could be calculating the derivatives of $L$ at $0$. Although for fixed $\nu$ it can be done by brute force, I think it's too hard to come up with some kind of general formula for any $\nu$. $\endgroup$ – Pratyush Sarkar Oct 29 '15 at 16:05
  • $\begingroup$ Indeed.... I think it would be best to leave the formula in the derivative form; however, computation sites like wolfram alpha can be helpful. Such as typing "the Taylor series of .... at x=infinity". Other than that I just wanted to show a general formula is possible; it is not meant to apply. Thanks for checking! $\endgroup$ – Arbuja Oct 29 '15 at 17:18
2
$\begingroup$

Not sure if this will suffice. I was curious myself to find a formula specifically for the division of $n$th degree polynomials by a linear factor. This is the formula, where $n$ is the degree of $P$. Clearly not to supple a result. $$P(x)/(x+c)=\sum^n_{i=1}(\sum^i_{j=1}(-c)^{i-j} a_{n-j+1}))x^{n-j}+P(-c)/(x+c)$$

each term $a_{n-j+1}$ refers to a coefficient of $P(x)=a_nx^n+a_{n-1}x^{n-1}+. . .+a_1x+a_0$

$\endgroup$
  • $\begingroup$ Thanks for taking the time to actually do the calculations ;) This shows that there is indeed a formula, and not just a recurrence relation, for the result of the division. The inner sum can be renamed into something more succinct, and the calculations repeated the desired number of times. $\endgroup$ – Erik Vesterlund Sep 2 '13 at 10:50
1
$\begingroup$

Polynomial division is equivalent to deconvolution using an IIR filter with an impulse as input, where 'filter' is meant in the signal processing sense and not the set theory sense. (If there is no remainder, then the IIR filter becomes the FIR filter.)

Let $f = a_0 x^{N-1} + a_i x^{N-2} + \cdots a_{N-1}x^0$ and likewise for $g$.For $\mathbf{b}\in \mathbb{R}^M$ and $\mathbf{a} \in \mathbb{R}^N$ such that $a_0=1$, the polynomial division is given by

$$ y_n = \sum_{k=0}^{M-1}{ \delta_{n-k} b_k } - \sum_{i=1}^{\min(n,N-1)} y_{n-i} a_i $$

where

$$ \delta_k = \begin{cases} 1, & k = 0 \\ 0, & k \neq 0 \end{cases} $$

The first $M-N+1$ terms of ${y_n}$ will be the coefficients of the quotient and the remaining non-zero terms will be the coefficients of the remainder.

$\endgroup$
  • $\begingroup$ Like I said in the comments this is beyond my knowledge but hopefully it's helpful to those who understand it. $\endgroup$ – Erik Vesterlund Aug 19 '13 at 2:15
  • 1
    $\begingroup$ @ErikVesterlund Ignore the talk of filters; it just hints how the equation is derived. To use it, though, only requires simple addition and multiplication. $\endgroup$ – AnonSubmitter85 Aug 19 '13 at 2:18
  • $\begingroup$ @AnonSubmitter85 Does convolution have anything to do with the taylor series at infinity? I posted my answer. $\endgroup$ – Arbuja Oct 28 '15 at 1:58
  • $\begingroup$ @AnonSubmitter85 I thought convolution was not division in all cases? $\endgroup$ – Arbuja Oct 29 '15 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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