Given two polynomials f,g of arbitrary degree over the integers, your program/function should evaluate the first polynomial in the second polynomial. f(g(x)) (a.k.a. the composition (fog)(x) of the two polynomials)


Builtins are allowed. You can assume any reasonable formatting as input/output, but the input and output format should match. E.g. formatting as a string


or as as list of coefficients:

[1,3,5] or alternatively [5,3,1]

Furthermore the input polynomials can be assumed to be fully expanded, and the outputs are also expected to be fully expanded.


A(x) = x^2 + 3x + 5, B(y) = y+1
A(B(y)) = (y+1)^2 + 3(y+1) + 5 = y^2 + 5y + 9

A(x) = x^6 + x^2 + 1, B(y) = y^2 - y
A(B(y))= y^12 - 6y^11 + 15y^10 - 20y^9 + 15y^8 - 6y^7 + y^6 + y^4 - 2 y^3 + y^2 + 1

A(x) = 24x^3 - 144x^2 + 288x - 192, B(y) = y + 2
A(B(y)) = 24y^3

A(x) = 3x^4 - 36x^3 + 138x^2 - 180x + 27, B(y) = 2y + 3
A(B(y)) = 48y^4 - 96y^2
  • \$\begingroup\$ what about builtins? \$\endgroup\$
    – Maltysen
    Apr 23 '16 at 22:15
  • 1
    \$\begingroup\$ @Maltysen "Details: Builtins are allowed.(...)" :D \$\endgroup\$
    – flawr
    Apr 23 '16 at 22:17
  • 2
    \$\begingroup\$ I think "any reasonable format" might be a bit stretchable. If a function that evaluates the polynomial is allowed, then the composition function (.) is an answer in Haskell. You probably mean some representation of the list of coefficients. \$\endgroup\$
    – xnor
    Apr 24 '16 at 0:03
  • 1
    \$\begingroup\$ The title! I just got it :-D \$\endgroup\$
    – Luis Mendo
    Apr 24 '16 at 11:46
  • 2
    \$\begingroup\$ @LuisMendo Quick thinker =P \$\endgroup\$
    – flawr
    Apr 24 '16 at 11:53

12 Answers 12


Haskell, 86 72 bytes

u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c
o g=(0:)!((<$>g).(*))!pure

Defines a function o such that o g f computes the composition f ∘ g. Polynomials are represented by a nonempty list of coefficients starting at the constant term.


*Main> o [1,1] [5,3,1]
*Main> o [0,-1,1] [1,0,1,0,0,0,1]
*Main> o [2,1] [-192,288,-144,24]
*Main> o [3,2] [27,-180,138,-36,3]

How it works

No polynomial-related builtins or libraries. Observe the similar recurrences

f(x) = a + f₁(x)x ⇒ f(x)g(x) = a g(x) + f₁(x)g(x)x,
f(x) = a + f₁(x)x ⇒ f(g(x)) = a + f₁(g(x))g(x),

for polynomial multiplication and composition, respectively. They both take the form

f(x) = a + f₁(x)x ⇒ W(f)(x) = C(a)(x) + U(W(f₁))(x).

The operator ! solves a recurrence of this form for W given U and C, using zipWith(+).(++[0,0..]) for polynomial addition (assuming the second argument is longer—for our purposes, it always will be). Then,

(0:) multiplies a polynomial argument by x (by prepending a zero coefficient);
(<$>g).(*) multiplies a scalar argument by the polynomial g;
(0:)!((<$>g).(*)) multiplies a polynomial argument by the polynomial g;
pure lifts a scalar argument to a constant polynomial (singleton list);
(0:)!((<$>g).(*))!pure composes a polynomial argument with the polynomial g.


Mathematica, 17 bytes


Example usage:

In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x]

              2       4
Out[17]= -96 x  + 48 x

TI-Basic 68k, 12 bytes


The usage is straightforward, e.g. for the first example:


