Sum of squares

Question

Sum of squares

Navigation

#1 by (2 votes)
#2 by (2 votes)

1

I've been doing a function to calculate 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 function type for the sum of the squares, to compute the sum x ^ 2 (x + 1) ^ 2 + ... + (x + n-1) ^ 2, for xen data, but I'm not getting how to get to this function: /

c

asked by anonymous 29.09.2014 / 00:46

2 answers

verification function always returning true Get the value of a TD tag by jquery and send to method in Controller

score 2 · Answer 1

This is a recursive function that calculates 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 it 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);
}

score 2 · Answer 2

You can use it without recursion, because the computational time will be much smaller, below it 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 processing so that it can continue where it left off after the completion of each new run 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 available space for the control flow is generally much smaller than the space available in the heap, and recursive algorithms tend to require of more space in the stack than iterative algorithms.

It is important to mention that this iterative solution requires two temporary variables (counting with i) and will still spend less than the recursive execution time; in general, recursive algorithm formulations are often considered "leaner" or "smarter" than iterative formulations.