How do I express this?

Question

I'm trying to work out how to write the following:

total = (value * 0.95 ^ 0) + (value * 0.95 ^ 1) + (value * 0.95 ^ 2) ...

or:

x = (y * z ^ 0) + (y * z ^ 1) + (y * z ^ 2) + (y * z ^ 3) ...

This expresses how to calculate x for 4 iterations, but how can I express this to work with a variable number of iterations? Obviously I could create a loop and add the values together, but I'd really like to find a single equation that solves this.

I'm using c++ but I guess this isn't really a language specific problem (sorry I literally don't know where else to ask this question!).

Any ideas?

Thanks, Chris.

Answer 1

There is no need for a loop here, you "just" need to employ some maths.

Note that you can rewrite that as

y * (z⁰ + z¹ + ... + zⁿ)

Now, the series

z⁰ + z¹ + ... + zⁿ

sums to

(z⁽ⁿ⁺¹⁾ - 1) / (z - 1)

so your equation would be

x = y * (z⁽ⁿ⁺¹⁾ - 1) / (z - 1)

Answer 2

Equation-wise solving, this is a geometric series and can therefore be calculated with

double geometric_series(double y, double z, int N) {
  return y * (std::pow(z, N) - 1.0) / (z - 1.0);
}

but the same result can be obtained with some fun C++ metaprogramming: if you know the number of iterations in advanced and you're allowed to use C++17 features and fold expressions you could do as follows

template<std::size_t... N> 
double calculate_x(double y, double z, std::index_sequence<N...>) { // [0;N[
 auto f = [](double y_p, double z_p, double exp) {
   return y_p * std::pow(z_p, exp);
 };
 return (f(y, z, N) + ...);
}

template <std::size_t N>
auto calculate_x(double y, double z) {
  return calculate_x(y, z, std::make_index_sequence<N>{}); 
}

Alternatively this can also be done with pre-C++17 templates

template <int N>
double calculate_x(double y, double z) {
  return calculate_x<N-1>(y, z) + (y * std::pow(z, N - 1));
}

template <>
double calculate_x<0>(double, double) {
  return 0;
}

Otherwise a simpler solution would be to just use a loop

double calculate_x_simple(double y, double z, int N) {
  double ret = 0.0;
  for (int i = 0 ; i < N ; ++i)
    ret += y * std::pow(z, i);
  return ret;
}

Driver for the code above

int main() {

   // x = (y * z ^ 0) + (y * z ^ 1) + (y * z ^ 2) + (y * z ^ 3)
   double y = 42.0;
   double z = 44.5;
   std::cout << (calculate_x<3>(y, z) == calculate_x_simple(y, z, 3)); // 1

}

Answer 3

As you mentioned, it seems reasonable to use a loop. But if you know the amount of iterations at compile time, you could use templates like this:

template <int n>
double foo(double y, double z)
{
    return foo<n-1>(y, z) + y * std::pow(z, n);
}

template <>
double foo<-1>(double, double)
{
    return 0;
}

With just a little bit of optimisation this will unfold to a single equation.

Example:

#include <iostream>
#include <cmath>

template <int n>
double foo(double y, double z)
{
    return foo<n-1>(y, z) + y * std::pow(z, n);
}

template <>
double foo<-1>(double, double)
{
    return 0;
}


int main()
{
    std::cout << foo<2>(2,3) << std::endl;
}

Output: 26