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

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

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

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

[edit] Using Vector Operations

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

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

[edit] Short Functional Version

Same output:

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

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

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

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

Works with: jq version 1.4
# 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;

Example:

def s: [90, 47, 58, 29, 22, 32, 55, 5, 55, 73];
 
range(0;12) as $i | (s|ndiff($i))
Output:
$ 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]
[]
[]

[edit] Julia

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

ndiff(A, n::Integer) = n < 1 ? A : diff(ndiff(A, n-1))
Output:
julia> s = [90, 47, 58, 29, 22, 32, 55, 5, 55, 73]
julia> [ndiff(s, i) for i in 0:9]
10-element Array{Any,1}:
 [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] 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] 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))
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)

[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);
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]
Output:
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] Nimrod

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

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

[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

[edit] zkl

Translation of: Scheme
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
Output:
nthForwardDiff(9,T(90, 47, 58, 29, 22, 32, 55, 5, 55, 73))
L(-2921)

Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox