Task

Provide code that produces a list of numbers which is the   nth  order forward difference, given a non-negative integer (specifying the order) and a list of numbers.



The first-order forward difference of a list of numbers   A   is a new list   B,   where   Bn = An+1 - An.

List   B   should have one fewer element as a result.

The second-order forward difference of   A   will be:

tdefmodule Diff do
	def forward(arr,i\\1) do
		forward(arr,[],i)
	end

	def forward([_|[]],diffs,i) do
		if i == 1 do
			IO.inspect diffs
		else 
			forward(diffs,[],i-1)
		end
	end

	def forward([val1|[val2|vals]],diffs,i) do
		forward([val2|vals],diffs++[val2-val1],i) 
	end
end 

The same as the first-order forward difference of   B.

That new list will have two fewer elements than   A   and one less than   B.

The goal of this task is to repeat this process up to the desired order.

For a more formal description, see the related   Mathworld article.



Algorithmic options

 Iterate through all previous forward differences and re-calculate a new array each time.
 Use this formula (from Wikipedia):


 




Δ

n


[
f
]
(
x
)
=

∑

k
=
0


n





(


n
k


)



(
−
1

)

n
−
k


f
(
x
+
k
)


{\displaystyle \Delta ^{n}[f](x)=\sum _{k=0}^{n}{n \choose k}(-1)^{n-k}f(x+k)}




 (Pascal's Triangle   may be useful for this option.)


      DIM A(9)
      A() = 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0
      PRINT "Original array: " FNshowarray(A())
      PROCforward_difference(1, A(), B())
      PRINT "Forward diff 1: " FNshowarray(B())
      PROCforward_difference(2, A(), C())
      PRINT "Forward diff 2: " FNshowarray(C())
      PROCforward_difference(9, A(), D())
      PRINT "Forward diff 9: " FNshowarray(D())
      END
 
      DEF PROCforward_difference(n%, a(), RETURN b())
      LOCAL c%, i%, j%
      DIM b(DIM(a(),1) - n%)
      FOR i% = 0 TO DIM(b(),1)
        b(i%) = a(i% + n%)
        c% = 1
        FOR j% = 1 TO n%
          c% = -INT(c% * (n% - j% + 1) / j% + 0.5)
          b(i%) += c% * a(i% + n% - j%)
        NEXT
      NEXT
      ENDPROC
 
      DEF FNshowarray(a())
      LOCAL i%, a$
      FOR i% = 0 TO DIM(a(),1)
        a$ += STR$(a(i%)) + ", "
      NEXT
      = LEFT$(LEFT$(a$))