Writing a function that calculates the sum of squares within a range in one line in C

Question

My try

double sum_squares_from(double x, double n){

    return n<=0 ? 0 : x*x + sum_squares_from((x+n-1)*(x+n-1),n-1);

}

Instead of using loops my professor wants us to write functions like this... What the exercise asks for is a function sum_squares_from() with double x being the starting number and n is the number of number. For example if you do x = 2 and n = 4 you get 2*2+3*3+4*4+5*5. It returns zero if n == 0.

My thinking was that in my example what I have is basically x*x+(x+1)(x+1)+(x+1+1)(x+1+1)+(x+1+1+1)(x+1+1+1) = (x+0)(x+0)+(x+1)(x+1)+(x+2)(x+2)+(x+3)(x+3) = (x+n-1)^2 repeated n times where n gets decremented every time by one until it becomes zero and then you sum everything.

Did I do it right?

(if my professor seems a bit demanding... he somehow does this sort of thing all in his head without auxiliary calculations. Scary guy)

Answer 1

It's not recursive, but it's one line:

int 
sum_squares(int x, int n) {
  return ((x + n - 1) * (x + n) * (2 * (x + n - 1) + 1) / 6) - ((x - 1) * x * (2 * (x - 1) + 1) / 6);
}

Sum of squares (of integers) has a closed-form solution for 1 .. n. This code calculates the sum of squares from 1 .. (x+n) and then subtracts the sum of squares from 1 .. (x-1).

Answer 2

^{The original version of this answer used ASCII art.}

So,

• ∑_i:0..n i = n(n+1)(½)
• ∑_i:0..n i² = n(n+1)(2n+1)(⅙)

We note that,

• ∑_i:0..n (x+i)²
  = ∑_i:0...n x² + 2xi + i²
  = (n+1)x² + (2x)∑_i:0..n i + ∑_i:0..n i²
  = (n+1)x² + n(n+1)x + n(n+1)(2n+1)(⅙)

Thus, your sum has the closed form:

double sum_squares_from(double x, int n) {
    return ((n-- > 0)
            ? (n + 1) * x * x
              + x * n * (n + 1)
              + n * (n + 1) * (2 * n + 1) / 6.
            : 0);
}

If I apply some obfuscation, the one-line version becomes:

double sum_squares_from(double x, int n) {
    return (n-->0)?(n+1)*(x*x+x*n+n*(2*n+1)/6.):0;
}

If the task is to implement the summation in a loop, use tail recursion. Tail recursion can be mechanically replaced with a loop, and many compilers implement this optimization.

static double sum_squares_from_loop(double x, int n, double s) {
    return (n <= 0) ? s : sum_squares_from_loop(x+1, n-1, s+x*x);
}

double sum_squares_from(double x, int n) {
    return sum_squares_from_loop(x, n, 0);
}

As an illustration, if you observe the generated assembly in GCC at a sufficient optimization level (-Os, -O2, or -O3), you will notice that the recursive call is eliminated (and sum_squares_from_loop is inlined to boot).

Try it online!

Answer 3

As mentioned in my original comment, n should not be type double, but instead be type int to avoid floating point comparison problems with n <= 0. Making the change and simplifying the multiplication and recursive call, you do:

double sum_squares_from(double x, int n)
{
    return n <= 0 ? 0 : x * x + sum_squares_from (x + 1, n - 1);
}

If you think about starting with x * x and increasing x by 1, n times, then the simple x * x + sum_squares_from (x + 1, n - 1) is quite easy to understand.

Answer 4

Maybe this?

double sum_squares_from(double x, double n) {
    return n <= 0 ? 0 : (x + n - 1) * (x + n - 1) + sum_squares_from(x, n - 1);
}