Forward difference

From Rosetta Code
Jump to: navigation, search
Task
Forward difference
You are encouraged to solve this task according to the task description, using any language you may know.

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 Bn = An+1 - An. List B should have one fewer element as a result. The second-order forward difference of A will be 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)

Contents

[edit] 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;

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]

[edit] 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
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
)

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

[edit] APL

Works with: Dyalog APL
Translation of: J
      list ←  90 47 58 29 22 32 55 5 55 73
 
      fd   ←  {⍺=0:⍵⋄(⍺-1)∇(1↓⍵)-(¯1↓⍵)} 
 
      1 fd list 
¯43 11 ¯29 ¯7 10 23 ¯50 50 18
 
      2 fd list 
54 ¯40 22 17 13 ¯73 100 ¯32

[edit] AutoHotkey

contributed by Laszlo on the ahk forum 

MsgBox % diff("2,3,4,3",1)
MsgBox % diff("2,3,4,3",2)
MsgBox % diff("2,3,4,3",3)
MsgBox % diff("2,3,4,3",4)
 
diff(list,ord) { ; high order forward differences of a list
   Loop %ord% {
      L =
      Loop Parse, list, `, %A_Space%%A_Tab%
         If (A_Index=1)
            p := A_LoopField
         Else
            L .= "," A_LoopField-p, p := A_LoopField
      list := SubStr(L,2)
   }
   Return list
}

[edit] 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); 
}

Using Pascal's triangle: 

#!/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); 
}

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

[edit] BBC BASIC

Works with: BBC BASIC for Windows
      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$))

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

[edit] C

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
double* fwd_diff(double* x, unsigned int len, unsigned int order)
{
	unsigned int i, j;
	double* y;
 
	/* handle two special cases */
	if (order >= len) return 0;
 
	y = malloc(sizeof(double) * len);
	if (!order) {
		memcpy(y, x, sizeof(double) * len);
		return y;
	}
 
	/* first order diff goes from x->y, later ones go from y->y */
	for (j = 0; j < order; j++, x = y)
		for (i = 0, len--; i < len; i++)
			y[i] = x[i + 1] - x[i];
 
	y = realloc(y, sizeof(double) * len);
	return y;
}
 
int main(void)
{
	double *y, x[] = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73};
	int i, len = sizeof(x) / sizeof(x[0]);
 
	y = fwd_diff(x, len, 1);
	for (i = 0; i < len - 1; i++)
		printf("%g ", y[i]);
	putchar('\n');
 
	return 0;
}

Use method with Pascal triangle, binomial coefficients are pre-computed 

#include <stdio.h>
 
int* binomCoeff(int n) {
     int *b = calloc(n+1,sizeof(int)); 
     int j; 
     b[0] = n%2 ? -1 : 1; 
     for (j=1 ; j<=n; j++) 
           b[j] = -b[j-1]*(n+1-j)/j;
 
     return(b); 
};  
 
main () {
    double array[] = { 90, 47, 58, 29, 22, 32, 55, 5, 55, 73 };
    size_t lenArray = sizeof(array)/sizeof(array[0]);	
 
    int p = 4;  // order 
    int *b = binomCoeff(p);   // pre-compute binomial coefficients for order p
 
    int j, k; 
 
    // compute p-th difference 
    for (k=0 ; k < lenArray; k++)
        for (array[k] *= b[0], j=1 ; j<=p; j++) 
            array[k] += b[j] * array[k+j];
 
    free(b);     
 
    // resulting series is shorter by p elements
    lenArray -= p; 	
    for (k=0 ; k < lenArray; k++)  printf("%f ",array[k]);
    printf("\n");
}
 

[edit] C#

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

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

[edit] 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. 

#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));
 
  // outut 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;
}

This gives the following 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.

[edit] 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;
}
 

Produces: 

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: 

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

Produces: 

-2921

[edit] 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;
}
 

Produces: 

-2921

[edit] Clojure

(defn fwd-diff [nums order]
  (nth (iterate #(map - (next %) %) nums) order))

[edit] 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
 

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 []

[edit] Common 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)))


[edit] D

[edit] Basic Version

import std.stdio;
 
T[] forwardDifference(T)(in T[] data, in int level) pure nothrow
    in {
        assert(level >= 0 && level < data.length);
    } body {
        //auto result = data.dup; // not nothrow
        auto result = data ~ []; // slower
        foreach (i; 0 .. level)
            foreach (j, ref el; result[0 .. $ - i - 1])
                el = result[j + 1] - el;
        result.length -= level;
        return result;
    }
 
void main() {
    auto data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
    foreach (level; 0 .. data.length)
        writeln(forwardDifference(data, level));
}
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]

[edit] Alternative Version

Same output: 

import std.stdio, std.algorithm, std.range, std.array;
 
auto forwardDifference(Range)(Range d, in int level) {
    foreach (_; 0 .. level)
        d = zip(d[1 .. $], d).map!q{ a[0] - a[1] }().array();
    return d;
}
 
void main() {
    auto data = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
    foreach (level; 0 .. data.length)
        writeln(forwardDifference(data, level));
}

[edit] Using Vector Operations

forwardDifference mutates the array in-place (same output): 

import std.stdio;
 
T[] forwardDifference(T)(T[] s, in int n) pure {
    foreach (_; 0 .. n)
        s[] -= s[1 .. $];
    return s[0 .. $ - n];
}
void main() {
    immutable A = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
    foreach (level; 0 .. A.length)
        writeln(forwardDifference(A.dup, level));
}

[edit] Short Functional Version

Same output: 

import std.stdio, std.range;
 
void main() {
  auto D = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
  auto R = recurrence!q{(a[n-1].dup[] -= a[n-1][1..$])[0..$-1]}(D);
  foreach (di; take(R, D.length))
    writeln(di);
}

[edit] 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)
> }

[edit] 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 ;
 
 ( scratchpad ) { 90.5 47 58 29 22 32 55 5 55 73.5 } 4 n-order .
 { 156.5 -67 1 -82 259 -304.5 }

[edit] 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

[edit] Fortran

Works with: Fortran version 90 and later
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
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

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

[edit] F#

Straightforward recursive solution 

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

[edit] 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]
}

Output: 

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

[edit] Haskell

forwardDifference xs = zipWith (-) (tail xs) xs
 
nthForwardDifference xs n = iterate forwardDifference xs !! n
 
> take 10 (iterate forwardDifference [90, 47, 58, 29, 22, 32, 55, 5, 55, 73])
[[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]]

[edit] 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
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

[edit] Icon and Unicon

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

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

[edit] IDL

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

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

[edit] J

Of the many ways to code this in J, a particularly concise solution is: 

fd=: 2&(-~/\)

Alternatively, to reduce the number of J primitives, use: 

fd=:}.-}:^:

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

For example: 

   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

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

   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

[edit] Java

Works with: Java version 1.5+
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;
    }
}

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]

[edit] K4

fd:1_-':

To compute the nth forward difference, call as: 

n fd/

In order to obtain all intermediate results, call as: 

n fd\

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)

[edit] 

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]

[edit] 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}))

[edit] Mathematica

Built-in function: 

i={3,5,12,1,6,19,6,2,4,9};
Differences[i]

gives back: 

{2, 7, -11, 5, 13, -13, -4, 2, 5}

The nth difference can be done as follows: 

i={3,5,12,1,6,19,6,2,4,9};
Differences[i,n]

[edit] MATLAB / Octave

This is a built-in function. X is the list of numbers, n is the order of the forward difference. 

Y = diff(X,n);

Sample Output: 1st order forward difference. 

diff([1 2 3 4 5])
 
ans =
 
     1     1     1     1

[edit] 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);

[edit] 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

Output is the same as for Rexx

[edit] Nial

Define forward difference for order 1 

fd is - [rest, front]

forward difference of 4th order 

b := 90 47 58 29 22 32 55 5 55 73 
4 fold fd b
= 156 -67 1 -82 259 -305

[edit] Objeck

Translation of: Java
 
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;
    }
  }
}
 

[edit] 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)

Output: 

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

[edit] PARI/GP

fd(v)=vector(#v-1,i,v[i+1]-v[i]);

[edit] 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.

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

[edit] Perl

sub dif {
  my @s = @_;
  map { $s[$_+1] - $s[$_] } 0 .. $#s-1
}
 
sub difn {
  my ($n, @s) = @_;
  @s = dif @s foreach 1..$n;
  @s
}

[edit] 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. 

sub dif(@array [$, *@tail]) { @tail Z- @array }
sub difn($array, $n) { ($array, &dif ... *)[$n] }

[edit] 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);
  }
 
}

[edit] 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) )

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)

[edit] 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;
 

[edit] 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;

[edit] 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) 

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

[edit] 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 
 
 

Sample 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   []

[edit] 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]]

[edit] 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))

[edit] 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)
 

[edit] REXX

[edit] Version 1

Uses the same (input) numbers as the Ada example.
Half the program was dedicated to validating the input.
This version allows a specification of the vector and/or which order to process. 

/*REXX program to compute the  forward difference  of a list of numbers.*/
/* ┌───────────────────────────────────────────────────────────────────┐
   │              /\                   n     n         n-k             │
   │ {delta}     /  \ n  [ƒ] (x)   ≡   Σ    Ç   ∙  (-1)     ∙  ƒ(x+k)  │
   │            /____\                k=0    k                         │
   │                                                                   │
   │                 {n=order}             {Ç=comb or binomial coeff.} │
   └───────────────────────────────────────────────────────────────────┘*/
numeric digits 100                     /*ensure enough accuracy.        */
arg numbers ',' ord                     /*input:  x1 x2 x3 x4 ...  ,ORD */
if numbers=='' then numbers='90 47 58 29 22 32 55 5 55 73'    /*default?*/
w=words(numbers)                       /*set W to  # of numbers in list.*/
 
          do i=1  for w                /*validate input (valid numbers?)*/
          @.i=word(numbers,i)          /*assign the next # in the list. */
          if \datatype(@.i,'N')  then call ser @.i "isn't a valid number"
          @.i=@.i/1                    /*normalize the #, prettify the #*/
          end   /*i*/
/*═════════════════════════════════════════process the (optional) input.*/
if w==0                 then call ser 'no numbers were specified'
if ord\=='' & ord<0     then call ser ord "(ner) can't be negative"
if ord\=='' & ord>w     then call ser ord "(ner) can't be greater than" w
say right(w 'numbers: ' numbers,64)    /*sloppy way to do a header, ... */
say right(copies('─',length(numbers)),64)       /* and the header fence.*/
if ord==''  then do;   bot=0;   top=w;   end    /*define default ners.*/
            else do;   bot=n;   top=n;   end    /*just a specific ner?*/
/*═════════════════════════════════════════where da rubber meets da road*/
      do order=bot  to top;            do r=1  for w; !.r=@.r; end;     $=
        do j=1  for order;   d=!.j;    do k=j+1  to w      /*order diff.*/
                                       parse value !.k !.k-d with d !.k
                                       end   /*k*/
        end   /*j*/
                                       do i=order+1  to w  /*build list.*/
                                       $=$ !.i/1           /*append it. */
                                       end   /*i*/
      if $=='' then $='[null]'                             /*pretty null*/
          what=right(order,length(w))th(order)'-order'     /*nice format*/
      say what 'forward difference vector = ' strip($)     /*display it.*/
      end      /*o*/
exit                                   /*stick a fork in it, we're done.*/
/*──────────────────────────────────SER subroutine──────────────────────*/
ser:   say;     say '*** error! ***';     say arg(1);     say;     exit 13
/*──────────────────────────────────TH subroutine───────────────────────*/
th: parse arg ?; return word('th st nd rd',1+?//10*(?//100%10\==1)*(?//10<4))

output when the default input was used 

                       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 

 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]

[edit] Version 2

/* 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

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


[edit] 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
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

Example usage: 

p dif([1, 23, 45, 678])      # => [22, 22, 633]
p difn([1, 23, 45, 678], 2)  # => [0, 611]

[edit] 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))

Example: 

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

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)

[edit] 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))))

Output: 

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

[edit] 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;

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

[edit] 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]
].

Usage: 

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

[edit] Smalltalk

Works with: GNU 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 ]

[edit] SQL

This example is in need of improvement:
This was not written by an experienced SQL programmer. If possible in standard SQL, convert to a form that doesn't require unrolled recursion to obtain the nth forward difference. Remove works-with if not appropriate.
Works with: SQLite version 3.6.22
CREATE TABLE list (n INTEGER, v REAL);
INSERT INTO list VALUES (0, 90);
INSERT INTO list VALUES (1, 47);
INSERT INTO list VALUES (2, 58);
INSERT INTO list VALUES (3, 29);
INSERT INTO list VALUES (4, 22);
INSERT INTO list VALUES (5, 32);
INSERT INTO list VALUES (6, 55);
INSERT INTO list VALUES (7, 5);
INSERT INTO list VALUES (8, 55);
INSERT INTO list VALUES (9, 73);
 
CREATE VIEW diff1 AS SELECT list.n, (SELECT NEXT.v FROM list AS NEXT WHERE NEXT.n = list.n + 1) - list.v AS v FROM list;
CREATE VIEW diff2 AS SELECT list.n, (SELECT NEXT.v FROM diff1 AS NEXT WHERE NEXT.n = list.n + 1) - list.v AS v FROM diff1 AS list;
 
SELECT * FROM diff1;
    0|-43.0
    1|11.0
    2|-29.0
    3|-7.0
    4|10.0
    5|23.0
    6|-50.0
    7|50.0
    8|18.0
    9|
SELECT * FROM diff2;
    0|54.0
    1|-40.0
    2|22.0
    3|17.0
    4|13.0
    5|-73.0
    6|100.0
    7|-32.0
    8|
    9|

[edit] Standard ML

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)

Output: 

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

[edit] 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]]
}
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

[edit] Ursala

This function doesn't need to be defined because it's in a library already, but it could be defined like this. 

#import std
#import nat
#import flo
 
nth_diff "n" = rep"n" minus*typ

test program: 

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>

output: 

 291 -151 424 -905
 -442 575 -1329

[edit] Visual Basic .NET

Works with: Visual Basic .NET version 2008+
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

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

Retrieved from "http://rosettacode.org/mw/index.php?title=Forward_difference&oldid=156470"
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox