Forward difference

Task

Provide code that produces a list of numbers which is the n^th 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 B_n = A_n+1 - A_n.

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

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

11l

Translation of: Python

<lang 11l>V dif = s -> enumerate(s[1..]).map2((i, x) -> x - @s[i]) F difn(s, n) -> [Int]

  R I n != 0 {difn(dif(s), n - 1)} E s

V s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]

L(i) 10

  print(difn(s, i))</lang>

Output:

[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
[-43, 11, -29, -7, 10, 23, -50, 50, 18]
[54, -40, 22, 17, 13, -73, 100, -32]
[-94, 62, -5, -4, -86, 173, -132]
[156, -67, 1, -82, 259, -305]
[-223, 68, -83, 341, -564]
[291, -151, 424, -905]
[-442, 575, -1329]
[1017, -1904]
[-2921]

Ada

<lang ada>with Ada.Text_Io; with Ada.Float_Text_Io; use Ada.Float_Text_Io; with Ada.containers.Vectors;

procedure Forward_Difference is

  package Flt_Vect is new Ada.Containers.Vectors(Positive, Float);
  use Flt_Vect;
  procedure Print(Item : Vector) is
  begin
     if not Item.Is_Empty then
        Ada.Text_IO.Put('[');
        for I in 1..Item.Length loop
           Put(Item => Item.Element(Positive(I)), Fore => 1, Aft => 1, Exp => 0);
            if Positive(I) < Positive(Item.Length) then
              Ada.Text_Io.Put(", ");
           end if;
        end loop;
        Ada.Text_Io.Put_line("]");
     else
        Ada.Text_IO.Put_Line("Empty List");
     end if;
     
  end Print;
  
 function Diff(Item : Vector; Num_Passes : Natural) return Vector is
     A : Vector := Item;
     B : Vector := Empty_Vector;
  begin
     if not A.Is_Empty then
        for I in 1..Num_Passes loop
           for I in 1..Natural(A.Length) - 1 loop
                 B.Append(A.Element(I + 1) - A.Element(I));
           end loop;
           Move(Target => A, Source => B);
        end loop;
     end if;
     return A;
  end Diff;
  Values : array(1..10) of Float := (90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0);
  A : Vector;

begin

  for I in Values'range loop
     A.Append(Values(I)); -- Fill the vector
  end loop;
  Print(Diff(A, 1));
  Print(Diff(A, 2));
  Print(Diff(A, 9));
  Print(Diff(A, 10));
  print(Diff(A, 0));

end Forward_Difference;</lang>

Output:

 [-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0]
 [54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0]
 [-2921.0]
 Empty List
 [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]

ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny

<lang algol68>main:(

 MODE LISTREAL = [1:0]REAL;

 OP - = (LISTREAL a,b)LISTREAL: (
   [UPB a]REAL out;
   FOR i TO UPB out DO out[i]:=a[i]-b[i] OD;
   out
 );

 FORMAT real fmt=$zzz-d.d$;
 FORMAT repeat fmt = $n(UPB s-1)(f(real fmt)",")f(real fmt)$;
 FORMAT list fmt = $"("f(UPB s=1|real fmt|repeat fmt)")"$;

 FLEX [1:0] REAL s := (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);

 printf((list fmt,s,$";"l$));
 TO UPB s-1 DO
   s := s[2:] - s[:UPB s-1];
   printf((list fmt,s,$";"l$))
 OD

)</lang>

Output:

(   90.0,   47.0,   58.0,   29.0,   22.0,   32.0,   55.0,    5.0,   55.0,   73.0);
(  -43.0,   11.0,  -29.0,   -7.0,   10.0,   23.0,  -50.0,   50.0,   18.0);
(   54.0,  -40.0,   22.0,   17.0,   13.0,  -73.0,  100.0,  -32.0);
(  -94.0,   62.0,   -5.0,   -4.0,  -86.0,  173.0, -132.0);
(  156.0,  -67.0,    1.0,  -82.0,  259.0, -305.0);
( -223.0,   68.0,  -83.0,  341.0, -564.0);
(  291.0, -151.0,  424.0, -905.0);
( -442.0,  575.0,-1329.0);
( 1017.0,-1904.0);
(-2921.0);

ALGOL W

<lang algolw>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.</lang>

Output:

    1  :   -43     11    -29     -7     10     23    -50     50     18
    2  :    54    -40     22     17     13    -73    100    -32
    3  :   -94     62     -5     -4    -86    173   -132
    4  :   156    -67      1    -82    259   -305
    5  :  -223     68    -83    341   -564
    6  :   291   -151    424   -905
    7  :  -442    575  -1329
    8  :  1017  -1904
    9  : -2921

AppleScript

Translation of: JavaScript

<lang AppleScript>-- forwardDifference :: Num a => [a] -> [a] on forwardDifference(xs)

   zipWith(my subtract, xs, rest of xs)

end forwardDifference

-- nthForwardDifference :: Num a => Int -> [a] -> [a] on nthForwardDifference(xs, i)

   |index|(iterate(forwardDifference, xs), 1 + i)

end nthForwardDifference

TEST ---------------------------

on run

   script show
       on |λ|(xs, i)
           ((i - 1) as string) & " -> " & showList(xs)
       end |λ|
   end script
   
   unlines(map(show, ¬
       take(10, ¬
           iterate(forwardDifference, ¬
               {90, 47, 58, 29, 22, 32, 55, 5, 55, 73}))))

end run

GENERIC FUNCTIONS --------------------

-- Just :: a -> Maybe a on Just(x)

   -- Constructor for an inhabited Maybe (option type) value.
   -- Wrapper containing the result of a computation.
   {type:"Maybe", Nothing:false, Just:x}

end Just

-- Nothing :: Maybe a on Nothing()

   -- Constructor for an empty Maybe (option type) value.
   -- Empty wrapper returned where a computation is not possible.
   {type:"Maybe", Nothing:true}

end Nothing

-- index (!!) :: [a] -> Int -> Maybe a -- index (!!) :: Gen [a] -> Int -> Maybe a -- index (!!) :: String -> Int -> Maybe Char on |index|(xs, i)

   if script is class of xs then
       repeat with j from 1 to i
           set v to |λ|() of xs
       end repeat
       if missing value is not v then
           Just(v)
       else
           Nothing()
       end if
   else
       if length of xs < i then
           Nothing()
       else
           Just(item i of xs)
       end if
   end if

end |index|

-- intercalate :: String -> [String] -> String on intercalate(delim, xs)

   set {dlm, my text item delimiters} to ¬
       {my text item delimiters, delim}
   set str to xs as text
   set my text item delimiters to dlm
   str

end intercalate

-- iterate :: (a -> a) -> a -> Gen [a] on iterate(f, x)

   script
       property v : missing value
       property g : mReturn(f)'s |λ|
       on |λ|()
           if missing value is v then
               set v to x
           else
               set v to g(v)
           end if
           return v
       end |λ|
   end script

end iterate

-- length :: [a] -> Int on |length|(xs)

   set c to class of xs
   if list is c or string is c then
       length of xs
   else
       (2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
   end if

end |length|

-- map :: (a -> b) -> [a] -> [b] on map(f, xs)

   -- The list obtained by applying f
   -- to each element of xs.
   tell mReturn(f)
       set lng to length of xs
       set lst to {}
       repeat with i from 1 to lng
           set end of lst to |λ|(item i of xs, i, xs)
       end repeat
       return lst
   end tell

end map

-- min :: Ord a => a -> a -> a on min(x, y)

   if y < x then
       y
   else
       x
   end if

end min

-- mReturn :: First-class m => (a -> b) -> m (a -> b) on mReturn(f)

   -- 2nd class handler function lifted into 1st class script wrapper. 
   if script is class of f then
       f
   else
       script
           property |λ| : f
       end script
   end if

end mReturn

-- showList :: [a] -> String on showList(xs)

   "[" & intercalate(", ", map(my str, xs)) & "]"

end showList

-- str :: a -> String on str(x)

   x as string

end str

-- subtract :: Num -> Num -> Num on subtract(x, y)

   y - x

end subtract

-- take :: Int -> [a] -> [a] -- take :: Int -> String -> String on take(n, xs)

   set c to class of xs
   if list is c then
       if 0 < n then
           items 1 thru min(n, length of xs) of xs
       else
           {}
       end if
   else if string is c then
       if 0 < n then
           text 1 thru min(n, length of xs) of xs
       else
           ""
       end if
   else if script is c then
       set ys to {}
       repeat with i from 1 to n
           set v to |λ|() of xs
           if missing value is v then
               return ys
           else
               set end of ys to v
           end if
       end repeat
       return ys
   else
       missing value
   end if

end take

-- unlines :: [String] -> String on unlines(xs)

   -- A single string formed by the intercalation
   -- of a list of strings with the newline character.
   set {dlm, my text item delimiters} to ¬
       {my text item delimiters, linefeed}
   set s to xs as text
   set my text item delimiters to dlm
   s

end unlines

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] on zipWith(f, xs, ys)

   set lng to min(|length|(xs), |length|(ys))
   if 1 > lng then return {}
   set xs_ to take(lng, xs) -- Allow for non-finite
   set ys_ to take(lng, ys) -- generators like cycle etc
   set lst to {}
   tell mReturn(f)
       repeat with i from 1 to lng
           set end of lst to |λ|(item i of xs_, item i of ys_)
       end repeat
       return lst
   end tell

end zipWith</lang>

Output:

0 -> [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
1 -> [-43, 11, -29, -7, 10, 23, -50, 50, 18]
2 -> [54, -40, 22, 17, 13, -73, 100, -32]
3 -> [-94, 62, -5, -4, -86, 173, -132]
4 -> [156, -67, 1, -82, 259, -305]
5 -> [-223, 68, -83, 341, -564]
6 -> [291, -151, 424, -905]
7 -> [-442, 575, -1329]
8 -> [1017, -1904]
9 -> [-2921]

AWK

<lang awk>#!/usr/bin/awk -f BEGIN {

  if (p<1) {p = 1};

}

function diff(s, p) {

  n = split(s, a, " ");
  for (j = 1; j <= p; j++) {
     for(i = 1; i <= n-j; i++) {
        a[i] = a[i+1] - a[i]; 
     }
  } 
  s = "";
  for (i = 1; i <= n-p; i++) s = s" "a[i];
  return s;

}

{

  print diff($0, p);

}</lang>

Using Pascal's triangle:

<lang awk>#!/usr/bin/awk -f BEGIN {

  if (p<1) {p = 1};

}

function diff(s, p) {

   # pascal triangled with sign changes	
   b[1] = (p%2) ? 1 : -1;
   for (j=1; j < p; j++) { 
       b[j+1] = -b[j]*(p-j)/j;
   };

   n = split(s, a, " ");
   s = "";
   for (j = 1; j <= n-p+1; j++) {
       c = 0; 
       for(i = 1; i <= p; i++) {
           c += b[i]*a[j+i-1]; 
       }
       s = s" "c;
   } 
   return s;

}