Which returns

  • \$\begingroup\$ It seems like cheating to me to require the inputs to be in different variables. Does that matter for this answer? \$\endgroup\$
    – feersum
    Apr 23 '16 at 22:43
  • \$\begingroup\$ Feel free to do so, I explicitly allowed any reasonable convenient input format. \$\endgroup\$
    – flawr
    Apr 23 '16 at 22:45
  • \$\begingroup\$ Concerning the edit of your comment: yes it does matter. \$\endgroup\$
    – flawr
    Apr 23 '16 at 23:06
  • \$\begingroup\$ I'm not too familiar with the rules on this site. Is it correct for to be 1 byte in TI-BASIC? \$\endgroup\$
    – asmeurer
    Apr 25 '16 at 17:33
  • \$\begingroup\$ @asmeurer Indeed: TI-Basic is scored by the encoding used on the corresponding calculators. If you are interested in the details, you can read that here on meta. A table of tokens can be found here on ti-basic-dev. \$\endgroup\$
    – flawr
    Apr 25 '16 at 19:35

Python 2, 138 156 162 bytes

The inputs are expected to be integer lists with smallest powers first.

def c(a,b):
 g=lambda p,q:q>[]and q[0]+p*g(p,q[1:]);B=99**len(`a+b`);s=g(g(B,b),a);o=[]
 while s:o+=(s+B/2)%B-B/2,;s=(s-o[-1])/B
 return o


def c(a,b):
 w=sum(B**i*x for i,x in enumerate(b))
 s=sum(w**i*x for i,x in enumerate(a))
 while s:o+=min(s%B,s%B-B,key=abs),; s=(s-o[-1])/B
 return o

In this computation, the polynomial coefficients are seen as digits (which may be negative) of a number in a very large base. After polynomials are in this format, multiplication or addition is a single integer operation. As long as the base is sufficiently large, there won't be any carries that spill over into neighboring digits.

-18 from improving bound on B as suggested by @xnor.

  • \$\begingroup\$ Nice method. For B, would 10**len(`a+b`) be enough? \$\endgroup\$
    – xnor
    Apr 24 '16 at 1:30
  • \$\begingroup\$ @xnor Maybe... it's hard for me to tell. \$\endgroup\$
    – feersum
    Apr 24 '16 at 1:50
  • \$\begingroup\$ +1 This is a really creative solution, and a nice use of bigints!!! \$\endgroup\$
    – flawr
    Apr 24 '16 at 9:56
  • \$\begingroup\$ @xnor Now I've managed to convince myself that hte coefficient length is linear in the input length :) \$\endgroup\$
    – feersum
    Apr 24 '16 at 14:14

Python + SymPy, 59 35 bytes

from sympy import*

Thanks to @asmeurer for golfing off 24 bytes!

Test run

>>> from sympy import*
>>> var('x')
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
  • 1
    \$\begingroup\$ SymPy has a compose() function. \$\endgroup\$
    – asmeurer
    Apr 24 '16 at 16:30
  • 1
    \$\begingroup\$ Where's the answer? It no longer defines any functions or does anything... \$\endgroup\$
    – feersum
    Apr 24 '16 at 19:11
  • 1
    \$\begingroup\$ @feersum That has never been the case. You just edited that meta post. \$\endgroup\$
    – user45941
    Apr 24 '16 at 21:19
  • 3
    \$\begingroup\$ @feersum You edited an accepted meta post to modify the policy for your own agenda. That's not ok. \$\endgroup\$
    – user45941
    Apr 24 '16 at 21:22
  • 3
    \$\begingroup\$ @feersum Though you may have thought your wording was ambiguous, it clearly was not for the rest of the community. We accepted the consensus that from module import*;function was a valid submission. Regardless, this is a more recent policy, which allows imports and helper functions with unnamed lambdas. \$\endgroup\$
    – user45941
    Apr 24 '16 at 21:55

Sage, 24 bytes

lambda A,B:A(B).expand()

