Sum of squares

Asked

Viewed 1,183 times

1

I’ve been doing a function to compute the sum of the first number (x0) with the ratio (r) by multiplying by a number (n) of times, like this function:

double sum_arithmetic(double x0, double r, int n)
{
   return n == 0 ? 0 : x0 + sum_arithmetic(x0 + r, r, n-1);
}

for example when x0=6, r=3, n=3 the result is 27 because it is 6 + 9 + 12, but now I want the same kind of function for the sum of squares, to compute the sum x 2 + (x+1) 2 + ... + (x+n-1) 2 , for x and n data, but I’m not getting how to get to that function :/

c
  • 3

    I don’t know if I got your question right, but if the problem is the square, x² is the equivalent of x*x. If you want to keep the recursive form just replace x0 + sum_arithmetic(x0 + r, r, n-1); for x0 * x0 + sum_arithmetic(x0 + r, r, n-1);

  • thank you very much, that was it!

  • @Brunorodrigues +1 for the problem, nice to see these problems involving p.a

2 answers

2

This is a recursive function that computes the sum of the term-to-term arithmetic progression (x, x + r, x + 2r, etc). The sum of the squares follows the same structure, the only difference is that in each recursive step should be computed x² (x0 * x0).

double sumOfSquares(double x0, double r, int n)
{
   return n == 0 ? 0 : x0 * x0 + sumOfSquares(x0 + r, r, n-1);
}

2

You can use without recursion, because the computational time will be much smaller, below is implemented iteratively:

double quadrado(double x0, double r, int n)
{
   int resultado = 0;
   for(int i = 0; i<n ;i++)
    {
         resultado = resultado + (x0+r*i)*(x0+r*i);  
    }
   return resultado;

}

Iterative implementation usually tends to be slightly faster in practice than recursive implementation, since a recursive implementation needs to record the current state of the processing so that it can continue where it left off after the completion of each new subordinate execution of the recursive procedure. This action consumes time and memory.

Another possible motivation for choosing an iterative algorithm rather than a recursive algorithm is that in modern programming languages the space available for the control flow is usually much smaller than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

It is important to mention that this iterative solution requires two temporary variables (relying on i) and will still spend less execution time than recursive; in general, recursive formulations of algorithms are often considered "leaner" or "more elegant" than iterative formulations.

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.