# Calculate the n-th iterate of a polynomial for a specific value; fⁿ(x)

Given a polynomial function f (e.g. as a list p of real coefficients in ascending or descending order), a non-negative integer n, and a real value x, return:

# fn(x)

i.e. the value of f (f (f (…f (x)…))) for n applications of f on x.

Use reasonable precision and rounding.

Solutions that take f as a list of coefficients will probably be the most interesting, but if you are able to take f as an actual function (thereby reducing this challenge to the trivial "apply a function n times"), feel free to include it after your non-trivial solution.

### Example cases

p =[1,0,0] or f =x^2, n =0, x =3: f0(3) =3

p =[1,0,0] or f =x^2, n =1, x =3: f1(3) =9

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =0, x =2.3: f0(2.3) =2.3

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =1, x =2.3: f1(2.3) =-8.761

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =2, x =2.3: f2(2.3) =23.8258

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =3, x =2.3: f3(2.3) =-2.03244

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =4, x =2.3: f4(2.3) =1.08768

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =5, x =2.3: f5(2.3) =-6.38336

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =6, x =2.3: f6(2.3) =14.7565

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =7, x =2.3: f7(2.3) =-16.1645

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =8, x =2.3: f8(2.3) =59.3077

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =9, x =2.3: f9(2.3) =211.333

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =10, x =2.3: f10(2.3) =3976.08

p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =11, x =2.3: f11(2.3) =1571775

p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =0, x =-1.1: f0(-1.1) =-1.1

p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =1, x =-1.1: f1(-1.1) =1.349

p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =2, x =-1.1: f2(-1.1) =6.92072

p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =14, x =-1.1: f14(-1.1) =15.6131

p =[0.02,0,0,0,-0.05] or f =0.02x^4-0.05, n =25, x =0.1: f25(0.1) =-0.0499999

p =[0.02,0,-0.01,0,-0.05] or f =0.02x^4-0.01x^2-0.05, n =100, x =0.1: f100(0.1) =-0.0500249

• Related – Adám Aug 4 '17 at 10:58
• Can my Jelly answer take a Jelly link and consider it a "function", for example? – Erik the Outgolfer Aug 4 '17 at 11:21
• @EriktheOutgolfer I originally required input as list of coefficients in order to prevent such trivial solutions. However, I relaxed it by request. I suggest that you post the list version, and add the trivial version as a note (or opposite). – Adám Aug 4 '17 at 11:23
• I've already posted the list version, but the function version is a lot shorter. – Erik the Outgolfer Aug 4 '17 at 11:24
• @EriktheOutgolfer Yeah, obviously. See my added note. – Adám Aug 4 '17 at 11:25

# Octave, 49 bytes

@(p,x,n)(f=@(r,m){@()p(r(r,m-1)),x}{~m+1}())(f,n)


Try it online!

Or, taking coefficients:

## Octave, 75 57 bytes

@(p,x,n)(f=@(f,n){@()polyval(p,f(f,n-1)),x}{~n+1}())(f,n)


Try it online!

A special thanks for Suever over at StackOverflow, for this answer some time ago on a question of mine, proving that a recursive anonymous function is possible.

This defines an anonymous function, which is a wrapper for a recursive anonymous function; something which is not a native Octave concept, and requires some fancy cell array indexing.

As a bonus, the second version is a nice lesson in variable scoping in Octave. All instances of r can legally be replaced by f, which then simply overwrites the existing f in the most local scope (similar for n)

### Explanation

