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

19

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:

   f n(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: f 0(3) =3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p =[0.02,0,0,0,-0.05] or f =0.02x^4-0.05, n =25, x =0.1: f 25(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: f 100(0.1) =-0.0500249

Adám

Posted 2017-08-04T10:58:20.507

Reputation: 37 779

Related – Adám – 2017-08-04T10:58:30.703

Can my Jelly answer take a Jelly link and consider it a "function", for example? – Erik the Outgolfer – 2017-08-04T11:21:24.177

@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 – 2017-08-04T11:23:46.880

I've already posted the list version, but the function version is a lot shorter. – Erik the Outgolfer – 2017-08-04T11:24:41.120

@EriktheOutgolfer Yeah, obviously. See my added note. – Adám – 2017-08-04T11:25:42.610

Added the Jelly link version, below the list version. – Erik the Outgolfer – 2017-08-04T11:27:13.180

So, in terms of lambda calculus, λf.λn.λx.n f x? – Zacharý – 2017-08-05T14:50:38.653

@Zacharý If you say so… I don't speak lambda. – Adám – 2017-08-05T21:57:42.613

With lambda definition n f n is already a function for this – l4m2 – 2018-03-12T09:53:46.447

Answers

7

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..

Sanchises

Posted 2017-08-04T10:58:20.507

Reputation: 8 530

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 – 2017-08-04T15:27:50.433

2@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 – 2017-08-04T17:03:23.083

1@Michthan Hopefully, the new explanation makes some sense, looking at it in an 'exploded' view. – Sanchises – 2017-08-04T19:54:08.553

4

Mathematica, 56 47 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.

user202729

Posted 2017-08-04T10:58:20.507

Reputation: 14 620

Do you need to reverse the coefficients? – Giuseppe – 2017-08-04T11:19:29.413

@Giuseppe That's why there is Reverse in the code. – user202729 – 2017-08-04T11:19:51.450

@user202729 I think you can take the coefficients in whatever order you want, either ascending or descending. – Erik the Outgolfer – 2017-08-04T11:20:11.703

We are allowed to take them in increasing or decreasing order of degree, I believe. (I don't know Mathematica at all) – Giuseppe – 2017-08-04T11:21:05.113

Yes, you can can take them in desired order: in ascending or descending order – Adám – 2017-08-04T11:21:27.870

How does \[Function] look? – Adám – 2017-08-04T11:33:36.960

@Adám Similar to ↦. – user202729 – 2017-08-04T11:48:43.240

4

Pari/GP, 31 bytes

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

Try it online!

alephalpha

Posted 2017-08-04T10:58:20.507

Reputation: 23 988

4

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.

Leo

Posted 2017-08-04T10:58:20.507

Reputation: 8 482

3

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))

Arnauld

Posted 2017-08-04T10:58:20.507

Reputation: 111 334

If p is in descending order, you can reduce using s*x+v and ignore i. – G B – 2017-08-04T11:27:55.547

In that case, can you omit the ,0 from the reduce? – Neil – 2017-08-04T15:38:18.280

@Neil Good catch. :-) – Arnauld – 2017-08-04T17:03:31.493

3

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!

G B

Posted 2017-08-04T10:58:20.507

Reputation: 11 099

2

R, 96 58 55 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)

Giuseppe

Posted 2017-08-04T10:58:20.507

Reputation: 21 077

2

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.

user41805

Posted 2017-08-04T10:58:20.507

Reputation: 16 320

2

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

Datboi

Posted 2017-08-04T10:58:20.507

Reputation: 1 213

1You can remove the second ³. – Erik the Outgolfer – 2017-08-04T12:39:18.337

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 – 2017-08-04T12:42:20.017

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 – 2017-08-04T13:07:26.460

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 – 2017-08-04T13:12:09.160

"sF³gݨm³O" and in the explanation too... – Erik the Outgolfer – 2017-08-04T13:12:51.307

Damn you're fast. Fixed. – Datboi – 2017-08-04T13:16:13.703

2

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]
     {.            Head of g
   p.              Evaluate P at that value
                   Return g = [P(head(g))]
0{               Return the value at index 0

miles

Posted 2017-08-04T10:58:20.507

Reputation: 15 654

2

Haskell, 15 bytes

((!!).).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:

Haskell, 53 bytes

((!!).).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.

Mego

Posted 2017-08-04T10:58:20.507

Reputation: 32 998

115 bytes. – totallyhuman – 2018-03-12T10:22:06.380

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 [0] or similar).

– ბიმო – 2018-03-13T17:07:39.913

1

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.

Erik the Outgolfer

Posted 2017-08-04T10:58:20.507

Reputation: 38 134

1

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 McAvoy

Posted 2017-08-04T10:58:20.507

Reputation: 229

1

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.

Kamil Drakari

Posted 2017-08-04T10:58:20.507

Reputation: 3 461

1

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.

Sanchises

Posted 2017-08-04T10:58:20.507

Reputation: 8 530

1

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]

Goysa

Posted 2017-08-04T10:58:20.507

Reputation: 91

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

RosLuP

Posted 2017-08-04T10:58:20.507

Reputation: 3 036

1

Röda, 41 bytes

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

Try it online!

A trivial version:

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

Try it online!

It takes the the value for x from the stream.

fergusq

Posted 2017-08-04T10:58:20.507

Reputation: 4 867

1

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;
 }
}

Karl Napf

Posted 2017-08-04T10:58:20.507

Reputation: 4 131

0

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

steenbergh

Posted 2017-08-04T10:58:20.507

Reputation: 7 772

0

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

NikoNyrh

Posted 2017-08-04T10:58:20.507

Reputation: 2 361

0

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!

Nit

Posted 2017-08-04T10:58:20.507

Reputation: 2 667

Asked: 2017-08-04T10:58:20.507

Viewed: 1 253 times

Active: 2018-04-30T14:24:24.597