4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ In general, if you have an assignment from something (teacher, book, boss) and you want to do it a very different way from the way that was suggested, make sure it's okay, first. Ask your boss why he needs you to use for loops when a while would be easier to understand. Maybe there's an old macro that causes while loops to bug out, and the temporary work around is to use a for. (I wish that wasn't a true story.) \$\endgroup\$ – Nic Hartley Aug 27 '17 at 16:34
  • \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 Aug 29 '17 at 19:16
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Minor: "by about five to six numbers" is unclear. \$\endgroup\$ – chux Aug 28 '17 at 16:54
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ There's an intermediate solution zakres * (zakres + 1) / 2 * (2 * zakres + 1) / 3, but that only buys one bit of range; to get the full range, we need to compute all three multiplicands and divide one of them by 2 and divide one of them (possibly the same one) by 3 before multiplying. \$\endgroup\$ – Toby Speight Aug 29 '17 at 13:56
  • \$\begingroup\$ @TobySpeight Perhaps a ponderous (2 * zakres + 1)%3 ? (zakres * (zakres + 1) / 6 * (2 * zakres + 1)) : (zakres * (zakres + 1) / 2 * ((2 * zakres + 1) / 3));? \$\endgroup\$ – chux Aug 29 '17 at 14:28
  • \$\begingroup\$ I was thinking more of breaking into separate expressions and some if/else statements - too long for a comment; I'll write an answer. \$\endgroup\$ – Toby Speight Aug 29 '17 at 14:40
2
\$\begingroup\$

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. Performance

\$\endgroup\$
  • 1
    \$\begingroup\$ Theunsigned idea is good, yet too late. unsigned int numerator = (n * (n + 1)) * (2 * n + 1); assigns an int to an unsigned for no benefit. I'd recommend to use unsigned int sumSquares(unsigned int n) and drop the unneeded if (n <= 0) test. \$\endgroup\$ – chux Aug 28 '17 at 15:52
  • 1
    \$\begingroup\$ The statement that there is no performance difference between the two approaches is premature. I understand that you've measured it once, and one measurement is not enough to determine it. Also, the difference may be negligible for small n, but I can imagine that in case of n being of the order of million, execution time will differ significantly. \$\endgroup\$ – KjMag Aug 29 '17 at 11:34
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Nice c <= n for detecting OF in b,c. Yet since 0 is a proper response to sum_squares_to(0), perhaps consider an alteration value or approach to signal OF? \$\endgroup\$ – chux Aug 29 '17 at 17:15
  • \$\begingroup\$ You're right, @chux - I just threw in something to make the point that checking for errors is a good thing. I've now changed it so that it sets errno appropriately (though, unlike library functions, it clears errno on success - that's an arguable choice). If zero is returned, we can still distinguish between sum_squares_to(0) and sum_squares_to(ULONG_MAX). \$\endgroup\$ – Toby Speight Aug 30 '17 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.