{

  print diff($0, p);

}</lang>

Output:

$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=1
 1 1 2 3 -3 -2 -1 -1
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=2
 0 1 1 -6 1 1 0
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=3
 1 0 -7 7 0 -1
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=4
 -1 -7 14 -7 -1
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=5
 -6 21 -21 6
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=6
 27 -42 27
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=7
 -69 69
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=8
 138
$ echo '0 1 2 4 7 4 2 1 0' | ./diff.awk -v p=9

BBC BASIC

Works with: BBC BASIC for Windows

<lang bbcbasic> 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$))</lang>

Output:

Original array: 90, 47, 58, 29, 22, 32, 55, 5, 55, 73
Forward diff 1: -43, 11, -29, -7, 10, 23, -50, 50, 18
Forward diff 2: 54, -40, 22, 17, 13, -73, 100, -32
Forward diff 9: -2921

C#

<lang csharp>using System; using System.Collections.Generic; using System.Linq;

class Program {

   static IEnumerable<int> ForwardDifference(IEnumerable<int> sequence, uint order = 1u)
   {
       switch (order)
       {
           case 0u:
               return sequence;
           case 1u:
               return sequence.Skip(1).Zip(sequence, (next, current) => next - current);
           default:
               return ForwardDifference(ForwardDifference(sequence), order - 1u);
       }
   }

   static void Main()
   {
       IEnumerable<int> sequence = new[] { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 };
       do
       {
           Console.WriteLine(string.Join(", ", sequence));
       } while ((sequence = ForwardDifference(sequence)).Any());
   }

}</lang>

Output:

90, 47, 58, 29, 22, 32, 55, 5, 55, 73
-43, 11, -29, -7, 10, 23, -50, 50, 18
54, -40, 22, 17, 13, -73, 100, -32
-94, 62, -5, -4, -86, 173, -132
156, -67, 1, -82, 259, -305
-223, 68, -83, 341, -564
291, -151, 424, -905
-442, 575, -1329
1017, -1904
-2921

C++

Works with: g++ version 4.1.2 20061115 (prerelease) (SUSE Linux)

This code uses a separate function to do a first-order forward difference, which is then called several times for calculating n-th order forward difference. No error checking is implemented. <lang cpp>#include <vector>

include <iterator>
include <algorithm>

// calculate first order forward difference // requires: // * InputIterator is an input iterator // * OutputIterator is an output iterator // * The value type of InputIterator is copy-constructible and assignable // * The value type of InputIterator supports operator - // * The result type of operator- is assignable to the value_type of OutputIterator // returns: The iterator following the output sequence template<typename InputIterator, typename OutputIterator>

OutputIterator forward_difference(InputIterator first, InputIterator last,
                                  OutputIterator dest)

{

 // special case: for empty sequence, do nothing
 if (first == last)
   return dest;

 typedef typename std::iterator_traits<InputIterator>::value_type value_type;

 value_type temp = *first++;
 while (first != last)
 {
   value_type temp2 = *first++;
   *dest++ = temp2 - temp;
   temp = temp2;
 }

 return dest;

}

// calculate n-th order forward difference. // requires: // * InputIterator is an input iterator // * OutputIterator is an output iterator // * The value type of InputIterator is copy-constructible and assignable // * The value type of InputIterator supports operator - // * The result type of operator- is assignable to the value_type of InputIterator // * The result type of operator- is assignable to the value_type of OutputIterator // * order >= 0 // returns: The iterator following the output sequence template<typename InputIterator, typename OutputIterator>

OutputIterator nth_forward_difference(int order,
                                      InputIterator first, InputIterator last,
                                      OutputIterator dest)

{

 // special case: If order == 0, just copy input to output
 if (order == 0)
   return std::copy(first, last, dest);

 // second special case: If order == 1, just forward to the first-order function
 if (order == 1)
   return forward_difference(first, last, dest);

 // intermediate results are stored in a vector
 typedef typename std::iterator_traits<InputIterator>::value_type value_type;
 std::vector<value_type> temp_storage;

 // fill the vector with the result of the first order forward difference
 forward_difference(first, last, std::back_inserter(temp_storage));

 // the next n-2 iterations work directly on the vector
 typename std::vector<value_type>::iterator begin = temp_storage.begin(),
                                            end = temp_storage.end();
 for (int i = 1; i < order-1; ++i)
   end = forward_difference(begin, end, begin);

 // the final iteration writes directly to the output iterator
 return forward_difference(begin, end, dest);

}

// example usage code

include <iostream>

int main() {

 double array[10] = { 90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0 };

 // this stores the results in the vector dest
 std::vector<double> dest;
 nth_forward_difference(1, array, array+10, std::back_inserter(dest));

 // output dest
 std::copy(dest.begin(), dest.end(), std::ostream_iterator<double>(std::cout, " "));
 std::cout << std::endl;

 // however, the results can also be output as they are calculated
 nth_forward_difference(2, array, array+10, std::ostream_iterator<double>(std::cout, " "));
 std::cout << std::endl;

 nth_forward_difference(9, array, array+10, std::ostream_iterator<double>(std::cout, " "));
 std::cout << std::endl;

 nth_forward_difference(10, array, array+10, std::ostream_iterator<double>(std::cout, " "));
 std::cout << std::endl;

 nth_forward_difference(0, array, array+10, std::ostream_iterator<double>(std::cout, " "));
 std::cout << std::endl;

 // finally, the results can also be written into the original array
 // (which of course destroys the original content)
 double* end = nth_forward_difference(3, array, array+10, array);

 for (double* p = array; p < end; ++p)
   std::cout << *p << " ";
 std::cout << std::endl;

 return 0;

}</lang>

Output:

 -43 11 -29 -7 10 23 -50 50 18 
 54 -40 22 17 13 -73 100 -32 
 -2921 
 
 90 47 58 29 22 32 55 5 55 73 
 -94 62 -5 -4 -86 173 -132

Note the empty line indicating the empty sequence for order 10.

Using Standard Template Library

include <iostream>
include <numeric>

// Calculate the Forward Difference of a series if integers showing each order // // Nigel Galloway. August 20th., 2012 // int main() {

   int x[] = {NULL,-43,11,-29,-7,10,23,-50,50,18};
   const int N = sizeof(x) / sizeof(int) - 1;
   for (int ord = 0; ord < N - 1; ord++) {
       std::adjacent_difference(x+1, x + N + 1 - ord, x);
       for (int i = 1; i < N - ord; i++) std::cout << x[i] << ' ';
       std::cout << std::endl;
   }
   return 0;

} </lang>

Output:

54 -40 22 17 13 -73 100 -32
-94 62 -5 -4 -86 173 -132
156 -67 1 -82 259 -305
-223 68 -83 341 -564
291 -151 424 -905
-442 575 -1329
1017 -1904
-2921

Usually one will not want the intermediate results, in which case the following is sufficient: <lang cpp>

include <iostream>
include <numeric>

// Calculate the Forward Difference of a series if integers // // Nigel Galloway. August 20th., 2012 // int main() {

   int x[] = {NULL,-43,11,-29,-7,10,23,-50,50,18};
   const int N = sizeof(x) / sizeof(int) - 1;
   for (int ord = 0; ord < N - 1; ord++) std::adjacent_difference(x+1, x + N + 1 - ord, x);
   std::cout << x[1] << std::endl;
   return 0;

} </lang>

Output:

-2921

Using Pascal's Triangle

include <iostream>
include <algorithm>

// Calculate the Forward Difference of a series if integers using Pascal's Triangle // For this example the 9th line of Pascal's Triangle is stored in P. // // Nigel Galloway. August 20th., 2012 // int main() {

   const int P[] = {1,-8,28,-56,70,-56,28,-8,1};
   int x[] = {-43,11,-29,-7,10,23,-50,50,18};
   std::transform(x, x + sizeof(x) / sizeof(int), P, x, std::multiplies<int>());
   std::cout << std::accumulate(x, x + sizeof(x) / sizeof(int), 0) << std::endl;
   return 0;

} </lang>

Output:

-2921

Clojure

