9
\$\begingroup\$

Context

After "Computing a specific coefficient in a product of polynomials", asking you to compute a specific coefficient of polynomial multiplication, I wish to create a "mirror" challenge, asking you to compute a specific coefficient from polynomial division.

Polynomial division

Let us establish an analogy with integer division. If you have two integers a and b, then there is a unique way of writing a = qb + r, with q, r integers and 0 <= r < b.

Let p(x), a(x) be two polynomials. Then there is a unique way of writing a(x) = q(x)p(x) + r(x), where q(x), r(x) are two polynomials and the degree of r(x) is strictly less than the degree of p(x).

Algorithm

Polynomial division can be performed through an iterative algorithm:

  1. Initialize the quotient at q(x) = 0
  2. While the degree of a(x) is at least as big as the degree of p(x):
    • let n = degree(a) - degree(p), let A be the coefficient of the term of highest degree in a(x) and P be the coefficient of highest degree in p(x).
    • do q(x) = q(x) + (A/P)x^n
    • update a(x) = a(x) - p(x)(A/P)x^n
  3. q(x) is the quotient and what is left at a(x) is the remainder, which for our case will always be 0.

Task

Given two polynomials a(x), p(x) such that there exists q(x) satisfying a(x) = p(x)q(x) (with all three polynomials having integer coefficients), find the coefficient of q(x) of degree k.

(Yes, we are assuming the remainder is 0)

Input

Two polynomials (with integer coefficients) and an integer.

Each input polynomial can be in any sensible format. A few suggestions come to mind:

  • A string, like "1 + 3x + 5x^2"
  • A list of coefficients where index encodes exponent, like [1, 3, 5]
  • A list of (coefficient, exponent) pairs, like [(1, 0), (3, 1), (5, 2)]

An input format must be sensible AND completely unambiguous over the input space.

The integer k is a non-negative integer. You may take it in any of the usual ways. You can assume k is less than or equal to the differences of the degrees of a(x) and p(x), i.e. k <= deg(a) - deg(p) and you can assume deg(a) >= deg(p).

Output

The integer corresponding to the coefficient of x^k in the polynomial q(x) that satisfies the equality a(x) = q(x)p(x).

Test cases

The input order for the test cases is a(x), p(x), integer k.

[12], [4], 0 -> 3
[0, 0, 6], [0, 3], 0 -> 0
[0, 0, 6], [0, 3], 1 -> 2
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 0 -> 7
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 1 -> 0
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 2 -> 1
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 3 -> 6
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 0 -> -5
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 1 -> 7
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 2 -> -10
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 3 -> -8
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 4 -> 1
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 5 -> 0
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 6 -> -1

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

(This is not part of the RGS Golfing Showdown)

\$\endgroup\$
7
  • \$\begingroup\$ related \$\endgroup\$
    – RGS
    Feb 25 '20 at 7:28
  • 1
    \$\begingroup\$ The 4,5,6 examples are wrong: q(x)=7 + x^2 + 6 x^3 so coefficients {0,1,2,3} = {7,0,1,6} \$\endgroup\$
    – ZaMoC
    Feb 25 '20 at 10:00
  • 1
    \$\begingroup\$ Note to self: never do test cases by hand and late at night again \$\endgroup\$
    – RGS
    Feb 25 '20 at 10:09
  • \$\begingroup\$ @J42161217 thanks, I had skipped the test case with only x and counted wrong :p fixed! \$\endgroup\$
    – RGS
    Feb 25 '20 at 10:10
  • 1
    \$\begingroup\$ Also in first test case 15/4 = 15/4 not 3 \$\endgroup\$
    – ZaMoC
    Feb 25 '20 at 10:23
6
\$\begingroup\$

MATL, 6 bytes

Y-PiQ)

The inputs contain the coefficients in order of decreasing powers.

Try it online! Or verify all test cases

Explanation

(De)convolution is the key to success

     % Implicit inputs: two numerical vectors
Y-   % Deconvolution 
P    % Flip
i    % Input: integer
Q    % Add 1
)    % Get the entry at that position
     % Implicit display
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Really short answer! Didn't know of that "deconvolution" operation \$\endgroup\$
    – RGS
    Feb 25 '20 at 12:08
3
\$\begingroup\$

Wolfram Language (Mathematica), 31 bytes

Coefficient[Factor[#/#2],x,#3]&

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Nice you managed to reduce the byte count! \$\endgroup\$
    – RGS
    Feb 25 '20 at 12:06
  • \$\begingroup\$ A different approach with the same byte count: Limit[D[#/#2,{x,#3}]/#3!,x->0]& (It calculates the kth-order coefficient in the Taylor series of the quotient, which will just be the polynomial coefficient. Note that setting x to 0 via ... /.x->0 doesn't work for all polynomials.) \$\endgroup\$ Feb 25 '20 at 21:22
  • \$\begingroup\$ Unfortunately, SeriesCoefficient[#/#2,{x,0,#3}]& is two bytes longer. \$\endgroup\$ Feb 25 '20 at 21:28
  • \$\begingroup\$ @MichaelSeifert yes, I tried many things myself but they didn't work for all cases... \$\endgroup\$
    – ZaMoC
    Feb 25 '20 at 22:28
2
\$\begingroup\$

JavaScript (ES6), 81 bytes

Takes input as (a,p,k). The polynomial coefficients are expected from highest to lowest.

(a,[c,...p],k)=>a.slice(p.length+k).map((_,n)=>p.map(v=>a[++n]-=v*q,q=a[n]/c))&&q

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ What is going on with the &&q at the end? Is it just to return the coefficient you want? q stores the intermediate coefficients of the quotient, right? \$\endgroup\$
    – RGS
    Feb 25 '20 at 12:08
  • 1
    \$\begingroup\$ @RGS Yes, the last \$q\$ is the answer. \$\endgroup\$
    – Arnauld
    Feb 25 '20 at 18:45
1
\$\begingroup\$

Python 3, 51 49 48 bytes

Input: a, p, k. The format for the polynomials a and p is a list of coefficients, in order of highest to lowest degree.

lambda*p,k:numpy.polydiv(*p)[0][~k]
import numpy

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Turns out importing numpy gives a really short answer! +1 well played \$\endgroup\$
    – RGS
    Feb 25 '20 at 23:39
1
\$\begingroup\$

Pari/GP, 24 bytes

f(a,p,k)=polcoeff(a/p,k)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ I see :p really short submission! Good job +1 \$\endgroup\$
    – RGS
    Feb 26 '20 at 7:55

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.