As of Sage 6.9 (the version that runs on http://sagecell.sagemath.org), function calls without explicit argument assignment (f(2) rather than f(x=2)) causes an annoying and unhelpful message to be printed to STDERR. Because STDERR can be ignored by default in code golf, this is still valid.

This is very similar to Dennis's SymPy answer because Sage is a) built on Python, and b) uses Maxima, a computer algebra system very similar to SymPy in many ways. However, Sage is much more powerful than Python with SymPy, and thus is a different enough language that it merits its own answer.

Verify all test cases online


PARI/GP, 19 bytes


which lets you do


to get

%2 = x^4 + 2*x^3 - x^2 - 2*x + 2


MATLAB with Symbolic Toolbox, 28 bytes


This is an anonymous function. To call it assign it to a variable or use ans. Inputs are strings with the format (spaces are optional)

x^2 + 3*x + 5

Example run:

>> @(f,g)collect(subs(f,'x',g))
ans = 
>> ans('3*x^4 - 36*x^3 + 138*x^2 - 180*x + 27','2*x + 3')
ans =
48*x^4 - 96*x^2

Python 2, 239 232 223 bytes

a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
m=lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in r(k+1))for k in r(len(p+q)-1)]
o=lambda f,g:e(a,[e(m,[[c]]+[g]*k)for k,c in enumerate(f)])

A 'proper' implementation that does not abuse bases. Least significant coefficient first.

a is polynomial addition, m is polynomial multiplication, and o is composition.

  • \$\begingroup\$ Is m([c],e(m,[[1]]+[g]*k)) not the same as e(m,[[c]]+[g]*k)? \$\endgroup\$
    – Neil
    Apr 24 '16 at 20:28
  • \$\begingroup\$ @Neil Good call, can squash two in one with that! \$\endgroup\$
    – orlp
    Apr 24 '16 at 20:48
  • \$\begingroup\$ a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l) \$\endgroup\$ Apr 24 '16 at 20:59
  • \$\begingroup\$ @AndersKaseorg Right, I added it, thanks :) \$\endgroup\$
    – orlp
    Apr 24 '16 at 21:12
  • \$\begingroup\$ It might be possible to simplify your polynomial addition, since I think one list will always be longer than the other, so you don't need the ( or 0) in that version. \$\endgroup\$
    – Neil
    Apr 25 '16 at 0:04

JavaScript (ES6), 150 103 bytes


Accepts and returns polynomials as an array a = [a0, a1, a2, ...] that represents a0 + a1*x + a2*x2 ...

Edit: Saved 47 bytes by switching from recursive to iterative polynomial multiplication, which then allowed me to merge two map calls.

Explanation: r is the result, which starts at zero, represented by an empty array, and p is gh, which starts at one. p is multiplied by each fh in turn, and the result accumulated in r. p is also multiplied by g at the same time.

(f,g)=>f.map(n=>            Loop through each term of f (n = f[h])
 r=p.map((m,i)=>(           Loop through each term of p (m = p[i])
  g.map((n,j)=>             Loop though each term of g (n = g[j])
   p[j+=i]=m*n+(p[j]||0)),  Accumulate p*g in p
  m*n+(r[i]||0)),           Meanwhile add p[i]*f[h] to r[i]
  p=[]),                    Reset p to 0 each loop to calculate p*g
 r=[],                      Initialise r to 0
 p=[1]                      Initialise p to 1
)&&r                        Return the result

Pyth, 51 34 bytes


Test suite.

  • 2
    \$\begingroup\$ when python outgolfs pyth \$\endgroup\$ Apr 24 '16 at 19:14
  • \$\begingroup\$ @downrep_nation not anymore :) \$\endgroup\$
    – Leaky Nun
    Aug 4 '17 at 5:52

Ruby 2.4 + polynomial, 41+12 = 53 bytes

Uses flag -rpolynomial. Input is two Polynomial objects.

If someone outgolfs me in vanilla Ruby (no polynomial external library), I will be very impressed.


Your Answer

