Implement Euler's method

Question

The goal of this challenge is to use Euler's method to approximate the solution of a differential equation of the form f⁽ⁿ⁾(x) = c.^†

The input will be a list of integers in which the nth value represents the value of f⁽ⁿ⁾(0). The first integer is f(0), the second is f'(0), and so on. The last integer in this list is the constant and will always remain the same.

Also provided as input will be a positive (nonzero) integer x, which represents the target value (you are trying to estimate f(x)). The step size for Euler's method will always be 1. Thus, you will need to take x steps total.

If you are unfamliar with Euler's method, here is a detailed example with an explanation for the input [4, -5, 3, -1], x = 8.

x       f(x)      f'(x)     f''(x)    f'''(x)
0          4         -5          3         -1
1   4-5 = -1  -5+3 = -2   3-1 =  2         -1
2  -1-2 = -3  -2+2 =  0   2-1 =  1         -1
3  -3+0 = -3   0+1 =  1   1-1 =  0         -1
4  -3+1 = -2   1+0 =  1   0-1 = -1         -1
5  -2+1 = -1   1-1 =  0  -1-1 = -2         -1
6  -1+0 = -1   0-2 = -2  -2-1 = -3         -1
7  -1-2 = -3  -2-3 = -5  -3-1 = -4         -1
8  -3-5 = -8

Essentially, each cell in the generated table is the sum of the cell above it and the cell above and to the right. So, f(a) = f(a-1) + f'(a-1); f'(a) = f'(a-1) + f''(a-1); and f''(a) = f''(a-1) + f'''(a-1). The final answer is f(8) ≈ -8.^††

The input list will always contain 2 or more elements, all of which will have absolute values less than 10. x ≥ 1 is also guaranteed. The output is a single integer, the approximation of f(x). Input may be taken in either order (the list before x, or x before the list). x may also be the first or last element of the list, if desired.

Test cases:

[4, -5, 3, -1], x = 8 => -8
[1, 2, 3, 4, 5, 6], x = 10 => 3198
[1, 3, 3, 7], x = 20 => 8611
[-3, 3, -3, 3, -3, 3, -3, 3, -3], x = 15 => -9009
[1, 1], x = 1 => 2

---

^{†: it is notable that using an approximation method in this situation is, in fact, stupid. however, the simplest possible function was chosen for the purposes of this challenge.}

^{††: the actual value happens to be -25⅓, which would qualify this approximation as "not very good."}

Answer 1

Haskell, 38 bytes

l%n|n<1=l!!0|m<-n-1=l%m+tail(l++[0])%m

Try it online!

Improved from 39 bytes:

l%0=l!!0
l%n=l%(n-1)+tail(l++[0])%(n-1)

Recursively expresses the output l%n. Moving up corresponds to decrementing n, and moving right corresponds to taking tail l to shift all list elements one space left. So, the output l%n is the value above l%(n-1), plus the value above and to the right (tail l)%(n-1)

The base case n==0 is to take the first list element.

Ideally, the input would be padded with infinitely many zeroes to the right, since the derivatives of a polynomial eventually become zero. We simulate this by appending a 0 when we take the tail.

Weird alt 41:

(iterate(\q l->q l+q(tail l++[0]))head!!)

Answer 2

MATL, 9 bytes

:"TTZ+]1)

Try it online! Or verify all test cases.

Explanation

:"      % Implicitly input x. Do the following x times
  TT    %   Push [1 1]
  Z+    %   Convolution, keeping size. Implicitly inputs array the first time
]       % End
1)      % Get first entry. Implictly display

Answer 3

Jelly, 6 5 bytes

Ḋ+$¡Ḣ

Try it online!

-1 byte thanks to @Doorknob

Explanation

Ḋ+$¡Ḣ  - Main dyadic link. First input list, second x
       - (implicit) on the previous iteration (starting at input list)
Ḋ      - Dequeue. e.g. [-5,3,-1]
 +     - Add this to
       - (implicit) the previous iteration. e.g. [4+(-5),-5+3,3+(-1),-1+0]
  $¡   - apply this successively x times
    Ḣ  - get the first element from the resultant list

Answer 4

Brachylog, 13 12 bytes

{,0s₂ᶠ+ᵐ}ⁱ⁾h

Try it online!

How it works

{,0s₂ᶠ+ᵐ}ⁱ⁾h
{       }ⁱ⁾   iterate the previous predicate
              to the array specified by first element of input
              as many times as the second element of input
           h  and get the first element

              example input to predicate: [4, _5, 3, _1]
 ,0           append 0: [4, _5, 3, _1, 0]
   s₂ᶠ        find all substrings with length 2:
              [[4, _5], [_5, 3], [3, _1], [_1, 0]]
      +ᵐ      "add all the elements" mapped to each subarray:
              [_1, _2, _2, _1]

Previous 13-byte solution

{b,0;?z+ᵐ}ⁱ⁾h

Try it online!

How it works

{b,0;?z+ᵐ}ⁱ⁾h
{        }ⁱ⁾   iterate the previous predicate
               to the array specified by first element of input
               as many times as the second element of input
            h  and get the first element

               example input to predicate: [4, _5, 3, _1]
 b             remove the first element: [_5, 3, _1]
  ,0           append 0: [_5, 3, _1, 0]
    ;?         pair with input: [[_5, 3, _1, 0], [4, _5, 3, _1]]
      z        zip: [[_5, 4], [3, _5], [_1, 3], [0, _1]]
       +ᵐ      "add all the elements" mapped to each subarray:
               [_1, _2, _2, _1]