@(p,x,n)(f=@(r,m){@()p(r(r,m-1)),x}{~m+1}())(f,n)
@(p,x,n)         .                ..    .  ..   .   % Defines main anonymous function
(f=@(r,m).                ..    .  ).   .   % Defines recursive anonymous function
.                ..    .   .   .   %  r: Handle ('pointer') to recursive function
.                ..    .   .   .   %  m: Current recursion depth (counting from n to 0)
.                ..    .   (f,n)   % And call it, with
.                ..    .           %  r=f (handle to itself)
.                ..    .           %  m=n (initial recursion)
{                }{    }           % Create and index into cell array
~m+1            %  Index: for m>0: 1; for m==0: 2.
,x                  %  Index 2: final recursion, just return x.
@()                               %  Index 1: define anonymous function, taking no inputs.
p(        )                    %   which evaluates the polynomial
r(     )                     %    of the recursive function call
r,m-1                      %     which is called with r
%     and recursion depth m-1
%     (until m=0, see above)
()         % Evaluate the result of the cell array indexing operation.
%  which is either the anonymous function
%  or the constant x.


The key to this is that anonymous functions are not evaluated when they are defined. So, the @(), which seems a bit superfluous since it defines an anonymous function which is called with () directly after, is actually strictly necessary. It is not called unless it is selected by the indexing statement.

### Octave, 39 bytes (boring way)

function x=f(p,x,n)for i=1:n;o=p(o);end


Just for completeness, the Octave solution with the shortest bytecount. Yawn..

• I'll try rereading this another time, but I still don't quite get it.. As a big Octave fan I can only say, great job +1. – Michthan Aug 4 '17 at 15:27
• @Michthan l'll try and make a better explanation, but it's by far the most terse Octave I've written - usually, function names are the majority of the byte count. It's almost Lisp. – Sanchises Aug 4 '17 at 17:03
• @Michthan Hopefully, the new explanation makes some sense, looking at it in an 'exploded' view. – Sanchises Aug 4 '17 at 19:54

# Mathematica, 5647 28 bytes

