Mixing
Multiply numerical polynomials
Clash Royale CLAN TAG#URR8PPP
up vote
7
down vote
favorite
A numerical polynomial is a polynomial p in one variable with rational coefficients such that for every integer i, p(i) is also an integer. The numerical polynomials have a basis given by the binomial coefficients:
For instance:
The product of any two numerical polynomials is a numerical polynomial, so there are formulas expressing p_m * p_n as a linear combination of p_0, p_1, ..., p_m+n.
Your job is to produce these formulas.
Goal:
Input: A pair of positive integers m and n
Output: The list of integers [a_1,...,a_m+n] of length m+n such that
$p_mtimes p_n = sum_i=1^m+n a_ip_i$
This is code golf, so shortest code wins.
Examples:
Test Cases:
(1,1) ==> [1,2]
(1,2) ==> [0,2,3]
(1,3) ==> [0, 0, 3, 4]
(1,4) ==> [0, 0, 0, 4, 5]
(2,2) ==> [0, 1, 6, 6]
(2,3) ==> [0, 0, 3, 12, 10]
(2,4) ==> [0, 0, 0, 6, 20, 15]
(3,4) ==> [0, 0, 0, 4, 30, 60, 35]
(4,4) ==> [0, 0, 0, 1, 20, 90, 140, 70]
code-golf math polynomials
edited 1 hour ago
alephalpha
20.5k32886
asked 20 hours ago
Hood
3868
add a comment |Â
up vote
7
down vote
favorite
A numerical polynomial is a polynomial p in one variable with rational coefficients such that for every integer i, p(i) is also an integer. The numerical polynomials have a basis given by the binomial coefficients:
For instance:
The product of any two numerical polynomials is a numerical polynomial, so there are formulas expressing p_m * p_n as a linear combination of p_0, p_1, ..., p_m+n.
Your job is to produce these formulas.
Goal:
Input: A pair of positive integers m and n
Output: The list of integers [a_1,...,a_m+n] of length m+n such that
$p_mtimes p_n = sum_i=1^m+n a_ip_i$
This is code golf, so shortest code wins.
Examples:
Test Cases:
(1,1) ==> [1,2]
(1,2) ==> [0,2,3]
(1,3) ==> [0, 0, 3, 4]
(1,4) ==> [0, 0, 0, 4, 5]
(2,2) ==> [0, 1, 6, 6]
(2,3) ==> [0, 0, 3, 12, 10]
(2,4) ==> [0, 0, 0, 6, 20, 15]
(3,4) ==> [0, 0, 0, 4, 30, 60, 35]
(4,4) ==> [0, 0, 0, 1, 20, 90, 140, 70]
code-golf math polynomials
edited 1 hour ago
alephalpha
20.5k32886
asked 20 hours ago
Hood
3868
4
Just an FYI we have MathJax now so you can use$to write in-line equations like $ p_m $ instead of using images.
– FryAmTheEggman
20 hours ago
Looks like every test is missing the $a_0=0$ entry; so are the inputs actually going to be strictly positive integers or should(0,0)yield an empty list?
– Jonathan Allan
20 hours ago
@JonathanAllan Strictly positive -- none of the polynomials have a constant coefficient so it would be kind of boring.
– Hood
19 hours ago
@FryAmTheEggman That's good to know because making the images is quite annoying.
– Hood
19 hours ago
@JonathanAllan I guess I shouldn't have given p_0 as an example of a basis element...
– Hood
19 hours ago
add a comment |Â
up vote
7
down vote
favorite
up vote
7
down vote
favorite
A numerical polynomial is a polynomial p in one variable with rational coefficients such that for every integer i, p(i) is also an integer. The numerical polynomials have a basis given by the binomial coefficients:
For instance:
The product of any two numerical polynomials is a numerical polynomial, so there are formulas expressing p_m * p_n as a linear combination of p_0, p_1, ..., p_m+n.
Your job is to produce these formulas.
Goal:
Input: A pair of positive integers m and n
Output: The list of integers [a_1,...,a_m+n] of length m+n such that
$p_mtimes p_n = sum_i=1^m+n a_ip_i$
This is code golf, so shortest code wins.
Examples:
Test Cases:
(1,1) ==> [1,2]
(1,2) ==> [0,2,3]
(1,3) ==> [0, 0, 3, 4]
(1,4) ==> [0, 0, 0, 4, 5]
(2,2) ==> [0, 1, 6, 6]
(2,3) ==> [0, 0, 3, 12, 10]
(2,4) ==> [0, 0, 0, 6, 20, 15]
(3,4) ==> [0, 0, 0, 4, 30, 60, 35]
(4,4) ==> [0, 0, 0, 1, 20, 90, 140, 70]
code-golf math polynomials
edited 1 hour ago
alephalpha
20.5k32886
asked 20 hours ago
Hood
3868
A numerical polynomial is a polynomial p in one variable with rational coefficients such that for every integer i, p(i) is also an integer. The numerical polynomials have a basis given by the binomial coefficients:
For instance:
The product of any two numerical polynomials is a numerical polynomial, so there are formulas expressing p_m * p_n as a linear combination of p_0, p_1, ..., p_m+n.
Your job is to produce these formulas.
Goal:
Input: A pair of positive integers m and n
Output: The list of integers [a_1,...,a_m+n] of length m+n such that
$p_mtimes p_n = sum_i=1^m+n a_ip_i$
This is code golf, so shortest code wins.
Examples:
Test Cases:
(1,1) ==> [1,2]
(1,2) ==> [0,2,3]
(1,3) ==> [0, 0, 3, 4]
(1,4) ==> [0, 0, 0, 4, 5]
(2,2) ==> [0, 1, 6, 6]
(2,3) ==> [0, 0, 3, 12, 10]
(2,4) ==> [0, 0, 0, 6, 20, 15]
(3,4) ==> [0, 0, 0, 4, 30, 60, 35]
(4,4) ==> [0, 0, 0, 1, 20, 90, 140, 70]
code-golf math polynomials
code-golf math polynomials
edited 1 hour ago
alephalpha
20.5k32886
asked 20 hours ago
Hood
3868
edited 1 hour ago
alephalpha
20.5k32886
asked 20 hours ago
Hood
3868
edited 1 hour ago
alephalpha
20.5k32886
edited 1 hour ago
alephalpha
20.5k32886
edited 1 hour ago
alephalpha
20.5k32886
20.5k32886
asked 20 hours ago
Hood
3868
asked 20 hours ago
Hood
3868
asked 20 hours ago
Hood
3868
3868
4
Just an FYI we have MathJax now so you can use$to write in-line equations like $ p_m $ instead of using images.
– FryAmTheEggman
20 hours ago
Looks like every test is missing the $a_0=0$ entry; so are the inputs actually going to be strictly positive integers or should(0,0)yield an empty list?
– Jonathan Allan
20 hours ago
@JonathanAllan Strictly positive -- none of the polynomials have a constant coefficient so it would be kind of boring.
– Hood
19 hours ago
@FryAmTheEggman That's good to know because making the images is quite annoying.
– Hood
19 hours ago
@JonathanAllan I guess I shouldn't have given p_0 as an example of a basis element...
– Hood
19 hours ago
add a comment |Â
4
Just an FYI we have MathJax now so you can use$to write in-line equations like $ p_m $ instead of using images.
– FryAmTheEggman
20 hours ago
Looks like every test is missing the $a_0=0$ entry; so are the inputs actually going to be strictly positive integers or should(0,0)yield an empty list?
– Jonathan Allan
20 hours ago
@JonathanAllan Strictly positive -- none of the polynomials have a constant coefficient so it would be kind of boring.
– Hood
19 hours ago
@FryAmTheEggman That's good to know because making the images is quite annoying.
– Hood
19 hours ago
@JonathanAllan I guess I shouldn't have given p_0 as an example of a basis element...
– Hood
19 hours ago
4
4
Just an FYI we have MathJax now so you can use
$ to write in-line equations like $ p_m $ instead of using images.– FryAmTheEggman
20 hours ago
Just an FYI we have MathJax now so you can use
$ to write in-line equations like $ p_m $ instead of using images.– FryAmTheEggman
20 hours ago
Looks like every test is missing the $a_0=0$ entry; so are the inputs actually going to be strictly positive integers or should
(0,0) yield an empty list?– Jonathan Allan
20 hours ago
Looks like every test is missing the $a_0=0$ entry; so are the inputs actually going to be strictly positive integers or should
(0,0) yield an empty list?– Jonathan Allan
20 hours ago
@JonathanAllan Strictly positive -- none of the polynomials have a constant coefficient so it would be kind of boring.
– Hood
19 hours ago
@JonathanAllan Strictly positive -- none of the polynomials have a constant coefficient so it would be kind of boring.
– Hood
19 hours ago
@FryAmTheEggman That's good to know because making the images is quite annoying.
– Hood
19 hours ago
@FryAmTheEggman That's good to know because making the images is quite annoying.
– Hood
19 hours ago
@JonathanAllan I guess I shouldn't have given p_0 as an example of a basis element...
– Hood
19 hours ago
@JonathanAllan I guess I shouldn't have given p_0 as an example of a basis element...
– Hood
19 hours ago
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
4
down vote
Haskell, 84 bytes
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
Explanation
Given a polynomial $q$, the following algorithm (see here) computes the unique coefficients $a_0,a_1,ldots$ such that $q=a_0p_0+a_1p_1+ldots$.
Let
$$
Delta^(0)q(x)=q(x)\
Delta^(i+1)q(x)=Delta^(i)q(x+1)-Delta^(i)q(x).
$$
Then $a_i=Delta^(i)q(0)$.
Moreover, it can be easily proved that
$$
Delta^(i)q(0)=sum_k=0^i(-1)^i-kichoose kq(k).
$$
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
The function # computes the answer to the challenge. It simply uses the observation above to compute
$$
a_i=sum_k=0^i(-1)^i-kichoose kkchoose nkchoose m.
$$
The foldr1(-) is the only thing that needs explaining. When applied to a list $[b_0,b_1,ldots,b_l]$, foldr1(-) returns
$$
b_0-(b_1-(ldots-(b_l-1-b_l)ldots)=sum_j=0^l(-1)^jb_j
$$
Haskell, 108 100 bytes
I'm also keeping this one. It is, in my opinion, more elegant, albeit much more verbose.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
The function # computes the answer to the challenge. Let $q=p_ncdot p_m$.
[x!n*x!m|x<-[0..]]is the infinite list
$$
left[0choose n0choose m,1choose n1choose m,2choose n2choose m,ldotsright]
$$
i.e.
$$
[q(0),q(1),q(2),ldots].
$$- Given a list $[b_0,b_1,b_2,ldots]$, the function
zipWith(-)=<<tailreturns $[b_1-b_0,b_2-b_1,ldots]$. Thus the codehead<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]returns the infinite list
$$
[Delta^(0)q(0),Delta^(1)q(0),Delta^(2)q(0),ldots]=[a_0,a_1,a_2,ldots].
$$ - Finally with
take(n+m).tailwe drop $a_0$ and we take the first $n+m$ coefficients, thereby solving the challenge.
answered 19 hours ago
Delfad0r
963213
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
add a comment |Â
up vote
3
down vote
Haskell, 74 bytes
a%b|let a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a=map(a?)[1..a+b]
Try it online!
Uses a recursive formulation I found. Let $g_b(a,i)$ be the coefficient of $p_i$ in $p_a p_b$, which is implemented in the code by a?i (with b fixed). We can express $g_b$ recursively as
$$g_b(a,i)=fracicdot g_b(a-1,i-1)-(a-1-i)cdot g_b(a-1,i-1)a$$
with base case
$$g_b(0,i)=
begincases
1,text if b=i\
0,text otherwise\
endcases
$$
The base case corresponds to the expansion for $p_b$, which has a single nonzero coefficient of $p_i$ at $i=b$. The code implements this indicator function as 0^(i-b)^2.
The code has guards belonging to the definition of ? in the let binding. It's perhaps easier to read as the following (non-working) code where the definition of a?i expects b as a global variable. Perhaps confusingly, the a in the definition of ? is not always the same as the input to %, since it recurses down.
a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a
a%b=map(a?)[1..a+b]
The main function % lists the coefficients for each i from 1 to a+b. It's possible to code the recursion in % directly by zipping shifted lists, but I did not find a short way to do it especially with the dependence on the position i.
answered 2 hours ago
xnor
87.7k17182433
add a comment |Â
up vote
2
down vote
Pari/GP, 66 bytes
(m,n)->b=matpascal(m+n);([b[i,m+1]*b[i,n+1]|i<-[1..#b]]/b~)[2..#b]
Try it online!
answered 42 mins ago
alephalpha
20.5k32886
Nice answer. As a completely minor golf, curryinng gives -1 bytes (m->n->).
– Mr. Xcoder
21 mins ago
add a comment |Â
up vote
1
down vote
JavaScript (ES6), 109 bytes
This is really just a port of Delfad0r's great answer, implemented as nested recursive functions.
Takes input as (n)(m).
n=>m=>(g=i=>i?[...g(i-1),(h=k=>k&&h(k-1)-(b=(y,x=k)=>y?x*b(y-1,x-1)/y:i-k&1||-1)(k,i)*b(n)*b(m))(i)]:)(n+m)
Try it online!
How?
The function $b(y,x)$ computes:
$$-(-1)^i-kxchoose y$$
It's slightly shorter to return $-(-1)^i-k$ as the last iteration of this function than processing it separately. Because we compute the product of three binomial coefficients, the signs of the first two of them are simply cancelling each other out.
The function $h()$ is used to compute:
$$sum_k=1^i-b(k,i)times b(n,k)times b(m,k)\
=sum_k=1^i(-1)^i-kichoose kkchoose nkchoose m$$
And the function $g()$ is used to compute each term $a_i$ for $1le i le n+m$.
answered 8 hours ago
Arnauld
66.3k583280
add a comment |Â
up vote
1
down vote
Wolfram Language (Mathematica), 58 bytes
Inverse[b=Array[Binomial,+##1,1]].(b[[;;,#]]b[[;;,#2]])&
Try it online!
answered 26 mins ago
alephalpha
20.5k32886
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
Haskell, 84 bytes
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
Explanation
Given a polynomial $q$, the following algorithm (see here) computes the unique coefficients $a_0,a_1,ldots$ such that $q=a_0p_0+a_1p_1+ldots$.
Let
$$
Delta^(0)q(x)=q(x)\
Delta^(i+1)q(x)=Delta^(i)q(x+1)-Delta^(i)q(x).
$$
Then $a_i=Delta^(i)q(0)$.
Moreover, it can be easily proved that
$$
Delta^(i)q(0)=sum_k=0^i(-1)^i-kichoose kq(k).
$$
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
The function # computes the answer to the challenge. It simply uses the observation above to compute
$$
a_i=sum_k=0^i(-1)^i-kichoose kkchoose nkchoose m.
$$
The foldr1(-) is the only thing that needs explaining. When applied to a list $[b_0,b_1,ldots,b_l]$, foldr1(-) returns
$$
b_0-(b_1-(ldots-(b_l-1-b_l)ldots)=sum_j=0^l(-1)^jb_j
$$
Haskell, 108 100 bytes
I'm also keeping this one. It is, in my opinion, more elegant, albeit much more verbose.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
The function # computes the answer to the challenge. Let $q=p_ncdot p_m$.
[x!n*x!m|x<-[0..]]is the infinite list
$$
left[0choose n0choose m,1choose n1choose m,2choose n2choose m,ldotsright]
$$
i.e.
$$
[q(0),q(1),q(2),ldots].
$$- Given a list $[b_0,b_1,b_2,ldots]$, the function
zipWith(-)=<<tailreturns $[b_1-b_0,b_2-b_1,ldots]$. Thus the codehead<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]returns the infinite list
$$
[Delta^(0)q(0),Delta^(1)q(0),Delta^(2)q(0),ldots]=[a_0,a_1,a_2,ldots].
$$ - Finally with
take(n+m).tailwe drop $a_0$ and we take the first $n+m$ coefficients, thereby solving the challenge.
answered 19 hours ago
Delfad0r
963213
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
add a comment |Â
up vote
4
down vote
Haskell, 84 bytes
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
Explanation
Given a polynomial $q$, the following algorithm (see here) computes the unique coefficients $a_0,a_1,ldots$ such that $q=a_0p_0+a_1p_1+ldots$.
Let
$$
Delta^(0)q(x)=q(x)\
Delta^(i+1)q(x)=Delta^(i)q(x+1)-Delta^(i)q(x).
$$
Then $a_i=Delta^(i)q(0)$.
Moreover, it can be easily proved that
$$
Delta^(i)q(0)=sum_k=0^i(-1)^i-kichoose kq(k).
$$
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
The function # computes the answer to the challenge. It simply uses the observation above to compute
$$
a_i=sum_k=0^i(-1)^i-kichoose kkchoose nkchoose m.
$$
The foldr1(-) is the only thing that needs explaining. When applied to a list $[b_0,b_1,ldots,b_l]$, foldr1(-) returns
$$
b_0-(b_1-(ldots-(b_l-1-b_l)ldots)=sum_j=0^l(-1)^jb_j
$$
Haskell, 108 100 bytes
I'm also keeping this one. It is, in my opinion, more elegant, albeit much more verbose.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
The function # computes the answer to the challenge. Let $q=p_ncdot p_m$.
[x!n*x!m|x<-[0..]]is the infinite list
$$
left[0choose n0choose m,1choose n1choose m,2choose n2choose m,ldotsright]
$$
i.e.
$$
[q(0),q(1),q(2),ldots].
$$- Given a list $[b_0,b_1,b_2,ldots]$, the function
zipWith(-)=<<tailreturns $[b_1-b_0,b_2-b_1,ldots]$. Thus the codehead<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]returns the infinite list
$$
[Delta^(0)q(0),Delta^(1)q(0),Delta^(2)q(0),ldots]=[a_0,a_1,a_2,ldots].
$$ - Finally with
take(n+m).tailwe drop $a_0$ and we take the first $n+m$ coefficients, thereby solving the challenge.
answered 19 hours ago
Delfad0r
963213
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Haskell, 84 bytes
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
Explanation
Given a polynomial $q$, the following algorithm (see here) computes the unique coefficients $a_0,a_1,ldots$ such that $q=a_0p_0+a_1p_1+ldots$.
Let
$$
Delta^(0)q(x)=q(x)\
Delta^(i+1)q(x)=Delta^(i)q(x+1)-Delta^(i)q(x).
$$
Then $a_i=Delta^(i)q(0)$.
Moreover, it can be easily proved that
$$
Delta^(i)q(0)=sum_k=0^i(-1)^i-kichoose kq(k).
$$
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
The function # computes the answer to the challenge. It simply uses the observation above to compute
$$
a_i=sum_k=0^i(-1)^i-kichoose kkchoose nkchoose m.
$$
The foldr1(-) is the only thing that needs explaining. When applied to a list $[b_0,b_1,ldots,b_l]$, foldr1(-) returns
$$
b_0-(b_1-(ldots-(b_l-1-b_l)ldots)=sum_j=0^l(-1)^jb_j
$$
Haskell, 108 100 bytes
I'm also keeping this one. It is, in my opinion, more elegant, albeit much more verbose.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
The function # computes the answer to the challenge. Let $q=p_ncdot p_m$.
[x!n*x!m|x<-[0..]]is the infinite list
$$
left[0choose n0choose m,1choose n1choose m,2choose n2choose m,ldotsright]
$$
i.e.
$$
[q(0),q(1),q(2),ldots].
$$- Given a list $[b_0,b_1,b_2,ldots]$, the function
zipWith(-)=<<tailreturns $[b_1-b_0,b_2-b_1,ldots]$. Thus the codehead<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]returns the infinite list
$$
[Delta^(0)q(0),Delta^(1)q(0),Delta^(2)q(0),ldots]=[a_0,a_1,a_2,ldots].
$$ - Finally with
take(n+m).tailwe drop $a_0$ and we take the first $n+m$ coefficients, thereby solving the challenge.
answered 19 hours ago
Delfad0r
963213
Haskell, 84 bytes
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
Explanation
Given a polynomial $q$, the following algorithm (see here) computes the unique coefficients $a_0,a_1,ldots$ such that $q=a_0p_0+a_1p_1+ldots$.
Let
$$
Delta^(0)q(x)=q(x)\
Delta^(i+1)q(x)=Delta^(i)q(x+1)-Delta^(i)q(x).
$$
Then $a_i=Delta^(i)q(0)$.
Moreover, it can be easily proved that
$$
Delta^(i)q(0)=sum_k=0^i(-1)^i-kichoose kq(k).
$$
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=[foldr1(-)[i!k*k!n*k!m|k<-[i,i-1..0]]|i<-[1..n+m]]
The function # computes the answer to the challenge. It simply uses the observation above to compute
$$
a_i=sum_k=0^i(-1)^i-kichoose kkchoose nkchoose m.
$$
The foldr1(-) is the only thing that needs explaining. When applied to a list $[b_0,b_1,ldots,b_l]$, foldr1(-) returns
$$
b_0-(b_1-(ldots-(b_l-1-b_l)ldots)=sum_j=0^l(-1)^jb_j
$$
Haskell, 108 100 bytes
I'm also keeping this one. It is, in my opinion, more elegant, albeit much more verbose.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
_!0=1
n!k=n*(n-1)!(k-1)`div`k
Try it online!
_!0=1
n!k=n*(n-1)!(k-1)`div`k
n!k is the binomial coefficient $nchoose k$.
n#m=take(n+m).tail$head<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]
The function # computes the answer to the challenge. Let $q=p_ncdot p_m$.
[x!n*x!m|x<-[0..]]is the infinite list
$$
left[0choose n0choose m,1choose n1choose m,2choose n2choose m,ldotsright]
$$
i.e.
$$
[q(0),q(1),q(2),ldots].
$$- Given a list $[b_0,b_1,b_2,ldots]$, the function
zipWith(-)=<<tailreturns $[b_1-b_0,b_2-b_1,ldots]$. Thus the codehead<$>iterate(zipWith(-)=<<tail)[x!n*x!m|x<-[0..]]returns the infinite list
$$
[Delta^(0)q(0),Delta^(1)q(0),Delta^(2)q(0),ldots]=[a_0,a_1,a_2,ldots].
$$ - Finally with
take(n+m).tailwe drop $a_0$ and we take the first $n+m$ coefficients, thereby solving the challenge.
answered 19 hours ago
Delfad0r
963213
edited 10 hours ago
answered 19 hours ago
Delfad0r
963213
answered 19 hours ago
Delfad0r
963213
answered 19 hours ago
Delfad0r
963213
963213
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
add a comment |Â
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
Cool! I guess this is a sort of discrete Taylor expansion.
– Hood
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
@Hood Indeed ;)
– Delfad0r
19 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
This description also explains why p_m*p_n never involves binomial coefficients lower than min(m,n): the discrete derivative has a product rule: D(f*g)=D(f(x))*g(x+1) + f(x)*D(g(x)). Applying this k times, you can see that D^k(f*g)=D^n(f(x))*g(x+k) + D^k-1(f(x))*D(g(x+k-1)) + ... + f(x)*D^n(g(x)). If k<n then all of the derivatives of p_n have value zero at zero, so D^k(p_n*g)(0)=0.
– Hood
3 hours ago
add a comment |Â
up vote
3
down vote
Haskell, 74 bytes
a%b|let a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a=map(a?)[1..a+b]
Try it online!
Uses a recursive formulation I found. Let $g_b(a,i)$ be the coefficient of $p_i$ in $p_a p_b$, which is implemented in the code by a?i (with b fixed). We can express $g_b$ recursively as
$$g_b(a,i)=fracicdot g_b(a-1,i-1)-(a-1-i)cdot g_b(a-1,i-1)a$$
with base case
$$g_b(0,i)=
begincases
1,text if b=i\
0,text otherwise\
endcases
$$
The base case corresponds to the expansion for $p_b$, which has a single nonzero coefficient of $p_i$ at $i=b$. The code implements this indicator function as 0^(i-b)^2.
The code has guards belonging to the definition of ? in the let binding. It's perhaps easier to read as the following (non-working) code where the definition of a?i expects b as a global variable. Perhaps confusingly, the a in the definition of ? is not always the same as the input to %, since it recurses down.
a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a
a%b=map(a?)[1..a+b]
The main function % lists the coefficients for each i from 1 to a+b. It's possible to code the recursion in % directly by zipping shifted lists, but I did not find a short way to do it especially with the dependence on the position i.
answered 2 hours ago
xnor
87.7k17182433
add a comment |Â
up vote
3
down vote
Haskell, 74 bytes
a%b|let a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a=map(a?)[1..a+b]
Try it online!
Uses a recursive formulation I found. Let $g_b(a,i)$ be the coefficient of $p_i$ in $p_a p_b$, which is implemented in the code by a?i (with b fixed). We can express $g_b$ recursively as
$$g_b(a,i)=fracicdot g_b(a-1,i-1)-(a-1-i)cdot g_b(a-1,i-1)a$$
with base case
$$g_b(0,i)=
begincases
1,text if b=i\
0,text otherwise\
endcases
$$
The base case corresponds to the expansion for $p_b$, which has a single nonzero coefficient of $p_i$ at $i=b$. The code implements this indicator function as 0^(i-b)^2.
The code has guards belonging to the definition of ? in the let binding. It's perhaps easier to read as the following (non-working) code where the definition of a?i expects b as a global variable. Perhaps confusingly, the a in the definition of ? is not always the same as the input to %, since it recurses down.
a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a
a%b=map(a?)[1..a+b]
The main function % lists the coefficients for each i from 1 to a+b. It's possible to code the recursion in % directly by zipping shifted lists, but I did not find a short way to do it especially with the dependence on the position i.
answered 2 hours ago
xnor
87.7k17182433
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Haskell, 74 bytes
a%b|let a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a=map(a?)[1..a+b]
Try it online!
Uses a recursive formulation I found. Let $g_b(a,i)$ be the coefficient of $p_i$ in $p_a p_b$, which is implemented in the code by a?i (with b fixed). We can express $g_b$ recursively as
$$g_b(a,i)=fracicdot g_b(a-1,i-1)-(a-1-i)cdot g_b(a-1,i-1)a$$
with base case
$$g_b(0,i)=
begincases
1,text if b=i\
0,text otherwise\
endcases
$$
The base case corresponds to the expansion for $p_b$, which has a single nonzero coefficient of $p_i$ at $i=b$. The code implements this indicator function as 0^(i-b)^2.
The code has guards belonging to the definition of ? in the let binding. It's perhaps easier to read as the following (non-working) code where the definition of a?i expects b as a global variable. Perhaps confusingly, the a in the definition of ? is not always the same as the input to %, since it recurses down.
a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a
a%b=map(a?)[1..a+b]
The main function % lists the coefficients for each i from 1 to a+b. It's possible to code the recursion in % directly by zipping shifted lists, but I did not find a short way to do it especially with the dependence on the position i.
answered 2 hours ago
xnor
87.7k17182433
Haskell, 74 bytes
a%b|let a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a=map(a?)[1..a+b]
Try it online!
Uses a recursive formulation I found. Let $g_b(a,i)$ be the coefficient of $p_i$ in $p_a p_b$, which is implemented in the code by a?i (with b fixed). We can express $g_b$ recursively as
$$g_b(a,i)=fracicdot g_b(a-1,i-1)-(a-1-i)cdot g_b(a-1,i-1)a$$
with base case
$$g_b(0,i)=
begincases
1,text if b=i\
0,text otherwise\
endcases
$$
The base case corresponds to the expansion for $p_b$, which has a single nonzero coefficient of $p_i$ at $i=b$. The code implements this indicator function as 0^(i-b)^2.
The code has guards belonging to the definition of ? in the let binding. It's perhaps easier to read as the following (non-working) code where the definition of a?i expects b as a global variable. Perhaps confusingly, the a in the definition of ? is not always the same as the input to %, since it recurses down.
a?i|a<1=0^(i-b)^2|d<-a-1=div(i*d?(i-1)-(d-i)*d?i)a
a%b=map(a?)[1..a+b]
The main function % lists the coefficients for each i from 1 to a+b. It's possible to code the recursion in % directly by zipping shifted lists, but I did not find a short way to do it especially with the dependence on the position i.
answered 2 hours ago
xnor
87.7k17182433
answered 2 hours ago
xnor
87.7k17182433
answered 2 hours ago
xnor
87.7k17182433
answered 2 hours ago
xnor
87.7k17182433
87.7k17182433
add a comment |Â
add a comment |Â
up vote
2
down vote
Pari/GP, 66 bytes
(m,n)->b=matpascal(m+n);([b[i,m+1]*b[i,n+1]|i<-[1..#b]]/b~)[2..#b]
Try it online!
answered 42 mins ago
alephalpha
20.5k32886
Nice answer. As a completely minor golf, curryinng gives -1 bytes (m->n->).
– Mr. Xcoder
21 mins ago
add a comment |Â
up vote
2
down vote
Pari/GP, 66 bytes
(m,n)->b=matpascal(m+n);([b[i,m+1]*b[i,n+1]|i<-[1..#b]]/b~)[2..#b]
Try it online!
answered 42 mins ago
alephalpha
20.5k32886
Nice answer. As a completely minor golf, curryinng gives -1 bytes (m->n->).
– Mr. Xcoder
21 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Pari/GP, 66 bytes
(m,n)->b=matpascal(m+n);([b[i,m+1]*b[i,n+1]|i<-[1..#b]]/b~)[2..#b]
Try it online!
answered 42 mins ago
alephalpha
20.5k32886
Pari/GP, 66 bytes
(m,n)->b=matpascal(m+n);([b[i,m+1]*b[i,n+1]|i<-[1..#b]]/b~)[2..#b]
Try it online!
answered 42 mins ago
alephalpha
20.5k32886
answered 42 mins ago
alephalpha
20.5k32886
answered 42 mins ago
alephalpha
20.5k32886
answered 42 mins ago
alephalpha
20.5k32886
20.5k32886
Nice answer. As a completely minor golf, curryinng gives -1 bytes (m->n->).
– Mr. Xcoder
21 mins ago
add a comment |Â
Nice answer. As a completely minor golf, curryinng gives -1 bytes (m->n->).
– Mr. Xcoder
21 mins ago
Nice answer. As a completely minor golf, curryinng gives -1 bytes (
m->n->).– Mr. Xcoder
21 mins ago
Nice answer. As a completely minor golf, curryinng gives -1 bytes (
m->n->).– Mr. Xcoder
21 mins ago
add a comment |Â
up vote
1
down vote
JavaScript (ES6), 109 bytes
This is really just a port of Delfad0r's great answer, implemented as nested recursive functions.
Takes input as (n)(m).
n=>m=>(g=i=>i?[...g(i-1),(h=k=>k&&h(k-1)-(b=(y,x=k)=>y?x*b(y-1,x-1)/y:i-k&1||-1)(k,i)*b(n)*b(m))(i)]:)(n+m)
Try it online!
How?
The function $b(y,x)$ computes:
$$-(-1)^i-kxchoose y$$
It's slightly shorter to return $-(-1)^i-k$ as the last iteration of this function than processing it separately. Because we compute the product of three binomial coefficients, the signs of the first two of them are simply cancelling each other out.
The function $h()$ is used to compute:
$$sum_k=1^i-b(k,i)times b(n,k)times b(m,k)\
=sum_k=1^i(-1)^i-kichoose kkchoose nkchoose m$$
And the function $g()$ is used to compute each term $a_i$ for $1le i le n+m$.
answered 8 hours ago
Arnauld
66.3k583280
add a comment |Â
up vote
1
down vote
JavaScript (ES6), 109 bytes
This is really just a port of Delfad0r's great answer, implemented as nested recursive functions.
Takes input as (n)(m).
n=>m=>(g=i=>i?[...g(i-1),(h=k=>k&&h(k-1)-(b=(y,x=k)=>y?x*b(y-1,x-1)/y:i-k&1||-1)(k,i)*b(n)*b(m))(i)]:)(n+m)
Try it online!
How?
The function $b(y,x)$ computes:
$$-(-1)^i-kxchoose y$$
It's slightly shorter to return $-(-1)^i-k$ as the last iteration of this function than processing it separately. Because we compute the product of three binomial coefficients, the signs of the first two of them are simply cancelling each other out.
The function $h()$ is used to compute:
$$sum_k=1^i-b(k,i)times b(n,k)times b(m,k)\
=sum_k=1^i(-1)^i-kichoose kkchoose nkchoose m$$
And the function $g()$ is used to compute each term $a_i$ for $1le i le n+m$.
answered 8 hours ago
Arnauld
66.3k583280
add a comment |Â
up vote
1
down vote
up vote
1
down vote
JavaScript (ES6), 109 bytes
This is really just a port of Delfad0r's great answer, implemented as nested recursive functions.
Takes input as (n)(m).
n=>m=>(g=i=>i?[...g(i-1),(h=k=>k&&h(k-1)-(b=(y,x=k)=>y?x*b(y-1,x-1)/y:i-k&1||-1)(k,i)*b(n)*b(m))(i)]:)(n+m)
Try it online!
How?
The function $b(y,x)$ computes:
$$-(-1)^i-kxchoose y$$
It's slightly shorter to return $-(-1)^i-k$ as the last iteration of this function than processing it separately. Because we compute the product of three binomial coefficients, the signs of the first two of them are simply cancelling each other out.
The function $h()$ is used to compute:
$$sum_k=1^i-b(k,i)times b(n,k)times b(m,k)\
=sum_k=1^i(-1)^i-kichoose kkchoose nkchoose m$$
And the function $g()$ is used to compute each term $a_i$ for $1le i le n+m$.
answered 8 hours ago
Arnauld
66.3k583280
JavaScript (ES6), 109 bytes
This is really just a port of Delfad0r's great answer, implemented as nested recursive functions.
Takes input as (n)(m).
n=>m=>(g=i=>i?[...g(i-1),(h=k=>k&&h(k-1)-(b=(y,x=k)=>y?x*b(y-1,x-1)/y:i-k&1||-1)(k,i)*b(n)*b(m))(i)]:)(n+m)
Try it online!
How?
The function $b(y,x)$ computes:
$$-(-1)^i-kxchoose y$$
It's slightly shorter to return $-(-1)^i-k$ as the last iteration of this function than processing it separately. Because we compute the product of three binomial coefficients, the signs of the first two of them are simply cancelling each other out.
The function $h()$ is used to compute:
$$sum_k=1^i-b(k,i)times b(n,k)times b(m,k)\
=sum_k=1^i(-1)^i-kichoose kkchoose nkchoose m$$
And the function $g()$ is used to compute each term $a_i$ for $1le i le n+m$.
answered 8 hours ago
Arnauld
66.3k583280
edited 7 hours ago
answered 8 hours ago
Arnauld
66.3k583280
answered 8 hours ago
Arnauld
66.3k583280
answered 8 hours ago
Arnauld
66.3k583280
66.3k583280
add a comment |Â
add a comment |Â
up vote
1
down vote
Wolfram Language (Mathematica), 58 bytes
Inverse[b=Array[Binomial,+##1,1]].(b[[;;,#]]b[[;;,#2]])&
Try it online!
answered 26 mins ago
alephalpha
20.5k32886
add a comment |Â
up vote
1
down vote
Wolfram Language (Mathematica), 58 bytes
Inverse[b=Array[Binomial,+##1,1]].(b[[;;,#]]b[[;;,#2]])&
Try it online!
answered 26 mins ago
alephalpha
20.5k32886
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Wolfram Language (Mathematica), 58 bytes
Inverse[b=Array[Binomial,+##1,1]].(b[[;;,#]]b[[;;,#2]])&
Try it online!
answered 26 mins ago
alephalpha
20.5k32886
Wolfram Language (Mathematica), 58 bytes
Inverse[b=Array[Binomial,+##1,1]].(b[[;;,#]]b[[;;,#2]])&
Try it online!
answered 26 mins ago
alephalpha
20.5k32886
answered 26 mins ago
alephalpha
20.5k32886
answered 26 mins ago
alephalpha
20.5k32886
answered 26 mins ago
alephalpha
20.5k32886
20.5k32886
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173984%2fmultiply-numerical-polynomials%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
4
Just an FYI we have MathJax now so you can use
$to write in-line equations like $ p_m $ instead of using images.– FryAmTheEggman
20 hours ago
Looks like every test is missing the $a_0=0$ entry; so are the inputs actually going to be strictly positive integers or should
(0,0)yield an empty list?– Jonathan Allan
20 hours ago
@JonathanAllan Strictly positive -- none of the polynomials have a constant coefficient so it would be kind of boring.
– Hood
19 hours ago
@FryAmTheEggman That's good to know because making the images is quite annoying.
– Hood
19 hours ago
@JonathanAllan I guess I shouldn't have given p_0 as an example of a basis element...
– Hood
19 hours ago