CODEWITHSUNDEEP
c++c++11templatesvariadic-functions
Miguel Carvajal
Miguel Carvajal

Reputation: 1974

Implement divided differences in C++ with variadic templates

I am trying to implement in C++ the divided differences formula as it appears here.

So far I have come with this

template<typename F, typename T>
T divdiff(F f, T t1, T t2) {
  return (f(t1) - f(t2)) / (t1 - t2);
};

template<typename F, typename T, typename... Args>
T divdiff(F f, T tstart, Args... t, T tend) {

  return (divdiff(f, tstart, t...) - divdiff(f, t..., tend))/ (tstart - tend);

};

It compiles fine but when it try to use it for example like this

 double r = divdiff([](double x) { return 2 * x; }, 1.0, 2.0, 3.0);

I got the following error

note: candidate function not viable: requires 3 arguments, but 4 were provided
T divdiff(F f, T tstart, Args... t, T tend) {``

My compilers is gcc

Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 8.0.0 (clang-800.0.42.1) Target: x86_64-apple-darwin15.4.0 Thread model: posix InstalledDir: /Library/Developer/CommandLineTools/usr/bin

Does anyone knows why it does not work and how to fix it

Upvotes: 2

Views: 233

Answers (2)

Christopher Oicles
Christopher Oicles

Reputation: 3107

Heres the standard, tuple-unpacking recursive solution. I changed your lambda, because linear functions are kinda boring here.

#include <iostream>
#include <utility>
#include <tuple>

// The base version of divdiff, ends recursion
template<typename F, typename T>
T divdiff(F f, T t0, T t1) {
    return (f(t0) - f(t1)) / (t0 - t1);
}

// This divdiff overload takes a tuple and an index sequence
// The index sequence specifies which elements from the tuple will
// be unpacked as arguments for a divdiff call
template <typename F, typename T, std::size_t... Is>
auto divdiff(F f, T arg_tuple, std::index_sequence<Is...>) {
    return divdiff(f, std::get<Is>(arg_tuple)...);
}

template<typename F, typename T, typename ...Ts>
T divdiff(F f, T t0, Ts ...right_args) {
    // pack all arguments into a tuple
    auto arg_tuple = std::make_tuple(t0, right_args...);
    // make an index sequence whose size is one less than the
    // current recursion's argument count
    using next_index_sequence = std::make_index_sequence<sizeof...(Ts)>;
    // get the value of the final argument in tn
    auto tn = std::get<sizeof...(Ts)>(arg_tuple);
    // Call divdiff, first using the tuple/sequence overload for the left
    // side arguments.
    // Then call it with the easily-obtained right side arguments.
    return (divdiff(f, arg_tuple, next_index_sequence{})
        - divdiff(f, right_args...)) / (t0 - tn);
}

int main() {
    double r = divdiff([](double x) { return x * x * x; }, 1.0, 2.0, 3.0);
    std::cout << r << '\n';
}

Upvotes: 0

Potatoswatter
Potatoswatter

Reputation: 137910

template<typename F, typename T, typename... Args>
T divdiff(F f, T tstart, Args... t, T tend)

Since Args... t is not at the end of the parameter list, it will not be deduced. Such deduction is not allowed partly to simplify the language rules, and partly to help keep programs simple (and prevent shooting oneself in the foot.) You could specify Args ... explicitly like divdiff<F, double, double>, but then for the recursive call it would be difficult to remove the last double.

In any case, the variadic template approach suffers template bloat, and inefficiency as the argument list may be copied by each function call. Since the elements of the sequence should all be the same type, consider using iterators instead. Then you can add a convenience overload using std::initializer_list for array-based iterable sequences.

template< typename F, typename bidirectional_iterator >
typename std::iterator_traits< bidirectional_iterator >::value_type
divdiff( F f, bidirectional_iterator first, bidirectional_iterator last ) {
    bidirectional_iterator next = std::next( first );
    bidirectional_iterator prev = std::prev( last );
    auto diff = next == prev?
        f( * first ) - f( * prev )
      : divdiff( f, first, prev ) - divdiff( f, next, last );
    return diff / ( * first - * prev );
}

template< typename F, typename T >
T divdiff( F f, std::initializer_list< T > il )
    { return divdiff( f, il.begin(), il.end() ); }

Demo.

Upvotes: 2

Related Questions