 # C++: Forward Difference

Posted in C++ 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)
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 = { 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 << 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;
}

Output:
-2921

SOURCE

Content is available under GNU Free Documentation License 1.2.