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\$
  • \$\begingroup\$ related \$\endgroup\$ – RGS Feb 25 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\$ – J42161217 Feb 25 at 10:00
  • 1
    \$\begingroup\$ Note to self: never do test cases by hand and late at night again \$\endgroup\$ – RGS Feb 25 at 10:09
  • \$\begingroup\$ @J42161217 thanks, I had skipped the test case with only x and counted wrong :p fixed! \$\endgroup\$ – RGS Feb 25 at 10:10
  • 1
    \$\begingroup\$ Also in first test case 15/4 = 15/4 not 3 \$\endgroup\$ – J42161217 Feb 25 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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Really short answer! Didn't know of that "deconvolution" operation \$\endgroup\$ – RGS Feb 25 at 12:08
3
\$\begingroup\$

Wolfram Language (Mathematica), 31 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice you managed to reduce the byte count! \$\endgroup\$ – RGS Feb 25 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\$ – Michael Seifert Feb 25 at 21:22
  • \$\begingroup\$ Unfortunately, SeriesCoefficient[#/#2,{x,0,#3}]& is two bytes longer. \$\endgroup\$ – Michael Seifert Feb 25 at 21:28
  • \$\begingroup\$ @MichaelSeifert yes, I tried many things myself but they didn't work for all cases... \$\endgroup\$ – J42161217 Feb 25 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!

| improve this answer | |
\$\endgroup\$
  • \$\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 at 12:08
  • 1
    \$\begingroup\$ @RGS Yes, the last \$q\$ is the answer. \$\endgroup\$ – Arnauld Feb 25 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!

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

Pari/GP, 24 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I see :p really short submission! Good job +1 \$\endgroup\$ – RGS Feb 26 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.