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 less 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.
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]
ALGOL 68
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);
C++
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;
}
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.
D
module fdiff ;
import std.stdio ;
T[] fdiff(T = int)(T[] a, int level) {
T[] s ;
if(level < 0 || level >= a.length)
return s ;
s = a.dup ;
for(int i = 0 ; i < level ;i++)
for(int j = 0 ; j < s.length - i - 1 ; j++)
s[j] = s[j+1] - s[j] ;
s.length = s.length - level ;
return s ;
}
void main() {
auto a = [90.5, 47, 58, 29, 22, 32, 55, 5, 55, 73.5];
for(int i = 0 ; i< a.length + 1; i++)
writefln(a.fdiff(i));
}
Sampe output:
D:\00MY\dmd>fdiff [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] []
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)))
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)
> }
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]]
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
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 (rather than characters), 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
Java
import java.util.Arrays;
public class FD {
public static void main(String args[]) {
double[] a = {90, 47, 58, 29, 22, 32, 55, 5, 55, 73};
System.out.println(Arrays.toString(dif(a, 1)));
System.out.println(Arrays.toString(dif(a, 2)));
System.out.println(Arrays.toString(dif(a, 9)));
System.out.println(Arrays.toString(dif(a, 10))); //let's test
System.out.println(Arrays.toString(dif(a, 11)));
System.out.println(Arrays.toString(dif(a, -1)));
System.out.println(Arrays.toString(dif(a, 0)));
}
public static double[] dif(double[] a, int n) {
if (n < 0)
return null; // if the programmer was dumb
for (int i = 0; i < n && a.length > 0; i++) {
double[] b = new double[a.length - 1];
for (int j = 0; j < b.length; j++){
b[j] = a[j+1] - a[j];
}
a = b; //"recurse"
}
return a;
}
}
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]
Logo
to fwd.diff :l if empty? :l [output []] if empty? bf :l [output []] output fput (first bf :l)-(first :l) fwd.diff bf :l end to nth.fwd.diff :n :l if :n = 0 [output :l] output nth.fwd.diff :n-1 fwd.diff :l end
show nth.fwd.diff 9 [90 47 58 29 22 32 55 5 55 73] [-2921]
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
OCaml
<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)</ocaml>
Output:
# nth_forward_difference 9 [90; 47; 58; 29; 22; 32; 55; 5; 55; 73];; - : int list = [-2921]
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;
Python
<python>
>>> dif = lambda s: [x-s[i] for i,x in enumerate(s[1:])] >>> 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]]
</python>
Scheme
<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))))</scheme>
Output:
> (nth-forward-diff 9 '(90 47 58 29 22 32 55 5 55 73)) (-2921)
Smalltalk
This version runs on GNU Smalltalk. Other implementations might lack some of the utility methods we use:
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 ]