Answer 5

Mathematica, 32 bytes

#&@@Nest[#+Rest@#~Append~0&,##]&

                               &  make a pure function
    Nest[                 &,##]   call inner function as many times as specified
           Rest@#                 drop the first element of the list
                 ~Append~0        and add a 0 to get [b,c,d,0]
         #+                       add original list to get [a+b,b+c,c+d,d]
#&@@                              take the first element after x iterations

Answer 6

Python, 80 58 bytes

Love the math for this challenge.

f=lambda a,x:x and f(map(sum,zip(a,a[1:]+[0])),x-1)or a[0]

How it works (only works with python 2):

f=lambda a,x:                                              - new lambda function
             x and                                         - iterate itself x times
                     map(sum,zip(a,a[1:]+[0]))             - e.g; f(a) = f(a-1) + f'(a-1)
                   f(                         ,x-1)        - iterate new array into itself
                                                   or a[0] - return first element

Try it online!

100 byte alternate with use of pascals triangle

from math import factorial as F
f=lambda a,x:sum([(a+[0]*x)[i]*F(x)/(F(x-i)*F(i))for i in range(x)])

How it works (works for python 2 and 3):

sum([                                                ]) - take the sum of array
     (a+[0]*x)                                        - append x zeros
              [i]*F(x)/(F(x-i)*F(i))                  - multiply each element by x choose i
                                    for i in range(x) - do this for every element

This formula works by mapping the coefficients of row x of pascals triangle onto the array. Each element of pascals triangle is determined by the choose function of the row and index. The sum of this new array is equivalent to the output at x. It's also intuitive as the iterated process of newtons method (shown in the example) acts exactly as the construction of pascals triangle.

Try it online!

Big thanks to ovs for reducing 22 bytes by converting loop into a recursive function

Answer 7

Haskell, 52 45 bytes

l#n=iterate(zipWith(+)=<<tail.(++[0]))l!!n!!0

Usage example: [-3,3,-3,3,-3,3,-3,3,-3] # 15 -> -9009. Try it online!

How it works

iterate(      )l          -- apply the function again and again starting with l
                          -- and collect the intermediate results in a list
                          -- the function is
          (++[0])         -- append a zero 
  zipWith(+)=<<tail       -- and build list of neighbor sums
                     !!0  -- take the first element from
                  !!n     -- the nth result

Edit: @xnor saved 7 bytes. Thanks!

Answer 8

CJam, 12 bytes

q~{_(;.+}*0=

Try it online!

Explanation

The code directly implements the procedure described in the challenge.

q~            e# Read input and evaluate. Pushes the array and the number x
  {     }*    e# Do the following x times
   _          e# Duplicate array
    (;        e# Remove first element
      .+      e# Vectorized sum. The last element in the first array, which doesn't 
              e# have a corresponding entry in the second, will be left as is
          0=  e# Get first element. Implicitly display

Answer 9

Octave, 42 bytes

@(a,x)conv(a,diag(flip(pascal(x+1))))(x+1)

This defines an anonymous function. Try it online!

Explanation

The solution could be computed by repeatedly convolving the input array and the resulting arrays with [1, 1]. But convolving twice, or thrice, or ... with [1, 1] corresponds to convolving once with [1, 2 ,1], or [1, 3, 3, 1], or ...; that is, with a row of the Pascal triangle. This is obtained as the anti-diagonal of the Pascal matrix of order x+1.

Answer 10

Pyth, 10 bytes

s.e*b.cQkE

Test suite.

How it works

s.e*b.cQkE
 .e      E   for (b,k) in enumerated(array):
     .cQk        (input) choose (k)
   *b            * b
s            sum

Answer 11

APL (Dyalog), 29 bytes

{0=⍺:⊃⍵
(⍺-1)∇(+/¨2,/⍵),¯1↑⍵}

Try it online!

This is a recursive dfn, but it turns out to be too verbose. Golfing in progress...

Answer 12

Actually, 7 bytes

;lr(♀█*

Try it online!

How it works

;lr(♀█*  input:
         8, [4, -5, 3, -1]
         top of stack at the right
;        duplicate
         8, [4, -5, 3, -1], [4, -5, 3, -1]
 l       length
         8, [4, -5, 3, -1], 4
  r      range
         8, [4, -5, 3, -1], [0, 1, 2, 3]
   (     rotate stack
         [4, -5, 3, -1], [0, 1, 2, 3], 8
    ♀█   map "n choose r"
         [4, -5, 3, -1], [1, 8, 28, 56]
      *  dot product
         -8

Answer 13

JavaScript (ES6), 41 bytes

f=(a,x,[b,...c]=a)=>x--?f(a,x)+f(c,x):b|0

Port of @xnor's excellent Haskell answer. Previous 47-byte solution.

f=(a,x)=>x--?f(a.map((e,i)=>e+~~a[i+1]),x):a[0]

Answer 14

Python 3 with Numpy, 82 bytes

import numpy
def f(a,x):
 for n in range(x):a=numpy.convolve(a,[1,1])
 return a[x]

Similar to my MATL answer, but using full-size convolution, and thus the result is the x-th entry of the final array.

Try it online!

Answer 15

Python, 51 bytes

f=lambda l,n:n and f(l,n-1)+f(l[1:]+[0],n-1)or l[0]

Try it online!

This is a port of my Haskell answer.