<lang lisp>(defn fwd-diff [nums order]

 (nth (iterate #(map - (next %) %) nums) order))</lang>

CoffeeScript

<lang coffeescript> forward_difference = (arr, n) ->

 # Find the n-th order forward difference for arr using
 # a straightforward recursive algorithm.
 # Assume arr is integers and n <= arr.length.
 return arr if n == 0
 arr = forward_difference(arr, n-1)
 (arr[i+1] - arr[i] for i in [0...arr.length - 1])

arr = [-1, 0, 1, 8, 27, 64, 125, 216] for n in [0..arr.length]

 console.log n, forward_difference arr, n

</lang>

Output:

> coffee forward_difference.coffee 
0 [ -1, 0, 1, 8, 27, 64, 125, 216 ]
1 [ 1, 1, 7, 19, 37, 61, 91 ]
2 [ 0, 6, 12, 18, 24, 30 ]
3 [ 6, 6, 6, 6, 6 ]
4 [ 0, 0, 0, 0 ]
5 [ 0, 0, 0 ]
6 [ 0, 0 ]
7 [ 0 ]
8 []

Common Lisp

<lang lisp>(defun forward-difference (list)

 (mapcar #'- (rest list) list))

(defun nth-forward-difference (list n)

 (setf list (copy-list list))
 (loop repeat n do (map-into list #'- (rest list) list))
 (subseq list 0 (- (length list) n)))</lang>

D

Basic Version

<lang d>T[] forwardDifference(T)(in T[] data, in int level) pure nothrow in {

   assert(level >= 0 && level < data.length);

} body {

   auto result = data.dup;
   foreach (immutable i; 0 .. level)
       foreach (immutable j, ref el; result[0 .. $ - i - 1])
           el = result[j + 1] - el;
   result.length -= level;
   return result;

}

void main() {

   import std.stdio;

   const data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
   foreach (immutable level; 0 .. data.length)
       forwardDifference(data, level).writeln;

}</lang>

Output:

[90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5]
[-43.5, 11, -29, -7, 10, 23, -50, 50, 18.5]
[54.5, -40, 22, 17, 13, -73, 100, -31.5]
[-94.5, 62, -5, -4, -86, 173, -131.5]
[156.5, -67, 1, -82, 259, -304.5]
[-223.5, 68, -83, 341, -563.5]
[291.5, -151, 424, -904.5]
[-442.5, 575, -1328.5]
[1017.5, -1903.5]
[-2921]

Alternative Version

Same output. <lang d>import std.stdio, std.algorithm, std.range, std.array;

auto forwardDifference(Range)(Range d, in int level) pure {

   foreach (immutable _; 0 .. level)
       d = d.zip(d.dropOne).map!(a => a[0] - a[1]).array;
   return d;

}

void main() {

   const data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
   foreach (immutable level; 0 .. data.length)
       forwardDifference(data, level).writeln;

}</lang>

Using Vector Operations

forwardDifference mutates the array in-place (same output): <lang d>import std.stdio;

T[] forwardDifference(T)(T[] s, in int n) pure nothrow @nogc {

   foreach (immutable i; 0 .. n)
       s[0 .. $ - i - 1] = s[1 .. $ - i] - s[0 .. $ - i - 1];
   return s[0 .. $ - n];

} void main() {

   immutable A = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
   foreach (immutable level; 0 .. A.length)
       forwardDifference(A.dup, level).writeln;

}</lang>

Short Functional Version

Same output: <lang d>void main() {

 import std.stdio, std.range;

 auto D = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
 writefln("%(%s\n%)",
   recurrence!q{ (a[n - 1][0 .. $ - 1] =
                  a[n - 1][1 .. $] -
                  a[n - 1][0 .. $ - 1])[0 .. $] }(D)
   .take(D.length));

}</lang>

Dart

<lang dart>List forwardDifference(List _list) {

 for (int i = _list.length - 1; i > 0; i--) {
   _list[i] = _list[i] - _list[i - 1];
 }

 _list.removeRange(0, 1);
 return _list;

}

void mainAlgorithms() {

 List _intList = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];

 for (int i = _intList.length - 1; i >= 0; i--) {
   List _list = forwardDifference(_intList);
   print(_list);
 }

}</lang>

Output:

Restarted application in 1,143ms.
flutter: [-43, 11, -29, -7, 10, 23, -50, 50, 18]
flutter: [54, -40, 22, 17, 13, -73, 100, -32]
flutter: [-94, 62, -5, -4, -86, 173, -132]
flutter: [156, -67, 1, -82, 259, -305]
flutter: [-223, 68, -83, 341, -564]
flutter: [291, -151, 424, -905]
flutter: [-442, 575, -1329]
flutter: [1017, -1904]
flutter: [-2921]
flutter: []

E

<lang e>pragma.enable("accumulator") /** Single step. */ def forwardDifference(seq :List) {

   return accum [] for i in 0..(seq.size() - 2) {
       _.with(seq[i + 1] - seq[i])
   }

}

/** Iterative implementation of the goal. */ def nthForwardDifference1(var seq :List, n :(int >= 0)) {

   for _ in 1..n { seq := forwardDifference(seq) }
   return seq

}

/** Imperative implementation of the goal. */ def nthForwardDifference2(seq :List, n :(int >= 0)) {

 def buf := seq.diverge()
 def finalSize := seq.size() - n
 for lim in (finalSize..!seq.size()).descending() {
   for i in 0..!lim {
     buf[i] := buf[i + 1] - buf[i]
   }
 }
 return buf.run(0, finalSize)

}

? def sampleData := [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] > for n in 0..10 { > def r1 := nthForwardDifference1(sampleData, n) > require(r1 == nthForwardDifference2(sampleData, n)) > println(r1) > }</lang>

EchoLisp

Using the built-in function iterate which, given a function f and n, returns the function f°f°f....°f . <lang lisp> (define (Δ-1 list) (for/list ([x (cdr list)] [y list]) (- x y)))

(define (Δ-n n) (iterate Δ-1 n))

((Δ-n 9) '(90 47 58 29 22 32 55 5 55 73))

   →  (-2921)

</lang>

Elixir

<lang Elixir>defmodule Diff do

 def forward(list,i\\1) do
   forward(list,[],i)
 end
 
 def forward([_],diffs,1), do: IO.inspect diffs
 def forward([_],diffs,i), do: forward(diffs,[],i-1)
 def forward([val1,val2|vals],diffs,i) do
   forward([val2|vals],diffs++[val2-val1],i)
 end

end

Enum.each(1..9, fn i ->

 Diff.forward([90, 47, 58, 29, 22, 32, 55, 5, 55, 73],i)

end)</lang>

Output:

[-43, 11, -29, -7, 10, 23, -50, 50, 18]
[54, -40, 22, 17, 13, -73, 100, -32]
[-94, 62, -5, -4, -86, 173, -132]
[156, -67, 1, -82, 259, -305]
[-223, 68, -83, 341, -564]
[291, -151, 424, -905]
[-442, 575, -1329]
[1017, -1904]
[-2921]

Erlang

<lang erlang>-module(forward_difference). -export([difference/1, difference/2]).

-export([task/0]). -define(TEST_DATA,[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]).

difference([X|Xs]) ->

   {Result,_} = lists:mapfoldl(fun (N_2,N_1) -> {N_2 - N_1, N_2} end, X, Xs),
   Result.

difference([],_) -> []; difference(List,0) -> List; difference(List,Order) -> difference(difference(List),Order-1).

task() ->

   io:format("Initial: ~p~n",[?TEST_DATA]),
   [io:format("~3b: ~p~n",[N,difference(?TEST_DATA,N)]) || N <- lists:seq(0,length(?TEST_DATA))],
   ok.</lang>

Output:

80> forward_difference:task().
Initial: [90,47,58,29,22,32,55,5,55,73]
  0: [90,47,58,29,22,32,55,5,55,73]
  1: [-43,11,-29,-7,10,23,-50,50,18]
  2: [54,-40,22,17,13,-73,100,-32]
  3: [-94,62,-5,-4,-86,173,-132]
  4: [156,-67,1,-82,259,-305]
  5: [-223,68,-83,341,-564]
  6: [291,-151,424,-905]
  7: [-442,575,-1329]
  8: [1017,-1904]
  9: [-2921]
 10: []
ok

F#

Straightforward recursive solution <lang fsharp>let rec ForwardDifference input n =

   match n with
   | _ when input = [] || n < 0 -> []      // If there's no more input, just return an empty list
   | 0 -> input                            // If n is zero, we're done - return the input
   | _ -> ForwardDifference                // otherwise, recursively difference..
           (input.Tail                     // All but the first element
           |> Seq.zip input                // tupled with itself
           |> Seq.map (fun (a, b) -> b-a)  // Subtract the i'th element from the (i+1)'th
           |> Seq.toList) (n-1)            // Make into a list and do an n-1 difference on it</lang>

Factor

<lang factor>USING: kernel math math.vectors sequences ; IN: rosetacode

1-order ( seq -- seq' )

   [ rest-slice ] keep v- ;

n-order ( seq n -- seq' )

   dup 0 <=
   [ drop ] [ [ 1-order ] times ] if ;

</lang>

 ( scratchpad ) { 90.5 47 58 29 22 32 55 5 55 73.5 } 4 n-order .
 { 156.5 -67 1 -82 259 -304.5 }

Forth

<lang forth>: forward-difference

 dup 0
 ?do
    swap rot over i 1+ - 0
    ?do dup i cells + dup cell+ @ over @ - swap ! loop
    swap rot
 loop -

create a

 90 , 47 , 58 , 29 , 22 , 32 , 55 , 5 , 55 , 73 ,

test a 10 9 forward-difference bounds ?do i ? loop ;

test</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>MODULE DIFFERENCE

 IMPLICIT NONE

 CONTAINS

 SUBROUTINE Fdiff(a, n)
   INTEGER, INTENT(IN) :: a(:), n
   INTEGER :: b(SIZE(a))  
   INTEGER :: i, j, arraysize
 
   b = a
   arraysize = SIZE(b)
   DO i = arraysize-1, arraysize-n, -1
     DO j = 1, i
       b(j) = b(j+1) - b(j)
     END DO
   END DO
   WRITE (*,*) b(1:arraysize-n)
 END SUBROUTINE Fdiff

END MODULE DIFFERENCE</lang>

<lang fortran>PROGRAM TEST

 USE DIFFERENCE
 IMPLICIT NONE

 INTEGER :: array(10) = (/ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 /)
 INTEGER :: i
 
 DO i = 1, 9
   CALL Fdiff(array, i)
 END DO

 END PROGRAM TEST</lang>

Output:

          -43          11         -29          -7          10          23         -50          50          18
           54         -40          22          17          13         -73         100         -32
          -94          62          -5          -4         -86         173        -132
          156         -67           1         -82         259        -305
         -223          68         -83         341        -564
          291        -151         424        -905
         -442         575       -1329
         1017       -1904
        -2921

Go

<lang go>package main

import "fmt"

func main() {

   a := []int{90, 47, 58, 29, 22, 32, 55, 5, 55, 73}
   fmt.Println(a)
   fmt.Println(fd(a, 9))

}

func fd(a []int, ord int) []int {

   for i := 0; i < ord; i++ {
       for j := 0; j < len(a)-i-1; j++ {
           a[j] = a[j+1] - a[j]
       }
   }
   return a[:len(a)-ord]

}</lang>

Output:

[90 47 58 29 22 32 55 5 55 73]
[-2921]

Haskell

<lang haskell>forwardDifference :: Num a => [a] -> [a] forwardDifference = tail >>= zipWith (-)

nthForwardDifference :: Num a => [a] -> Int -> [a] nthForwardDifference = (!!) . iterate forwardDifference

main :: IO () main =

 mapM_ print $
 take 10 (iterate forwardDifference [90, 47, 58, 29, 22, 32, 55, 5, 55, 73])</lang>

Output:

[90,47,58,29,22,32,55,5,55,73]
[-43,11,-29,-7,10,23,-50,50,18]
[54,-40,22,17,13,-73,100,-32]
[-94,62,-5,-4,-86,173,-132]
[156,-67,1,-82,259,-305]
[-223,68,-83,341,-564]
[291,-151,424,-905]
[-442,575,-1329]
[1017,-1904]
[-2921]

HicEst

<lang hicest>REAL :: n=10, list(n)

list = ( 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 ) WRITE(Format='i1, (i6)') 0, list

DO i = 1, n-1

 ALIAS(list,1,  diff,n-i) ! rename list(1 ... n-i) with diff
 diff = list($+1) - diff  ! $ is the running left hand array index
 WRITE(Format='i1, (i6)') i, diff

ENDDO

END</lang>

Output:

0    90    47    58    29    22    32    55     5    55    73
1   -43    11   -29    -7    10    23   -50    50    18
2    54   -40    22    17    13   -73   100   -32
3   -94    62    -5    -4   -86   173  -132
4   156   -67     1   -82   259  -305
5  -223    68   -83   341  -564
6   291  -151   424  -905
7  -442   575 -1329
8  1017 -1904
9 -2921

Icon and Unicon

<lang icon>procedure main(A) # Compute all forward difference orders for argument list

   every order := 1 to (*A-1) do showList(order, fdiff(A, order))

end

procedure fdiff(A, order)

   every 1 to order do {
       every put(B := [], A[i := 2 to *A] - A[i-1])
       A := B
       }
  return A

end

procedure showList(order, L)

   writes(right(order,3),": ")
   every writes(!L," ")
   write()

end</lang>

A sample run:

->fdiff 3 1 4 1 5 9 2 6 3
  1: -2 3 -3 4 4 -7 4 -3 
  2: 5 -6 7 0 -11 11 -7 
  3: -11 13 -7 -11 22 -18 
  4: 24 -20 -4 33 -40 
  5: -44 16 37 -73 
  6: 60 21 -110 
  7: -39 -131 
  8: -92 
->

IDL

Standard IDL library function TS_diff(X,k,[/double]):

<lang idl>print,(x = randomu(seed,8)*100)

    15.1473      58.0953      82.7465      16.8637      97.7182      59.7856      17.7699      74.9154

print,ts_diff(x,1)

   -42.9479     -24.6513      65.8828     -80.8545      37.9326      42.0157     -57.1455     0.000000

print,ts_diff(x,2)

   -18.2967     -90.5341      146.737     -118.787     -4.08316      99.1613     0.000000     0.000000

print,ts_diff(x,3)

    72.2374     -237.271      265.524     -114.704     -103.244     0.000000     0.000000     0.000000</lang>

J

Of the many ways to code this in J, a particularly concise solution is: <lang j>fd=: 2&(-~/\)</lang>

Alternatively, to reduce the number of J primitives, use: <lang j>fd=: }. - }: ^:</lang>

(which is also elegant, because the open-ended power conjunction reads like "to the power of anything").

For example: <lang j> list=: 90 47 58 29 22 32 55 5 55 73 NB. Some numbers

  1 fd list

_43 11 _29 _7 10 23 _50 50 18

  2 fd list

54 _40 22 17 13 _73 100 _32</lang>

J is array oriented, so you can even ask for more than one forward difference at a time (i.e. N can be a list, instead of a single number): <lang j> 1 2 3 fd list NB. First, second, and third forward differences (simultaneously) 43 _11 29 7 _10 _23 50 _50 _18 54 _40 22 17 13 _73 100 _32 0 94 _62 5 4 86 _173 132 0 0

  a: fd list                             NB.  All forward differences
 90    47   58   29  22   32  55   5  55 73
 43   _11   29    7 _10  _23  50 _50 _18  0
 54   _40   22   17  13  _73 100 _32   0  0
 94   _62    5    4  86 _173 132   0   0  0
156   _67    1  _82 259 _305   0   0   0  0
223   _68   83 _341 564    0   0   0   0  0
291  _151  424 _905   0    0   0   0   0  0
442  _575 1329    0   0    0   0   0   0  0

1017 _1904 0 0 0 0 0 0 0 0 2921 0 0 0 0 0 0 0 0 0

  0     0    0    0   0    0   0   0   0  0</lang>

Java

Works with: Java version 1.5+

<lang java>import java.util.Arrays; public class FD {

   public static void main(String args[]) {
       double[] a = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73};
       System.out.println(Arrays.toString(dif(a, 1)));
       System.out.println(Arrays.toString(dif(a, 2)));
       System.out.println(Arrays.toString(dif(a, 9)));
       System.out.println(Arrays.toString(dif(a, 10)));      //let's test
       System.out.println(Arrays.toString(dif(a, 11)));
       System.out.println(Arrays.toString(dif(a, -1)));
       System.out.println(Arrays.toString(dif(a, 0)));
   }

   public static double[] dif(double[] a, int n) {
       if (n < 0)
           return null; // if the programmer was dumb

       for (int i = 0; i < n && a.length > 0; i++) {
           double[] b = new double[a.length - 1];
           for (int j = 0; j < b.length; j++){
               b[j] = a[j+1] - a[j];
           }
           a = b; //"recurse"
       }
       return a;
   }

}</lang>

Output:

[-43.0, 11.0, -29.0, -7.0, 10.0, 23.0, -50.0, 50.0, 18.0]
[54.0, -40.0, 22.0, 17.0, 13.0, -73.0, 100.0, -32.0]
[-2921.0]
[]
[]
null
[90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0]

JavaScript

ES6

<lang JavaScript>(() => {

   'use strict';

   // forwardDifference :: Num a => [a] -> [a]
   const forwardDifference = xs =>
       zipWith(subtract)(xs)(tail(xs));

   // nthForwardDifference :: Num a => Int -> [a] -> [a]
   const nthForwardDifference = xs =>
       index(iterate(forwardDifference)(xs)).Just;

   //----------------------- TEST ------------------------
   // main :: IO ()
   const main = () =>
       unlines(
           take(10)(
               iterate(forwardDifference)(
                   [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
               )
           ).map((x, i) => justifyRight(2)('x')(i) + (
               ' -> '
           ) + JSON.stringify(x))
       );

   //----------------- GENERIC FUNCTIONS -----------------

   // Just :: a -> Maybe a
   const Just = x => ({
       type: 'Maybe',
       Nothing: false,
       Just: x
   });

   // Nothing :: Maybe a
   const Nothing = () => ({
       type: 'Maybe',
       Nothing: true,
   });

   // Tuple (,) :: a -> b -> (a, b)
   const Tuple = a =>
       b => ({
           type: 'Tuple',
           '0': a,
           '1': b,
           length: 2
       });

   // index (!!) :: [a] -> Int -> Maybe a
   // index (!!) :: Generator (Int, a) -> Int -> Maybe a
   // index (!!) :: String -> Int -> Maybe Char
   const index = xs => i => {
       const s = xs.constructor.constructor.name;
       return 'GeneratorFunction' !== s ? (() => {
           const v = xs[i];
           return undefined !== v ? Just(v) : Nothing();
       })() : Just(take(i)(xs), xs.next().value);
   };

   // iterate :: (a -> a) -> a -> Gen [a]
   const iterate = f =>
       function*(x) {
           let v = x;
           while (true) {
               yield(v);
               v = f(v);
           }
       };

   // justifyRight :: Int -> Char -> String -> String
   const justifyRight = n =>
       // The string s, preceded by enough padding (with
       // the character c) to reach the string length n.
       c => s => n > s.length ? (
           s.padStart(n, c)
       ) : s;

   // length :: [a] -> Int
   const length = xs =>
       // Returns Infinity over objects without finite
       // length. This enables zip and zipWith to choose
       // the shorter argument when one is non-finite,
       // like cycle, repeat etc
       (Array.isArray(xs) || 'string' === typeof xs) ? (
           xs.length
       ) : Infinity;

   // map :: (a -> b) -> [a] -> [b]
   const map = f =>
       // The list obtained by applying f
       // to each element of xs.
       // (The image of xs under f).
       xs => (
           Array.isArray(xs) ? (
               xs
           ) : xs.split()
       ).map(f);

   // subtract :: Num -> Num -> Num
   const subtract = x =>
       y => y - x;

   // tail :: [a] -> [a]
   const tail = xs =>
       // A new list consisting of all
       // items of xs except the first.
       0 < xs.length ? xs.slice(1) : [];

   // take :: Int -> [a] -> [a]
   // take :: Int -> String -> String
   const take = n =>
       // The first n elements of a list,
       // string of characters, or stream.
       xs => 'GeneratorFunction' !== xs
       .constructor.constructor.name ? (
           xs.slice(0, n)
       ) : [].concat.apply([], Array.from({
           length: n
       }, () => {
           const x = xs.next();
           return x.done ? [] : [x.value];
       }));

   // unlines :: [String] -> String
   const unlines = xs =>
       // A single string formed by the intercalation
       // of a list of strings with the newline character.
       xs.join('\n');

   // zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
   const zipWith = f => xs => ys => {
       const
           lng = Math.min(length(xs), length(ys)),
           [as, bs] = [xs, ys].map(take(lng));
       return Array.from({
           length: lng
       }, (_, i) => f(as[i])(
           bs[i]
       ));
   };

   // MAIN ---
   return main();

})();</lang>

Output:

0 -> [90,47,58,29,22,32,55,5,55,73]
1 -> [-43,11,-29,-7,10,23,-50,50,18]
2 -> [54,-40,22,17,13,-73,100,-32]
3 -> [-94,62,-5,-4,-86,173,-132]
4 -> [156,-67,1,-82,259,-305]
5 -> [-223,68,-83,341,-564]
6 -> [291,-151,424,-905]
7 -> [-442,575,-1329]
8 -> [1017,-1904]
9 -> [-2921]

jq

Works with: jq version 1.4

<lang jq># If n is a non-negative number and if input is

a (possibly empty) array of numbers,
emit an array, even if the input list is too short:

def ndiff(n):

 if n==0 then .
 elif n == 1 then . as $in | [range(1;length) | $in[.] - $in[.-1]]
 else ndiff(1) | ndiff(n-1)
 end;</lang>

Example: <lang jq>def s: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];

range(0;12) as $i | (s|ndiff($i))</lang>

Output:

<lang sh>$ jq -c -n -f forward-difference.jq [90,47,58,29,22,32,55,5,55,73] [-43,11,-29,-7,10,23,-50,50,18] [54,-40,22,17,13,-73,100,-32] [-94,62,-5,-4,-86,173,-132] [156,-67,1,-82,259,-305] [-223,68,-83,341,-564] [291,-151,424,-905] [-442,575,-1329] [1017,-1904] [-2921] [] []</lang>

Julia

Works with: Julia version 0.6

Using the built-in diff function, which returns the 1st forward difference:

<lang julia>ndiff(A::Array, n::Integer) = n < 1 ? A : diff(ndiff(A, n-1))

s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] println.(collect(ndiff(s, i) for i in 0:9))</lang>

Output:

[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
[-43, 11, -29, -7, 10, 23, -50, 50, 18]
[54, -40, 22, 17, 13, -73, 100, -32]
[-94, 62, -5, -4, -86, 173, -132]
[156, -67, 1, -82, 259, -305]
[-223, 68, -83, 341, -564]
[291, -151, 424, -905]
[-442, 575, -1329]
[1017, -1904]
[-2921]

K4

To compute the nth forward difference, call as: <lang k4>n fd/</lang>

In order to obtain all intermediate results, call as: <lang k4>n fd\</lang>

Examples:

  fd 1 2 4 7 11 16
1 2 3 4 5
  2 fd/1 2 4 7 11 16
1 1 1 1
  3 fd\1 2 4 7 11 16
(1 2 4 7 11 16;1 2 3 4 5;1 1 1 1;0 0 0)

Kotlin

<lang scala>// version 1.1.2

fun forwardDifference(ia: IntArray, order: Int): IntArray {

   if (order < 0) throw IllegalArgumentException("Order must be non-negative")
   if (order == 0) return ia
   val size = ia.size
   if (size == 0) return ia  // same empty array
   if (order >= size) return intArrayOf()  // new empty array
   var old = ia
   var new = old
   var count = order
   while (count-- >= 1) {
      new = IntArray(old.size - 1)
      for (i in 0 until new.size) new[i] = old[i + 1] - old[i]
      old = new
   }
   return new

}

fun printArray(ia: IntArray) {

   print("[")
   for (i in 0 until ia.size) {
       print("%5d".format(ia[i]))
       if (i < ia .size - 1) print(", ")
   }
   println("]")

}

fun main(args: Array<String>) {

   val ia = intArrayOf(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)
   for (order in 0..ia.size) {
       val fd = forwardDifference(ia, order)
       print("%2d".format(order) + ":  ")
       printArray(fd)
   }

}</lang>

Output:

 0:  [   90,    47,    58,    29,    22,    32,    55,     5,    55,    73]
 1:  [  -43,    11,   -29,    -7,    10,    23,   -50,    50,    18]
 2:  [   54,   -40,    22,    17,    13,   -73,   100,   -32]
 3:  [  -94,    62,    -5,    -4,   -86,   173,  -132]
 4:  [  156,   -67,     1,   -82,   259,  -305]
 5:  [ -223,    68,   -83,   341,  -564]
 6:  [  291,  -151,   424,  -905]
 7:  [ -442,   575, -1329]
 8:  [ 1017, -1904]
 9:  [-2921]
10:  []

Lambdatalk

<lang scheme> {def fdiff

{lambda {:l}
 {A.new
  {S.map {{lambda {:l :i} {- {A.get {+ :i 1} :l} {A.get :i :l}} } :l}
         {S.serie 0 {- {A.length :l} 2}}}}}}

-> fdiff

{def disp

 {lambda {:l}
  {if {A.empty? {A.rest :l}}
   then else {let { {:l {fdiff :l}} } {br}:l {disp :l}}}}}

-> disp

{def L {A.new 90 47 58 29 22 32 55 5 55 73}} -> L

{disp {L}} -> [-43,11,-29,-7,10,23,-50,50,18] [54,-40,22,17,13,-73,100,-32] [-94,62,-5,-4,-86,173,-132] [156,-67,1,-82,259,-305] [-223,68,-83,341,-564] [291,-151,424,-905] [-442,575,-1329] [1017,-1904] [-2921] </lang>

Lasso

<lang lasso>#!/usr/bin/lasso9

define forwardDiff(values, order::integer=1) => {

 !#order ? return #values->asArray
 local(result = array)
 iterate(#values) => {
   loop_count < #values->size ?
     #result->insert(#values->get(loop_count+1) - #values->get(loop_count))
 }
 #order > 1 ? #result = forwardDiff(#result, #order-1)
 return #result

}

local(data = (:90, 47, 58, 29, 22, 32, 55, 5, 55, 73)) with x in generateSeries(0, #data->size-1) do stdoutnl(#x + ': ' + forwardDiff(#data, #x))</lang>

Output:

0: array(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)
1: array(-43, 11, -29, -7, 10, 23, -50, 50, 18)
2: array(54, -40, 22, 17, 13, -73, 100, -32)
3: array(-94, 62, -5, -4, -86, 173, -132)
4: array(156, -67, 1, -82, 259, -305)
5: array(-223, 68, -83, 341, -564)
6: array(291, -151, 424, -905)
7: array(-442, 575, -1329)
8: array(1017, -1904)
9: array(-2921)

Logo

<lang logo>to fwd.diff :l

 if empty? :l [output []]
 if empty? bf :l [output []]
 output fput (first bf :l)-(first :l) fwd.diff bf :l

end to nth.fwd.diff :n :l

 if :n = 0 [output :l]
 output nth.fwd.diff :n-1 fwd.diff :l

end

show nth.fwd.diff 9 [90 47 58 29 22 32 55 5 55 73] [-2921]</lang>

Lua

<lang lua>function dif(a, b, ...)

 if(b) then return b-a, dif(b, ...) end

end function dift(t) return {dif(unpack(t))} end print(unpack(dift{1,3,6,10,15}))</lang>

M2000 Interpreter

Function Diff(a()) get an array by value (a shallow copy) <lang M2000 Interpreter> Form 80, 40 Module Forward_difference {

     Print $(0,6)  ' 6 characters column
     Dim a(), b()
     a()=(90,47,58,29,22,32,55,5,55,73)
     Function Diff(a()) {
           for i=0 to len(a())-2: a(i)=a(i+1)-a(i):Next i
           Dim a(len(a())-1) ' redim one less
           =a()
     }
     Print "Original:","",a()
     b()=a()    ' copy a() to b()
     k=1
     While len(b())>1 {
           b()=Diff(b())   ' copy returned array to b()
           Print "Difference ";k;":",b()
           k++
     }

} Forward_difference

</lang>

Output:

Original:             90    47    58    29    22    32    55    5    55    73 
Difference 1:        -43    11   -29    -7    10    23   -50   50    18 
Difference 2:         54   -40    22    17    13   -73   100  -32 
Difference 3:        -94    62    -5    -4   -86   173  -132 
Difference 4:        156   -67     1   -82   259  -305 
Difference 5:       -223    68   -83   341  -564 
Difference 6:        291  -151   424  -905 
Difference 7:       -442   575 -1329 
Difference 8:       1017 -1904 
Difference 9:      -2921

Mathematica / Wolfram Language

Built-in function: <lang Mathematica>i={3,5,12,1,6,19,6,2,4,9}; Differences[i]</lang>

gives back:

<lang Mathematica>{2, 7, -11, 5, 13, -13, -4, 2, 5}</lang> The n^th difference can be done as follows: <lang Mathematica>i={3,5,12,1,6,19,6,2,4,9}; Differences[i,n]</lang>

MATLAB / Octave

This is a built-in function. X is the list of numbers, n is the order of the forward difference. <lang MATLAB>Y = diff(X,n);</lang>

Output:

1st order forward difference.

diff([1 2 3 4 5])

ans =

     1     1     1     1

Maxima

<lang maxima>ldiff(u, n) := block([m: length(u)], for j thru n do u: makelist(u[i + 1] - u[i], i, 1, m - j), u);</lang>

NetRexx

<lang NetRexx>/* NetRexx*************************************************************

Forward differences
18.08.2012 Walter Pachl derived from Rexx
- - - - /

 Loop n=-1 To 11
   differences('90 47 58 29 22 32 55 5 55 73',n)
   End

 method differences(a,n) public static
 --arr=Rexx[11]                       -- array must be declared (zero based)
   arr=                             -- alternative: indexed string
   m=a.words
   Select
     When n<0 Then Say 'n is negative:' n '<' 0
     When n>m Then Say 'n is too large:' n '>' m
     Otherwise Do
       Loop i=1 To m
         arr[i]=a.word(i)
         End
       Loop i = 1 to n
         t = arr[i]
         Loop j = i+1 to m
           u = arr[j]
           arr[j] = arr[j]-t
           t = u
           end
         end
       ol=
       Loop i=n+1 to m
         ol=ol arr[i]
         End
       Say n ol
       End
     End</lang>

Output is the same as for Rexx

Nial

Define forward difference for order 1 <lang nial>fd is - [rest, front]</lang>

Output:

forward difference of 4th order

Nim

<lang nim>proc dif(s): seq[int] =

 result = newSeq[int](s.len-1)
 for i, x in s[1..s.high]:
   result[i] = x - s[i]

proc difn(s, n): seq[int] =

 if n > 0: difn(dif(s), n-1)
 else: s

const s = @[90, 47, 58, 29, 22, 32, 55, 5, 55, 73] echo difn(s, 0) echo difn(s, 1) echo difn(s, 2)</lang>

Output:

@[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
@[-43, 11, -29, -7, 10, 23, -50, 50, 18]
@[54, -40, 22, 17, 13, -73, 100, -32]

Objeck

Translation of: Java

<lang objeck> bundle Default {

 class Test {
   function : Main(args : String[]) ~ Nil {
     a := [90.0, 47.0, 58.0, 29.0, 22.0, 32.0, 55.0, 5.0, 55.0, 73.0];
     Print(Diff(a, 1));
     Print(Diff(a, 2));
     Print(Diff(a, 9));
   }

   function : Print(a : Float[]) ~ Nil {
     if(a <> Nil) {
       '['->Print();
       each(i : a) {
         a[i]->Print(); ','->Print();
       };
       ']'->PrintLine();
     };
   }

   function : Diff(a : Float[], n : Int) ~ Float[] {
     if (n < 0) {
       return Nil;
      };

     for(i := 0; i < n & a->Size() > 0; i += 1;) {
       b := Float->New[a->Size() - 1];
       for(j := 0; j < b->Size(); j += 1;){
         b[j] := a[j+1] - a[j];
       };
       a := b;
     };

     return a;
   }
 }

} </lang>

OCaml

<lang ocaml>let rec forward_difference = function

   a :: (b :: _ as xs) ->
     b - a :: forward_difference xs
 | _ ->
     []

let rec nth_forward_difference n xs =

 if n = 0 then
   xs
 else
   nth_forward_difference (pred n) (forward_difference xs)</lang>

Output:

# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];;
- : int list = [-2921]

Oforth

<lang Oforth>: forwardDiff(l) l right(l size 1 -) l zipWith(#-) ;

forwardDiffN(n, l) l #[ forwardDiff dup println ] times(n) ;</lang>

Output:

10 [ 90, 47, 58, 29, 22, 32, 55, 5, 55, 73] forwardDiffN
[-43, 11, -29, -7, 10, 23, -50, 50, 18]
[54, -40, 22, 17, 13, -73, 100, -32]
[-94, 62, -5, -4, -86, 173, -132]
[156, -67, 1, -82, 259, -305]
[-223, 68, -83, 341, -564]
[291, -151, 424, -905]
[-442, 575, -1329]
[1017, -1904]
[-2921]
[]

PARI/GP

<lang parigp>fd(v)=vector(#v-1,i,v[i+1]-v[i]);</lang>

Pascal

<lang pascal>Program ForwardDifferenceDemo(output);

procedure fowardDifference(list: array of integer);

 var
   b: array of integer;
   i, newlength: integer;
 begin
   newlength := length(list) - 1;
   if newlength > 0 then
   begin
     setlength(b, newlength);
     for i := low(b) to high(b) do
     begin
       b[i] := list[i+1] - list[i];
       write (b[i]:6);
     end;
     writeln;
     fowardDifference(b);
   end;
 end;

var

 a: array [1..10] of integer = (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);

begin

 fowardDifference(a);

end.</lang>

Output:

:> ./ForwardDifference
   -43    11   -29    -7    10    23   -50    50    18
    54   -40    22    17    13   -73   100   -32
   -94    62    -5    -4   -86   173  -132
   156   -67     1   -82   259  -305
  -223    68   -83   341  -564
   291  -151   424  -905
  -442   575 -1329
  1017 -1904
 -2921

Perl

<lang perl>sub dif {

 my @s = @_;
 map { $s[$_+1] - $s[$_] } 0 .. $#s-1

}

@a = qw<90 47 58 29 22 32 55 5 55 73>; while (@a) { printf('%6d', $_) for @a = dif @a; print "\n" }</lang>

Output:

   -43    11   -29    -7    10    23   -50    50    18
    54   -40    22    17    13   -73   100   -32
   -94    62    -5    -4   -86   173  -132
   156   -67     1   -82   259  -305
  -223    68   -83   341  -564
   291  -151   424  -905
  -442   575 -1329
  1017 -1904
 -2921

Phix

<lang Phix>function fwd_diff_n(sequence s, integer order)

   if order>=length(s) then ?9/0 end if
   for i=1 to order do
       for j=1 to length(s)-1 do
           s[j] = s[j+1]-s[j]
       end for
       s = s[1..-2]
   end for
   return s

end function

constant s = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73} for i=1 to 9 do

   ?fwd_diff_n(s,i)

end for</lang>

Output:

{-43,11,-29,-7,10,23,-50,50,18}
{54,-40,22,17,13,-73,100,-32}
{-94,62,-5,-4,-86,173,-132}
{156,-67,1,-82,259,-305}
{-223,68,-83,341,-564}
{291,-151,424,-905}
{-442,575,-1329}
{1017,-1904}
{-2921}

PHP

<lang php><?php

function forwardDiff($anArray, $times = 1) {

 if ($times <= 0) { return $anArray; }
 for ($accumilation = array(), $i = 1, $j = count($anArray); $i < $j; ++$i) { 
   $accumilation[] = $anArray[$i] - $anArray[$i - 1];
 }
 if ($times === 1) { return $accumilation; }
 return forwardDiff($accumilation, $times - 1);

}

class ForwardDiffExample extends PweExample {

 function _should_run_empty_array_for_single_elem() {
   $expected = array($this->rand()->int());
   $this->spec(forwardDiff($expected))->shouldEqual(array());
 }
 
 function _should_give_diff_of_two_elem_as_single_elem() {
   $twoNums = array($this->rand()->int(), $this->rand()->int());
   $expected = array($twoNums[1] - $twoNums[0]);
   $this->spec(forwardDiff($twoNums))->shouldEqual($expected);
 }
 
 function _should_compute_correct_forward_diff_for_longer_arrays() {
   $diffInput = array(10, 2, 9, 6, 5);
   $expected  = array(-8, 7, -3, -1);
   $this->spec(forwardDiff($diffInput))->shouldEqual($expected);
 }
 
 function _should_apply_more_than_once_if_specified() {
   $diffInput = array(4, 6, 9, 3, 4);
   $expectedAfter1 = array(2, 3, -6, 1);
   $expectedAfter2 = array(1, -9, 7);
   $this->spec(forwardDiff($diffInput, 1))->shouldEqual($expectedAfter1);
   $this->spec(forwardDiff($diffInput, 2))->shouldEqual($expectedAfter2);
 }
 
 function _should_return_array_unaltered_if_no_times() {
   $this->spec(forwardDiff($expected = array(1,2,3), 0))->shouldEqual($expected);
 }

}</lang>

PicoLisp

<lang PicoLisp>(de fdiff (Lst)

  (mapcar - (cdr Lst) Lst) )

(for (L (90 47 58 29 22 32 55 5 55 73) L (fdiff L))

  (println L) )</lang>

Output:

(90 47 58 29 22 32 55 5 55 73)
(-43 11 -29 -7 10 23 -50 50 18)
(54 -40 22 17 13 -73 100 -32)
(-94 62 -5 -4 -86 173 -132)
(156 -67 1 -82 259 -305)
(-223 68 -83 341 -564)
(291 -151 424 -905)
(-442 575 -1329)
(1017 -1904)
(-2921)

PL/I

<lang PL/I> /* Forward differences. */ /* 23 April 2010 */ differences: procedure options (main);

  declare a(10) fixed(10) static initial
     (7, 3, 9, 250, 300, 4, 68, 72, 154, 601);
  declare (i, j, m, n, t, u) fixed binary;

  m = hbound(a,1);
  get (n); if n > m then signal error;
  put skip edit (a) (F(7));
  do i = 1 to n;
     t = a(i);
     do j = i+1 to m;
        u = a(j);
        a(j) = a(j) - t;
        t = u;
     end;
     put skip edit (a) (F(7));
  end;
  put skip edit ((a(i) do i = n+1 to m)) (F(9));

end differences; </lang>

Pop11

<lang pop11>define forward_difference(l);

   lvars res = [], prev, el;
   if l = [] then
       return([]);
   endif;
   front(l) -> prev;
   for el in back(l) do
       cons(el - prev, res) -> res;
       el -> prev;
   endfor;
   rev(res);

enddefine;

define nth_difference(l, n);

   lvars res = l, i;
   for i from 1 to n do
       forward_difference(res) -> res;
   endfor;
   res;

enddefine;</lang>

PowerShell

$\Delta ^{n}[f](x)=\sum _{k=0}^{n}\left({\prod _{i=1}^{k}{\frac {n-k+i}{i}}}\right)(-1)^{n-k}f(x+k)$ <lang PowerShell>function Forward-Difference( [UInt64] $n, [Array] $f ) { $flen = $f.length if( $flen -gt [Math]::Max( 1, $n ) ) { 0..( $flen - $n - 1 ) | ForEach-Object { $l=0; for( $k = 0; $k -le $n; $k++ ) { $j = 1 for( $i = 1; $i -le $k; $i++ ) { $j *= ( ( $n - $k + $i ) / $i ) } $l += $j * ( 1 - 2 * ( ( $n - $k ) % 2 ) ) * $f[ $_ + $k ] } $l } } }

Forward-Difference 2 1,2,4,5</lang>

PureBasic

<lang PureBasic>Procedure forward_difference(List a())

 If ListSize(a()) <= 1
   ClearList(a()): ProcedureReturn
 EndIf
 Protected NewList b()
 CopyList(a(), b())
 LastElement(a()): DeleteElement(a())
 SelectElement(b(), 1)
 ForEach a()
   a() - b(): NextElement(b())
 Next

EndProcedure

Procedure nth_difference(List a(), List b(), n)

 Protected i
 CopyList(a(), b())
 For i = 1 To n
   forward_difference(b())
 Next

EndProcedure

Procedure.s display(List a())

 Protected output.s
 ForEach a()
   output + Str(a()) + ","
 Next
 ProcedureReturn RTrim(output,",")

EndProcedure

DataSection

 ;list data
 Data.i 10 ;element count
 Data.i 90, 47, 58, 29, 22, 32, 55, 5, 55, 73

EndDataSection

create and fill list

Define i NewList a() Read.i i While i > 0

 AddElement(a()): Read.i a(): i - 1

Wend

If OpenConsole()

 NewList b()
 For i = 1 To 10
   nth_difference(a(), b(), i)
   PrintN(Str(i) + "   [" + display(b()) + "]")
 Next
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf

</lang>

Output:

1   [43,-11,29,7,-10,-23,50,-50,-18]
2   [54,-40,22,17,13,-73,100,-32]
3   [94,-62,5,4,86,-173,132]
4   [156,-67,1,-82,259,-305]
5   [223,-68,83,-341,564]
6   [291,-151,424,-905]
7   [442,-575,1329]
8   [1017,-1904]
9   [2921]
10   []

Python

<lang python>>>> dif = lambda s: [x-s[i] for i,x in enumerate(s[1:])] >>> # or, dif = lambda s: [x-y for x,y in zip(s[1:],s)] >>> difn = lambda s, n: difn(dif(s), n-1) if n else s

>>> s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] >>> difn(s, 0) [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] >>> difn(s, 1) [-43, 11, -29, -7, 10, 23, -50, 50, 18] >>> difn(s, 2) [54, -40, 22, 17, 13, -73, 100, -32]

>>> from pprint import pprint >>> pprint( [difn(s, i) for i in xrange(10)] ) [[90, 47, 58, 29, 22, 32, 55, 5, 55, 73],

[-43, 11, -29, -7, 10, 23, -50, 50, 18],
[54, -40, 22, 17, 13, -73, 100, -32],
[-94, 62, -5, -4, -86, 173, -132],
[156, -67, 1, -82, 259, -305],
[-223, 68, -83, 341, -564],
[291, -151, 424, -905],
[-442, 575, -1329],
[1017, -1904],
[-2921]]</lang>

R

<lang R>forwarddif <- function(a, n) {

 if ( n == 1 )
   a[2:length(a)] - a[1:length(a)-1]
 else {
   r <- forwarddif(a, 1)
   forwarddif(r, n-1)
 }

}

fdiff <- function(a, n) {

 r <- a
 for(i in 1:n) {
   r <- r[2:length(r)] - r[1:length(r)-1]
 }
 r

}

v <- c(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)

print(forwarddif(v, 9)) print(fdiff(v, 9))</lang>

Racket

lang racket

(define (forward-difference list)

 (for/list ([x (cdr list)] [y list]) (- x y)))

(define (nth-forward-difference n list)

 (for/fold ([list list]) ([n n]) (forward-difference list)))

(nth-forward-difference 9 '(90 47 58 29 22 32 55 5 55 73))

-> '(-2921)

</lang>

Raku

(formerly Perl 6)

Works with: Rakudo Star version 2010-07

Here we use signature matching to bind both an entire array and a version missing the head. The Z- operator is a zip metaoperator with a minus to subtract the two lists pairwise. It's almost a shame to define difn, since the series and subscript are hardly longer than the call itself would be, and arguably more self-documenting than the name of the function would be. <lang perl6>sub dif(@array [$, *@tail]) { @tail Z- @array } sub difn($array, $n) { ($array, &dif ... *)[$n] }</lang>

REXX

no error checking

The REXX version uses the same (input) numbers (for the default) as the Ada example.

This version allows a specification of the list of numbers and/or which order to process. <lang rexx>/*REXX program computes the forward difference of a list of numbers. */ numeric digits 100 /*ensure enough accuracy (decimal digs)*/ parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */ if e== then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/

=words(e) /*# is the number of elements in list.*/

                                                /* [↓]  assign list numbers to @ array.*/
  do i=1  for #;  @.i=word(e, i)/1;  end /*i*/  /*process each number one at a time.   */
                                                /* [↓]  process the optional order.    */

if N== then parse value 0 # # with bot top N /*define the default order range. */

         else parse var N bot 1 top             /*Not specified?  Then use only 1 order*/

say right(# 'numbers:', 44) e /*display the header title and ··· */ say left(, 44)copies('─', length(e)+2) /* " " " fence. */

                                                /* [↓]  where da rubber meets da road. */
     do o=bot  to top;        do r=1  for #;  !.r=@.r;     end /*r*/;        $=
       do j=1  for o; d=!.j;  do k=j+1  to #; parse value !.k !.k-d with d !.k; end /*k*/
       end   /*j*/
                              do i=o+1  to #; $=$ !.i/1;   end /*i*/
     if $==  then $=' [null]'
     say right(o, 7)th(o)'─order forward difference vector ='     $
     end     /*o*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</lang> output when using the default input:

                                 10 numbers: 90 47 58 29 22 32 55 5 55 73
                                            ──────────────────────────────
      0th-order forward difference vector =  90 47 58 29 22 32 55 5 55 73
      1st-order forward difference vector =  -43 11 -29 -7 10 23 -50 50 18
      2nd-order forward difference vector =  54 -40 22 17 13 -73 100 -32
      3rd-order forward difference vector =  -94 62 -5 -4 -86 173 -132
      4th-order forward difference vector =  156 -67 1 -82 259 -305
      5th-order forward difference vector =  -223 68 -83 341 -564
      6th-order forward difference vector =  291 -151 424 -905
      7th-order forward difference vector =  -442 575 -1329
      8th-order forward difference vector =  1017 -1904
      9th-order forward difference vector =  -2921
     10th-order forward difference vector =  [null]

output when the Tcl's input was used: 90.5 47 58 29 22 32 55 5 55 73.5

                                 10 numbers: 90.5 47 58 29 22 32 55 5 55 73.5
                                            ──────────────────────────────────
      0th-order forward difference vector =  90.5 47 58 29 22 32 55 5 55 73.5
      1st-order forward difference vector =  -43.5 11 -29 -7 10 23 -50 50 18.5
      2nd-order forward difference vector =  54.5 -40 22 17 13 -73 100 -31.5
      3rd-order forward difference vector =  -94.5 62 -5 -4 -86 173 -131.5
      4th-order forward difference vector =  156.5 -67 1 -82 259 -304.5
      5th-order forward difference vector =  -223.5 68 -83 341 -563.5
      6th-order forward difference vector =  291.5 -151 424 -904.5
      7th-order forward difference vector =  -442.5 575 -1328.5
      8th-order forward difference vector =  1017.5 -1903.5
      9th-order forward difference vector =  -2921
     10th-order forward difference vector =  [null]

with error checking

<lang rexx>/*REXX program computes the forward difference of a list of numbers. */ numeric digits 100 /*ensure enough accuracy (decimal digs)*/ parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */ if e== then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/

=words(e) /*# is the number of elements in list.*/

                                                /* [↓]  verify list items are numeric. */
  do i=1  for #;        _=word(e, i)            /*process each number one at a time.   */
  if \datatype(_, 'N')  then call ser    _    "isn't a valid number";    @.i=_/1
  end   /*i*/                                   /* [↑]  removes superfluous stuff.     */
                                                /* [↓]  process the optional order.    */

if N== then parse value 0 # # with bot top N /*define the default order range. */

         else parse var N bot 1 top             /*Not specified?  Then use only 1 order*/

if #==0 then call ser "no numbers were specified." if N<0 then call ser N "(order) can't be negative." if N># then call ser N "(order) can't be greater than" # say right(# 'numbers:', 44) e /*display the header (title) and ··· */ say left(, 44)copies('─', length(e)+2) /*display the header fence. */

                                                /* [↓]  where da rubber meets da road. */
     do o=bot  to top;        do r=1  for #;  !.r=@.r;     end /*r*/;        $=
       do j=1  for o; d=!.j;  do k=j+1  to #; parse value !.k !.k-d with d !.k; end /*k*/
       end   /*j*/
                              do i=o+1  to #; $=$ !.i/1;   end /*i*/
     if $==  then $=' [null]'
     say right(o, 7)th(o)'─order forward difference vector ='     $
     end     /*o*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ ser: say; say '***error***'; say arg(1); say; exit 13 th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</lang> output is the same as the REXX entry above.

with output alignment

<lang rexx>/*REXX program computes the forward difference of a list of numbers. */ numeric digits 100 /*ensure enough accuracy (decimal digs)*/ parse arg e ',' N /*get a list: ε1 ε2 ε3 ε4 ··· , order */ if e== then e=90 47 58 29 22 32 55 5 55 73 /*Not specified? Then use the default.*/

=words(e); w=5 /*# is the number of elements in list.*/

                                                /* [↓]  verify list items are numeric. */
  do i=1  for #;        _=word(e, i)            /*process each number one at a time.   */
  if \datatype(_, 'N')  then call ser    _    "isn't a valid number";    @.i=_/1
  w=max(w, length(@.i))                         /*use the maximum length of an element.*/
  end   /*i*/                                   /* [↑]  removes superfluous stuff.     */
                                                /* [↓]  process the optional order.    */

if N== then parse value 0 # # with bot top N /*define the default order range. */

         else parse var N bot 1 top             /*Not specified?  Then use only 1 order*/

if #==0 then call ser "no numbers were specified." if N<0 then call ser N "(order) can't be negative." if N># then call ser N "(order) can't be greater than" # _=; do k=1 for #; _=_ right(@.k, w); end /*k*/; _=substr(_, 2) say right(# 'numbers:', 44) _ /*display the header title and ··· */ say left(, 44)copies('─', w*#+#) /* " " " fence. */

                                                /* [↓]  where da rubber meets da road. */
     do o=bot  to top;        do r=1  for #;  !.r=@.r;     end /*r*/;        $=
       do j=1  for o; d=!.j;  do k=j+1  to #;     parse value  !.k  !.k-d   with   d  !.k
                              w=max(w, length(!.k))
                              end   /*k*/
       end   /*j*/
                              do i=o+1  to #; $=$ right(!.i/1, w);  end  /*i*/
     if $==  then $=' [null]'
     say right(o, 7)th(o)'─order forward difference vector ='     $
     end     /*o*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ ser: say; say '***error***'; say arg(1); say; exit 13 th: procedure; x=abs(arg(1)); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</lang> output when using the default input:

                                 10 numbers:    90    47    58    29    22    32    55     5    55    73
                                            ────────────────────────────────────────────────────────────
      0th─order forward difference vector =     90    47    58    29    22    32    55     5    55    73
      1st─order forward difference vector =    -43    11   -29    -7    10    23   -50    50    18
      2nd─order forward difference vector =     54   -40    22    17    13   -73   100   -32
      3rd─order forward difference vector =    -94    62    -5    -4   -86   173  -132
      4th─order forward difference vector =    156   -67     1   -82   259  -305
      5th─order forward difference vector =   -223    68   -83   341  -564
      6th─order forward difference vector =    291  -151   424  -905
      7th─order forward difference vector =   -442   575 -1329
      8th─order forward difference vector =   1017 -1904
      9th─order forward difference vector =  -2921
     10th─order forward difference vector = [null]

Version 2

<lang rexx>/* REXX ***************************************************************

Forward differences
18.08.2012 Walter Pachl derived from PL/I
- - - - /

Do n=-1 To 11

 Call differences '90 47 58 29 22 32 55 5 55 73',n
 End

Exit

differences: Procedure

 Parse Arg a,n
 m=words(a)
 Select
   When n<0 Then Say 'n is negative:' n '<' 0
   When n>m Then Say 'n is too large:' n '>' m
   Otherwise Do
     Do i=1 By 1 while a<>
       Parse Var a a.i a
       End
     Do i = 1 to n;
       t = a.i;
       Do j = i+1 to m;
         u = a.j
         a.j = a.j-t;
         t = u;
         end;
       end;
     ol=
     Do k=n+1 to m
       ol=ol a.k
       End
     Say n ol
     End
   End
 Return</lang>

Output:

for Java's input

n is negative: -1 < 0
0  90 47 58 29 22 32 55 5 55 73
1  -43 11 -29 -7 10 23 -50 50 18
2  54 -40 22 17 13 -73 100 -32
3  -94 62 -5 -4 -86 173 -132
4  156 -67 1 -82 259 -305
5  -223 68 -83 341 -564
6  291 -151 424 -905
7  -442 575 -1329
8  1017 -1904
9  -2921
10
n is too large: 11 > 10

Ring

Project : Forward difference

s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73] for p = 1 to 9

     s = fwddiff(s)
     showarray(s)

       for j=1 to len(s)-1
            s[j] = s[j+1]-s[j]
       next
       n = len(s)
       del(s, n)
       return s

func showarray(vect)

       see "{"
       svect = ""
       for n = 1 to len(vect)
             svect = svect + vect[n] + ", "
       next
       svect = left(svect, len(svect) - 2)
       see svect
       see "}" + nl

</lang> Output:

{-43, 11, -29, -7, 10, 23, -50, 50, 18}
{54, -40, 22, 17, 13, -73, 100, -32}
{-94, 62, -5, -4, -86, 173, -132}
{156, -67, 1, -82, 259, -305}
{-223, 68, -83, 341, -564}
{291, -151, 424, -905}
{-442, 575, -1329}
{1017, -1904}
{-2921}

Ruby

This code uses new features from Ruby 1.8.7:

Enumerable#each_cons is a new method.
Integer#times, without a block, returns an enumerator.

Works with: Ruby version 1.8.7

<lang ruby>def dif(s)

 s.each_cons(2).collect { |x, y| y - x }

end

def difn(s, n)

 n.times.inject(s) { |s, | dif(s) }

end</lang>

Example usage:

Scala

<lang scala>def fdiff(xs: List[Int]) = (xs.tail, xs).zipped.map(_ - _)

def fdiffn(i: Int, xs: List[Int]): List[Int] = if (i == 1) fdiff(xs) else fdiffn(i - 1, fdiff(xs))</lang>

Example:

<lang scala>val l=List(90,47,58,29,22,32,55,5,55,73) (1 to 9)foreach(x=>println(fdiffn(x,l)))</lang>

Output:

List(-43, 11, -29, -7, 10, 23, -50, 50, 18)
List(54, -40, 22, 17, 13, -73, 100, -32)
List(-94, 62, -5, -4, -86, 173, -132)
List(156, -67, 1, -82, 259, -305)
List(-223, 68, -83, 341, -564)
List(291, -151, 424, -905)
List(-442, 575, -1329)
List(1017, -1904)
List(-2921)

Scheme

<lang scheme>(define (forward-diff lst)

 (if (or (null? lst) (null? (cdr lst)))
     '()
     (cons (- (cadr lst) (car lst))
           (forward-diff (cdr lst)))))

(define (nth-forward-diff n xs)

 (if (= n 0)
     xs
     (nth-forward-diff (- n 1)
                       (forward-diff xs))))</lang>

Output:

> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73))
(-2921)

Seed7

<lang seed7>$ include "seed7_05.s7i";

const func array integer: forwardDifference (in array integer: data) is func

 result
   var array integer: diffResult is 0 times 0;
 local
   var integer: index is 0;
 begin
   for index range 1 to pred(length(data)) do
     diffResult &:= -data[index] + data[succ(index)];
   end for;
 end func;

const proc: main is func

 local
   var array integer: data is [] (90, 47, 58, 29, 22, 32, 55, 5, 55, 73);
   var integer: level is 0;
   var integer: number is 0;
   var boolean: firstElement is TRUE;
 begin
   for level range 0 to length(data) do
     firstElement := TRUE;
     for number range data do
       if not firstElement then
         write(", ");
       end if;
       firstElement := FALSE;
       write(number);
     end for;
     writeln;
     data := forwardDifference(data);
   end for;
 end func;</lang>

Output:

90, 47, 58, 29, 22, 32, 55, 5, 55, 73
-43, 11, -29, -7, 10, 23, -50, 50, 18
54, -40, 22, 17, 13, -73, 100, -32
-94, 62, -5, -4, -86, 173, -132
156, -67, 1, -82, 259, -305
-223, 68, -83, 341, -564
291, -151, 424, -905
-442, 575, -1329
1017, -1904
-2921

SequenceL

Solution that keeps track of intermediate values: <lang sequenceL> forwardDifference(x(1), n) := forwardDifferenceHelper(x, n, [x]);

forwardDifferenceHelper(x(1), n, result(2)) := let difference := tail(x) - x[1 ... size(x) - 1]; in result when n = 0 or size(x) = 1 else forwardDifferenceHelper(difference, n - 1, result ++ [difference]); </lang> If no intermediate values are needed, the following is sufficient: <lang sequenceL> forwardDifference(x(1),n) := x when n = 0 or size(x) = 1 else forwardDifference(tail(x) - x[1 ... size(x) - 1], n - 1); </lang>

Sidef

<lang ruby>func dif(arr) {

   gather {
       for i (0 ..^ arr.end) {
           take(arr[i+1] - arr[i])
       }
   }

}

func difn(n, arr) {

   { arr = dif(arr) } * n
   arr

}

say dif([1, 23, 45, 678]) # => [22, 22, 633] say difn(2, [1, 23, 45, 678]) # => [0, 611]</lang>

Slate

<lang slate>s@(Sequence traits) forwardDifference [

 s allButFirst with: s allButLast collect: #- `er

].

s@(Sequence traits) forwardDifference "Without creating two intermediate throwaway Sequences." [

 result ::= s allButFirst.
 result doWithIndex: [| :nextValue :index | result at: index infect: [| :oldValue | oldValue - (s at: index)].
 result

].

s@(Sequence traits) forwardDifference: n [

 (0 below: n) inject: s into: [| :seq :_ | seq forwardDifference]

].</lang>

Usage:

<lang slate>#data := ##(90 47 58 29 22 32 55 5 55 73). data keysDo: [| :index | inform: (data forwardDifference: index) printString].</lang>

Smalltalk

Works with: GNU Smalltalk

<lang smalltalk>Array extend [

   difference [
       ^self allButFirst with: self allButLast collect: [ :a :b | a - b ]
   ]

   nthOrderDifference: n [
       ^(1 to: n) inject: self into: [ :old :unused | old difference ]
   ]

]

s := #(90 47 58 29 22 32 55 5 55 73) 1 to: s size - 1 do: [ :i |

   (s nthOrderDifference: i) printNl ]</lang>

SQL

Works with: SQLite version 3.13.0

<lang sql>WITH RECURSIVE T0 (N, ITEM, LIST, NEW_LIST) AS (

   SELECT 1,
          NULL, 
          '90,47,58,29,22,32,55,5,55,73' || ',',
          NULL
    UNION ALL
   SELECT CASE
              WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) = 
              THEN N + 1
              ELSE N
          END,
          CASE
              WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) <> 
              THEN SUBSTR(LIST, 1, INSTR(LIST, ',') - 1)
              ELSE NULL
          END,
          CASE
              WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) = 
              THEN IFNULL(NEW_LIST || (SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) - ITEM) || ',', )
              ELSE SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST))
          END,
          CASE
              WHEN SUBSTR(LIST, INSTR(LIST, ',') + 1, LENGTH(LIST)) <> 
              THEN IFNULL(NEW_LIST, ) || IFNULL((SUBSTR(LIST, 1, INSTR(LIST, ',') - 1) - ITEM) || ',', )
              ELSE NULL
          END
     FROM T0
    WHERE INSTR(LIST, ',') > 0

) SELECT N,

      TRIM(LIST, ',') LIST
 FROM T0
WHERE NEW_LIST IS NULL
  AND LIST <> 
ORDER BY N;</lang>

Standard ML

<lang sml>fun forward_difference xs = ListPair.map op- (tl xs, xs)

fun nth_forward_difference n xs =

 if n = 0 then
   xs
 else
   nth_forward_difference (n-1) (forward_difference xs)</lang>

Output:

- nth_forward_difference 9 [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
val it = [~2921] : int list

Stata

It's possible to implement differences using row indices. For instance, first forward differences of a variable x can be defined by:

However, it's much more natural to use time-series varlists. In order to use them, it's necessary to first set a time variable, which may be simply an index variable.

<lang stata>* First create a dataset clear all set obs 100 gen i=_n tsset i gen x=rnormal()

Differences

display "Difference order?" _request(k) gen y=D${k}F${k}.x</lang>

Swift

<lang swift>func forwardsDifference<T: SignedNumeric>(of arr: [T]) -> [T] {

 return zip(arr.dropFirst(), arr).map({ $0.0 - $0.1 })

}

func nthForwardsDifference<T: SignedNumeric>(of arr: [T], n: Int) -> [T] {

 assert(n >= 0)

 switch (arr, n) {
 case ([], _):
   return []
 case let (arr, 0):
   return arr
 case let (arr, i):
   return nthForwardsDifference(of: forwardsDifference(of: arr), n: i - 1)
 }

}

for diff in (0...9).map({ nthForwardsDifference(of: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73], n: $0) }) {

 print(diff)

}</lang>

Output:

[90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
[-43, 11, -29, -7, 10, 23, -50, 50, 18]
[54, -40, 22, 17, 13, -73, 100, -32]
[-94, 62, -5, -4, -86, 173, -132]
[156, -67, 1, -82, 259, -305]
[-223, 68, -83, 341, -564]
[291, -151, 424, -905]
[-442, 575, -1329]
[1017, -1904]
[-2921]

Tcl

<lang tcl>proc do_fwd_diff {list} {

   set previous [lindex $list 0]
   set new [list]
   foreach current [lrange $list 1 end] {
       lappend new [expr {$current - $previous}]
       set previous $current
   }
   return $new

}

proc fwd_diff {list order} {

   while {$order >= 1} {
       set list [do_fwd_diff $list]
       incr order -1
   }
   return $list

}

set a {90.5 47 58 29 22 32 55 5 55 73.5}

for {set order 0} {$order <= 10} {incr order} {

   puts [format "%d\t%s" $order [fwd_diff $a $order]]

}</lang>

Output:

0	90.5 47 58 29 22 32 55 5 55 73.5
1	-43.5 11 -29 -7 10 23 -50 50 18.5
2	54.5 -40 22 17 13 -73 100 -31.5
3	-94.5 62 -5 -4 -86 173 -131.5
4	156.5 -67 1 -82 259 -304.5
5	-223.5 68 -83 341 -563.5
6	291.5 -151 424 -904.5
7	-442.5 575 -1328.5
8	1017.5 -1903.5
9	-2921.0
10

Ursala

This function doesn't need to be defined because it's in a library already, but it could be defined like this: <lang Ursala>#import std

import nat
import flo

nth_diff "n" = rep"n" minus*typ</lang> test program: <lang Ursala>test_data = <90.,47.,58.,29.,22.,32.,55.,5.,55.,73.>

show+

examples =

printf/*=*' %0.0f' <

  nth_diff6 test_data,
  nth_diff7 test_data></lang>

Output:

 291 -151 424 -905
 -442 575 -1329

Visual Basic .NET

Works with: Visual Basic .NET version 2008+

<lang vbnet>Module ForwardDifference

   Sub Main()
       Dim lNum As New List(Of Integer)(New Integer() {90, 47, 58, 29, 22, 32, 55, 5, 55, 73})
       For i As UInteger = 0 To 9
           Console.WriteLine(String.Join(" ", (From n In Difference(i, lNum) Select String.Format("{0,5}", n)).ToArray()))
       Next
       Console.ReadKey()
   End Sub

   Private Function Difference(ByVal Level As UInteger, ByVal Numbers As List(Of Integer)) As List(Of Integer)
       If Level >= Numbers.Count Then Throw New ArgumentOutOfRangeException("Level", "Level must be less than number of items in Numbers")

       For i As Integer = 1 To Level
           Numbers = (From n In Enumerable.Range(0, Numbers.Count - 1) _
                      Select Numbers(n + 1) - Numbers(n)).ToList()
       Next

       Return Numbers
   End Function

End Module</lang>

Output:

   90    47    58    29    22    32    55     5    55    73
  -43    11   -29    -7    10    23   -50    50    18
   54   -40    22    17    13   -73   100   -32
  -94    62    -5    -4   -86   173  -132
  156   -67     1   -82   259  -305
 -223    68   -83   341  -564
  291  -151   424  -905
 -442   575 -1329
 1017 -1904
-2921

Visual FoxPro

DEFINE CTAB CHR(9)

LOCAL lcList As String, i As Integer, n As Integer n = 10 LOCAL ARRAY aa[n] CLEAR lcList = "90,47,58,29,22,32,55,5,55,73" FOR i = 1 TO n

   aa[i] = VAL(GETWORDNUM(lcList, i, ","))

ENDFOR ShowOutput("Original", @aa) k = n - 1 FOR i = 1 TO n - 1

   ForwardDiff(@aa)
   ShowOutput("Difference " + TRANSFORM(i), @aa)

ENDFOR

PROCEDURE ForwardDiff(a) LOCAL i As Integer, n As Integer n = ALEN(a) LOCAL ARRAY b[n-1] FOR i = 1 TO n - 1

   b[i] = a[i+1] - a[i]

ENDFOR DIMENSION a[n-1] ACOPY(b, a) ENDPROC

PROCEDURE ShowOutput(lcLabel, zz) LOCAL i As Integer, n As Integer, lcTxt As String n = ALEN(zz) lcTxt = lcLabel + ":" + CTAB FOR i = 1 TO n

   lcTxt = lcTxt + TRANSFORM(zz[i]) + CTAB

ENDFOR lcTxt = LEFT(lcTxt, LEN(lcTxt) - 1) ? lcTxt ENDPROC </lang>

Output:

Original:       90      47      58      29      22      32      55      5       55      73 
Difference 1:   -43     11      -29     -7      10      23      -50     50      18 
Difference 2:   54      -40     22      17      13      -73     100     -32 
Difference 3:   -94     62      -5      -4      -86     173     -132 
Difference 4:   156     -67     1       -82     259     -305 
Difference 5:   -223    68      -83     341     -564 
Difference 6:   291     -151    424     -905 
Difference 7:   -442    575     -1329 
Difference 8:   1017    -1904 
Difference 9:   -2921

zkl

Translation of: Scheme

<lang zkl>fcn forwardDiff(lst){

  if(lst.len()<2)
     return(T);
     return(T(lst[1]-lst[0]).extend(forwardDiff(lst[1,*])))

} fcn nthForwardDiff(n,xs){

  if(n==0)
     return(xs);
     return(nthForwardDiff(n-1,forwardDiff(xs))) // tail recursion

}</lang> <lang zkl>nthForwardDiff(9,T(90, 47, 58, 29, 22, 32, 55, 5, 55, 73)).println();</lang>

Output:

L(-2921)

ZX Spectrum Basic

<lang zxbasic>10 DATA 9,0,1,2,4,7,4,2,1,0 20 LET p=1 30 READ n: DIM b(n) 40 FOR i=1 TO n 50 READ b(i) 60 NEXT i 70 FOR j=1 TO p 80 FOR i=1 TO n-j 90 LET b(i)=b(i+1)-b(i) 100 NEXT i 110 NEXT j 120 FOR i=1 TO n-p 130 PRINT b(i);" "; 140 NEXT i</lang>