Calculating sum of squares in C

Question

I wrote some program in C language. I have to calculate sum of squares. My book suggested me to use loops but I chose more efficient way by using formula:

$$1^2+2^2+\cdots+n^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$$

Original code from listing 5.13:

#include <stdio.h>

int main(void) {
    int licznik, suma;

    licznik = 0;
    suma = 0;
    while (licznik++ < 20)
        suma = suma + licznik;
    printf("suma = %d\n", suma);
    return 0;
}

Finally, this is my code:

#include <stdio.h>

int main(void) {
    int zakres;
    printf("Podaj zakres przeprowadzanych obliczen:\n");
    scanf("%i", &zakres);
    printf("suma kwadratow = %d\n", (((zakres * (zakres + 1)) * (2 * zakres + 1)) / 6));
    return 0;
}

What do you think about this solution? Is it more efficient than loops?

Answer 1

Well, I can't say much about your naming, as I cannot read it. For a wider audience than a purely local team - and probably even then - consider switching to english.

What I can tell is that you are very generous with parentheses. Using them everywhere actually reduces readability, you know?

Next, congratulations for working smarter instead of harder, it really pays in speed.
Though there is a down-side to your implementation of the modified algorithm: It encounters Undefined Behavior due to integer-overflow slightly before the brute-force-one does (by about five to six numbers). Why are you using signed arithmetic anyway?

And then you assume the programs input is always well-formed. You know scanf() can fail? So, test the return-value.

Answer 2

I have to calculate sum of squares

Over what range?

---

The original code (corrected suma = suma + licznik*licznik;) can be simplified to:

puts("suma kwadratow = 2870");

Yet it that the goal? Work fast over a limited range of just 20? - not likely.

---

The formula approach ((zakres * (zakres + 1)) * (2 * zakres + 1)) / 6 is faster than a loop for some inputs.

Yet the fast method calculates the wrong answer for 1024 and above (Assume 32-bit int) whereas the slow method works up to 1860.

So code has traded speed for reduced range. Yet is that the goal?

---

Code could use double for a much wider range to about 1,000,000, yet lose precision beyond that.

---

The point is that to rate if code is good, the coding goals need to be determined and presented. Otherwise the formula code can simply create the wrong answer faster.

Answer 3

Firstly the example you provided form the book does not calculate the sum of n squares. I have corrected the code:

#include <stdio.h>

int main(void) {
    int licznik, suma;

    licznik = 0;
    suma = 0;
    while (licznik++ < 10)
        suma = suma + (licznik*licznik);
    printf("suma = %d\n", suma);
    return 0;
}

Now your code. I would create a separate function for the formula called sumSquares. And inside the function you can split the calculation into two variables for the numerator (Polish: licznik) and denominator (Polish: mianownik). I assume the range (Polish: zakres) can be only positive, if so I would use unsigned int and check at the beginning if the entered range (n) is positive.

unsigned int sumSquares(unsigned int n) {
    unsigned int numerator = (n * (n + 1)) * (2 * n + 1);
    unsigned int denominator = 6;
    return numerator / denominator;
}

Now as you see it is more readable and it can be used easier.

#include <stdio.h>

unsigned int sumSquares(unsigned int n) {
    unsigned int numerator = (n * (n + 1)) * (2 * n + 1);
    unsigned int denominator = 6;
    return numerator / denominator;
}

int main(void) {
    int range = 20;
    printf("Sum: %u\n", sumSquares(range));
    return 0;
}

Performance

I think that not using loops should result in better performance and better efficiency. However, if it comes to speed there is no difference at all. Modern computers are so fast, that seriously it does not matter. I think that we should firstly determine the quality of code by comparing its readability and maintainability.

Answer 4

So your code is fine. I mostly agree with what @Deduplicator wrote. (I tend to like more parens than other programmers, but I do think you could remove the outermost set.) You've reduced the problem from being O(n) to being O(1). That's a really nice speed-up!

The problem is that you haven't done what the client (teacher) has asked. While I would argue that your solution is objectively better, it doesn't do one thing that was required (use a loop) and does one thing that wasn't specified (gets the input value from the user). I don't know your teacher, so I don't know if they'll care, but I have dealt with clients that had very specific requirements and it usually is a good idea to follow them and discuss with them why another solution would be better before implementing it. Presumably your teacher wanted you to use a loop because they wanted you to have practice writing and using loops!

Also, if you are going to get input from the user, you should validate it. Currently if the user types a nonsensical value like "abc$%." the results will be invalid.

Answer 5

The multiplication of the numerator is subject to overflow.

To avoid this, we can divide the multiplicands by 6 before multiplying them together. We can infer that exactly one of the three is a multiple of 3; similarly, one of the first two must be a multiple of 2. So we need to divide one value by 3, and also divide one value by 2 (this will be the same value, if n is a multiple of 6):

#include <limits.h>
#include <stdio.h>
#include <errno.h>

unsigned long sum_squares_to(unsigned long n)
{
    unsigned long a = n;
    unsigned long b = n + 1;
    unsigned long c = n + n + 1;

    if (c <= n || 1.0 * a * b * c / 6 > ULONG_MAX) {
        errno = ERANGE;
        return 0;
    } else {
        errno = 0;
    }

    /* exactly one of a,b,c is a multiple of 3 */
    switch (a % 3) {
    case 0:
        a /= 3; break;
    case 1:
        c /= 3; break;
    case 2:
        b /= 3; break;
    }

    /* exactly one of a,b is a multiple of 2 */
    if (a % 2)
        b /= 2;
    else
        a /= 2;

    return a * b * c;
}

int main(void)
{
    unsigned int zakres = 20;
    unsigned long sum = sum_squares_to(zakres);
    if (!sum) {
        fprintf(stderr, "Could not sum squares to %u\n", zakres);
        return 1;
    }
    printf("suma kwadratow = %ld\n", sum);
    return 0;
}

I've also increased the range to unsigned long int, which may have a bigger range, depending on your target platform.

This is a good lesson in taking results from pure mathematics and expressing them in a program: real-world mathematical numbers don't have the same limitations on precision and range that computer numbers do, and we often have to adapt our algorithms to work well with their machine representations.

BTW, this approach is probably not acceptable for your homework if it prescribes that you must use a loop for the calculation, but it is a valuable learning opportunity, so it's good that you explore this other approach and discover something your teacher hasn't put in front of you; I find that the most effective way to learn, and perhaps you do too. Happy programming!