C++: Forward Difference

Provide code that produces a list of numbers which is the n-th order forward difference, given a non-negative integer (specifying the order) and a list of numbers. The first-order forward difference of a list of numbers (A) is a new list (B) where B_n = A_n+1 – A_n. List B should have one fewer element as a result. The second-order forward difference of A will be 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)

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.

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

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