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


begin
    % calculate forward differences                                  %
 
    % sets elements of B to the first order forward differences of A %
    % A should have bounds 1 :: n, B should have bounds 1 :: n - 1   %
    procedure FirstOrderFDifference ( integer array A( * )
                                    ; integer array B( * )
                                    ; integer value n
                                    ) ;
        for i := 2 until n do B( i - 1 ) := A( i ) - A( i - 1 );
 
    integer array v   ( 1 :: 10 );
    integer array diff( 1 ::  9 );
    integer vPos, length;
 
    % construct the initial values array                              %    
    vPos := 1;
    for i := 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 do begin
        v( vPos ) := i;
        vPos := vPos + 1
    end for_i ;
    % calculate and show the differences                              %
    i_w    := 5; % set output format %
    length := 10;
    for order := 1 until length - 1 do begin
        FirstOrderFDifference( v, diff, length );
        length := length - 1;
        write( order, ": " ); for i := 1 until length do writeon( diff( i ) );
        for i := 1 until length do v( i ) := diff( i )
    end for_order
end.