The sum of a sequence

Question

I'm trying to make a function for calculating this formula

#include <iostream>
#include <vector>
double Sequence(std::vector < double > & a) {
  double result = 0;
  for (int i = a.size() - 1; i > 0; i--) {
    if (a[i] == 0) throw std::domain_error("Dividing with 0");
    if (i > 1)
      result += 1 / (a[i - 1] + 1 / a[i]);
    else result += a[i - i];
    std::cout << a[i] << " " << result << " " << "\n";
  }
  return result;
}
int main() {
  std::vector<double>a{1,2,3,4,5};
  try {
    std::cout << Sequence(a);
  } catch (std::domain_error e) {
    std::cout << e.what();
  }

  return 0;
}

Code gives correct result for {1,2,3} sequence. However, if I add a few numbers to that sequence result becomes wrong. Could you help me to fix this?

Answer 1

if (i > 1)
  result += 1 / (a[i - 1] + 1 / a[i]);
else result += a[i - i];

This is wrong; it just happens to work if you have three or fewer terms.

The recurrence you actually want is

if (i == a.size() - 1) {
    result = a[i];
} else {
    result = a[i] + 1 / result;
}

you can see that this is a correct recurrence by the fact that Tidying up some more things (removing the condition from inside the loop, fixing an off-by-one in the loop termination condition, and correcting the exception condition):

double Sequence(std::vector<double> &a) {
  double result = a[a.size() - 1];
  for (int i = a.size() - 1; i >= 0; i--) {
    if (result == 0)
      throw std::domain_error("Dividing with 0");
    result = a[i] + 1 / result;
  }
  return result;
}

Answer 2

This known as the Simple Continued Fraction where all numerators are 1s. It is basically represented as [a1;a2,a3,...,an] (well in fact starts from a0 but whatever). You can calculate the result from top to bottom while obtaining a better approximation (or convergent as they call it) at each step.

The result of this finite rational series or infinite irrational series is expressed as p/q. In order to calculate the result you assume

p0   1     p1   a1       p2   a2*p1+p0      p3   a3*p2+p1            pn   a_n*p_n-1+p_n-2
__ = _ and __ = __ then  __ = ________ then __ = ________ .. then .. __ = _______________
q0   0     q1   1        q2   a2*q1+q0      q3   a3*q2+q1            qn   a_n*q_n-1+q_n-2

and every next p_x/q_x yields a better appoximation to the result.

Say if you are given a decimal like 1.425 in continued fraction cefficients as

[1; 2, 2, 1, 5]

a.k.a.

          1
1 + _____________
            1
    2 + _________
              1
        2 + _____
                1
            1 + _
                5

Then the intermediate convergents calculated as described above would be;

1    1    3    7    10    57
_ -> _ -> _ -> _ -> __ -> __ = 1.425
0    1    2    5    7     40

Notice that each convergent overshoots up and down from the final result subsequently besides 57/40 being the minimal rational expression of 1.425.

Continued fractions are a very deep topic which in fact eliminates the floating point error once an arithmetic is establised among them in their continued fractions form.

You can play here.