Nest[x\[Function]x#+#2&~Fold~#,##2]&


\[Function] takes 3 bytes in UTF-8.

Take parameters in order p,x,n.

p (parameter 1) is in increasing order of degree.

Obviously if f can be taken as a function this can be reduced just to Nest.

• Do you need to reverse the coefficients? – Giuseppe Aug 4 '17 at 11:19
• @Giuseppe That's why there is Reverse in the code. – user202729 Aug 4 '17 at 11:19
• @user202729 I think you can take the coefficients in whatever order you want, either ascending or descending. – Erik the Outgolfer Aug 4 '17 at 11:20
• We are allowed to take them in increasing or decreasing order of degree, I believe. (I don't know Mathematica at all) – Giuseppe Aug 4 '17 at 11:21
• Yes, you can can take them in desired order: in ascending or descending order – Adám Aug 4 '17 at 11:21

# Husk, 5 bytes

←↓¡B


Try it online!

The key idea here is that evaluating a polinomial at a point x is equivalent to performing base conversion from base x.

B when given a base and a list of digits performs base conversion. Here we use its flipped version, in order to take the list of digits first and partially apply this function to it. We obtain then a function which computes the value of the given polynomial at a point, the second part of this solution deals with iterating this function the correct amount of times:

# Husk, 3 bytes

←↓¡


¡ is the "iterate" function, it takes a function and a starting point and returns the infinite list of values obtained iterating the function.

↓ takes a number (the third argument of this challenge) and drops that many elements from the start of the list.

← returns the first element of the resulting list.

# Pari/GP, 31 bytes

(p,n,x)->for(i=1,n,x=eval(p));x


Try it online!

# Ruby, 42 bytes

->c,n,x{n.times{x=c.reduce{|s,r|s*x+r}};x}


C is the list of coefficients in descending order

Trivial version, where f is a lambda function (26 bytes):

->f,n,x{n.times{x=f[x]};x}

# For example:
# g=->f,n,x{n.times{x=f[x]};x}
# p g[->x{0.02*x**4-0.01*x**2-0.05},100,0.1]


Try it online!

## JavaScript (ES6),  52 49 44  42 bytes

Saved 5 bytes thanks to G B and 2 more bytes thanks to Neil

Takes input in currying syntax as (p)(n)(x), where p is the list of coefficients in descending order.

p=>n=>g=x=>n--?g(p.reduce((s,v)=>s*x+v)):x


### Test cases

let f =

p=>n=>g=x=>n--?g(p.reduce((s,v)=>s*x+v)):x

console.log(f([1,0,0])(0)(3))
console.log(f([1,0,0])(1)(3))
console.log(f([0.1,-2.3,-4])(0)(2.3))
console.log(f([0.1,-2.3,-4])(1)(2.3))
console.log(f([0.1,-2.3,-4])(2)(2.3))
console.log(f([0.1,-2.3,-4])(3)(2.3))
console.log(f([0.1,-2.3,-4])(4)(2.3))
console.log(f([0.1,-2.3,-4])(5)(2.3))
console.log(f([0.1,-2.3,-4])(6)(2.3))
console.log(f([0.1,-2.3,-4])(7)(2.3))
console.log(f([0.1,-2.3,-4])(8)(2.3))
console.log(f([0.1,-2.3,-4])(9)(2.3))
console.log(f([0.1,-2.3,-4])(10)(2.3))
console.log(f([0.1,-2.3,-4])(11)(2.3))
console.log(f([-0.1,2.3,4])(0)(-1.1))
console.log(f([-0.1,2.3,4])(1)(-1.1))
console.log(f([-0.1,2.3,4])(2)(-1.1))
console.log(f([-0.1,2.3,4])(14)(-1.1))
console.log(f([0.02,0,0,0,-0.05])(25)(0.1))
console.log(f([0.02,0,-0.01,0,-0.05])(100)(0.1))

• If p is in descending order, you can reduce using s*x+v and ignore i. – G B Aug 4 '17 at 11:27
• In that case, can you omit the ,0 from the reduce? – Neil Aug 4 '17 at 15:38
• @Neil Good catch. :-) – Arnauld Aug 4 '17 at 17:03

# J, 15 bytes

0{(p.{.)^:(]{:)


Try it online!

Takes the polynomial as a list of coefficients of ascending powers.

## Explanation

0{(p.{.)^:(]{:)  Input: polynomial P (LHS), [x, n] (RHS)
{:   Tail of [x, n], gets n
]     Right identity, passes n
(    )^:       Repeat n times starting with g = [x, n]
p.              Evaluate P at that value
0{               Return the value at index 0


# 05AB1E, 10 9 bytes

-1 byte thanks to Erik the Outgolfer

sF³gÝ¨m*O


Try it online!

Takes x as first argument, n as second and p in ascending order as third.

### Explanation

sF³gÝ¨m*O
s         # Forces the top two input arguments to get pushed and swaped on the stack
F        # Do n times...
³        # Push the third input (the coefficients)
g       # Get the length of that array...
Ý¨     # and create the range [0 ... length]
m    # Take the result of the last iteration to these powers (it's just x for the first iteration)
*   # Multiply the resuling array with the corresponding coefficients
O # Sum the contents of the array
# Implicit print

• You can remove the second ³. – Erik the Outgolfer Aug 4 '17 at 12:39
• Also (This is in case n is 0 so x is on the stack) is wrong, you still need the s for non-zero n. – Erik the Outgolfer Aug 4 '17 at 12:42
• Yeah that's true. I was thinking more along the lines of replacing ¹².with s so it gets the job of pushing x to the stack done in 1 byte without needing to loop at least once. Probably should have worded that better ^^' .Also thanks for the -1! – Datboi Aug 4 '17 at 13:07
• I meant that you would still need it since 05AB1E uses the last input for implicit input if all inputs have been read. – Erik the Outgolfer Aug 4 '17 at 13:12
• "sF³gÝ¨m³O" and in the explanation too... – Erik the Outgolfer Aug 4 '17 at 13:12

((!!).).iterate


Try it online!

Thanks to totallyhuman for 11 bytes off of both solutions

This defines a tacit function that takes a function as its first argument and n as its second argument, and composes that function with itself n times. This can then be called with an argument x to get the final value. Thanks to the magic of currying, this is equivalent to one function taking three arguments.

Taking a list of coefficients instead of a function argument:

((!!).).iterate.(\p x->sum$zipWith(*)p[x^i|i<-[0..]])  Try it online! This is the same as the above code, but composed with a lambda function that converts a list of coefficients into a polynomial function. The coefficients are taken in reverse order from the examples - as ascending powers of x. • 15 bytes. – totallyhuman Mar 12 '18 at 10:22 • The TIO of the second one should take a list as argument, not a function ;) Though you can save a handful of bytes by using a fold like this (note that the zero-polynomial can't be [] but must be something like  or similar). – ბიმო Mar 13 '18 at 17:07 # APL (Dyalog), 20 9 bytes {⊥∘⍵⍣⎕⊢⍺}  Try it online! This takes x as the left argument, the coefficients of the function as the right argument, and n from STDIN. Looking back at this after many a long time, I realised I could simplify the calculation by using base conversion ⊥. # APL (Dyalog), 5 bytes If we can take the function as a Dyalog APL function, then this can be 5 bytes. ⎕⍣⎕⊢⎕  Takes x, n and then the function as input from STDIN. # R, 965855 52 bytes f=function(n,p,x)if(n,f(n-1,p,x^(seq(p)-1)%*%p),x)  Try it online! ### Explanation: seq(p) generates the list 1, 2, ..., length(p) when p is a vector, so seq(p)-1 is the exponents of the polynomial, hence x^(seq(p)-1) is equivalent to x^0 (always equal to 1), x^1, x^2, ... and computing a dot product %*% with p evaluates the polynomial at x. Additionally, if P is taken as a function, then this would be 38 bytes: function(n,P,x)if(n,f(n-1,P,P(x)),x)  And we can of course always generate P by P=function(a)function(x)sum(x^(seq(a)-1)*a) # Jelly, 10 bytes *⁹LḶ¤×⁹Sµ¡  Try it online! Takes x, coefficients in ascending order, n in this order. # 4 bytes ⁹v$¡


Try it online!

Takes x, Jelly link (may need to be quoted/escaped), n in this order.

# Python 3, 70 69 bytes

f=lambda p,n,x:n and f(p,n-1,sum(c*x**i for i,c in enumerate(p)))or x


Takes p in ascending order, i.e. if p is [0, 1, 2] then the corresponding polynomial is p(x) = 0 + 1*x + 2*x^2. Simple recursion solution.

Try it online!

# C# (.NET Core), 82 bytes

using System.Linq;f=(p,n,x)=>n<1?x:p.Select((c,i)=>c*Math.Pow(f(p,n-1,x),i)).Sum()


Try it online!

Takes a list of coefficients in the opposite order from the test cases (increasing order?) so that their index in the array is equal to the power x should be raised to.

And the trivial version in 30 bytes:

f=(p,n,x)=>n<1?x:f(p,n-1,p(x))


Try it online!

Takes a delegate and applies it recursively n times.

# MATL, 11 bytes

ii:"ZQ6Mw]&


Try it online!

Slightly less interesting than my Octave answer, although I think there's some clever juggling of inputs to make sure n=0 works as expected.

## Julia 0.6.0 (78 bytes)

using Polynomials;g(a,n,x)=(p=Poly(a);(n>0&&(return g(a,n-1,p(x)))||return x))

Explainations:

The package Polynomials is pretty self explanatory: it creates polynomials. After that it's a pretty basic recursion.

In order to have a polynomial: -4.0 - 2.3*x + 0.1*x^2 the input a must be like a = [-4, -2.3, 0.1]

# Axiom, 91 bytes

f(n,g,x)==(for i in 1..n repeat(v:=1;r:=0;for j in 1..#g repeat(r:=r+v*g.j;v:=v*x);x:=r);x)


indented

fn(n,g,x)==
for i in 1..n repeat
v:=1; r:=0
for j in 1..#g repeat(r:=r+v*g.j;v:=v*x)
x:=r
x


the input for polynomy g it is one list of numbers in the reverse of the example of exercise. for example

[1,2,3,4,5]


it would represent the polinomy

1+2*x+3*x^2+4*x^3+5*x^4


test:

(3) -> f(0,[0,0,1],3)
(3)  3
Type: PositiveInteger
(4) -> f(1,[0,0,1],3)
(4)  9
Type: PositiveInteger
(5) -> f(0,[-4,-2.30,0.1],2.3)
(5)  2.3
Type: Float
(6) -> f(1,[-4,-2.30,0.1],2.3)
(6)  - 8.7610000000 000000001
Type: Float
(7) -> f(2,[-4,-2.30,0.1],2.3)
(7)  23.8258121
Type: Float
(8) -> f(9,[-4,-2.30,0.1],2.3)
(8)  211.3326335688 2052491
Type: Float
(9) -> f(9,[-4,-2.30,0.1,0,0,0,0,1],2.3)
(9)  0.4224800431 1790652974 E 14531759
Type: Float
Time: 0.03 (EV) + 0.12 (OT) = 0.15 sec
(10) -> f(2,[-4,-2.30,0.1,0,0,0,0,1],2.3)
(10)  44199336 8495528344.36
Type: Float


# Röda, 41 bytes

f p,n,x{(*n)|x=_+p()|reduce _*x+_;[x]}


Try it online!

A trivial version:

f F,n{([_]..*n)|reduce F(_)+_}


Try it online!

It takes the the value for x from the stream.

# C++14, 71 bytes

As generic unnamed lambda, returning via the x Parameter:

[](auto C,int n,auto&x){for(auto t=x;t=0,n--;x=t)for(auto a:C)t=a+x*t;}


Ungolfed and testcase:

#include<iostream>
#include<vector>

using namespace std;

auto f=
[](auto C,int n,auto&x){
for(
auto t=x; //init temporary to same type as x
t=0, n--; //=0 at loop start, also check n
x=t       //apply the result
)
for(auto a:C)
t=a+x*t; //Horner-Scheme
}
;

int main() {
vector<double> C = {0.1,-2.3,-4};//{1,0,0};
for (int i = 0; i < 10; ++i) {
double x=2.3;
f(C, i, x);
cout << i << ": " << x << endl;
}
}


# QBIC, 19 bytes

[:|:=:*c^2+:*c+:}?c


Takes inputs as

• Number of iterations
• starting value of x
• Then the 3 parts of the polynomial

Sample output:

Command line: 8 2.3 0.1 -2.3 -4
59.30772


## Clojure, 66 bytes

#(nth(iterate(fn[v](apply +(map *(iterate(partial * v)1)%3)))%2)%)


Full example:

(def f #(nth(iterate(fn[v](apply +(map *(iterate(partial * v)1)%3)))%2)%))
(f 10 2.3 [-4 -2.3 0.1])
; 3976.0831439050253


Composing a function is 26 bytes:

#(apply comp(repeat % %2))

(def f #(apply comp(repeat % %2)))
((f 10 #(apply + (map * [-4 -2.3 0.1] (iterate (partial * %) 1)))) 2.3)
; 3976.0831439050253


# Japt, 18 bytes

Pretty straightforward, does what the challenge says on the tin.

o r_VË*ZpVÊ-EÉÃx}W
o                  // Take n and turn it into a range [0,n).
r_            }W // Reduce over the range with initial value of x.
VË             // On each iteration, map over p, yielding the item
*Z           // times the current reduced value
pVÊ-EÉ     // to the correct power,
Ãx   // returning the sum of the results.


Takes inputs in order n, p, x`.

Try it online!