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$
12
  • 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, 2013 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, 2013 at 1:52
  • $\begingroup$ Oops, didn't read your last comment. $\endgroup$
    – Pratyush Sarkar
    Aug 17, 2013 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, 2013 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, 2013 at 8:18

3 Answers 3

Reset to default
6
$\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$
5
  • 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, 2015 at 18:16
  • $\begingroup$ @AndréNicolas Thank You for checking my answer. $\endgroup$
    – Arbuja
    Oct 28, 2015 at 20:37
  • $\begingroup$ @ErikVesterlund I found a possible answer. Hopefully, you know of the Taylor series at infinity. $\endgroup$
    – Arbuja
    Oct 29, 2015 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, 2015 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, 2015 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$
1
  • $\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, 2013 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$
4
  • $\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, 2013 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, 2013 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, 2015 at 1:58
  • $\begingroup$ @AnonSubmitter85 I thought convolution was not division in all cases? $\endgroup$
    – Arbuja
    Oct 29, 2015 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .