5
\$\begingroup\$

Can someone give me suggestions on how to improve this program?

The objective is to find the sum of all the multiples of 3 or 5 below 1000.

#include <stdio.h>

main()
{
    int S, s3,s2,S1;
    int a=333,b=3,c=999, i=5,j=995, k=199, m = 15, n= 66, o= 990;
    S1= a*(b+c)/2;
    s2= k*(i+j)/2;
    s3= n*(m+o)/2;
    S= S1 + s2 - s3;
    printf("sum is:%d",S);
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ provide a link to the problem, or describe the problem. Some of us don't know what project Euler is. \$\endgroup\$ – Olayinka Sep 10 '13 at 11:56
  • 4
    \$\begingroup\$ You may take a look at this similar post from another user. \$\endgroup\$ – Jamal Sep 10 '13 at 12:11
2
\$\begingroup\$

You certainly got the point of the problem. You applied Inclusion-Exclusion principle. Your code works well too. Most of the operations you use are constant time operations and can't be optimized further. The only problem is code formatting. Every coder develops a coding style that suites him or herself, but when you code, always remember that your code can fall into someone else's hand one day and you don't want the person to suffer before understanding your code.

  • A comment at the beginning of the code will be good. Not just for a third party reader, but you. You may open the code in another decade, you don't wanna have to go to project Euler's site before you understand what your code does.
  • Naming variables, your variables name should reflect its meaning. And you initialized way too many variables on the same line. Funny enough those variables are pointless. You can just use their values immediately in S1, S2 and S3.
  • Spacing also is important, not for the compiler of course but for you or whoever is reading this code.

This is how I would have done it;

#include<stdio.h>

/* Function to find the sum of the multiples
of a OR b between 1 and N, excluding N */ 

int findSum(int a, int b, int N){
    N--;
    int a_n = (N/a)*a,
        b_n = (N/b)*b,
        ab_n = (N/(a*b))*a*b,
        sum_a = ((N/a) * (a + a_n))/2,
        sum_b = ((N/b) * (b + b_n))/2,
        sum_ab = ((N/(a*b)) * (a*b + ab_n))/2;
    return sum_a + sum_b - sum_ab;
}

int main(){
    int a = 3, b = 5, N = 1000;
    printf("%d", findSum(a, b, N));
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Ideone reports a runtime error (but still gives the correct output). \$\endgroup\$ – Jamal Sep 10 '13 at 13:18
  • 1
    \$\begingroup\$ You say that yashika initialised too many variables on one line, but they were simple initialisations. On one line you have int a_n = (N/a)*a, b_n = (N/b)*b, ab_n = (N/(a*b))*a*b; which is harder to read/understand. \$\endgroup\$ – JohnMark13 Sep 10 '13 at 13:25
  • \$\begingroup\$ @JohnMark13 really? well spaced initialization of three variables is hard to read? \$\endgroup\$ – Olayinka Sep 10 '13 at 13:29
  • 2
    \$\begingroup\$ @Jamal I missed return 0 \$\endgroup\$ – Olayinka Sep 10 '13 at 13:29
  • 1
    \$\begingroup\$ @Olayinka, well spaced perhaps, but they're 'complex' in the sense that they involve various operators and parentheses. Additional commas are easy enough to miss. Also, it's inconsistent with the two separate lines you use for sum_a and sum_b. By the same logic they would happen on the same line as all *_n variables. \$\endgroup\$ – Elmer Sep 10 '13 at 13:33
2
\$\begingroup\$

Your solution is good (and fast) because it uses a mathematical calculation over the more naive looping solutions. However...

I second @Olayinka comments about readability, but I'd go much further with understand-ability. The variable names and equations don't really express what they are doing. Also, violations of the DRY principle exist because although there are 6 equations, they are really 3 sets of the same two equations. I'd factor them into a function and give the variables names that mean what they are (disclaimer: I don't claim to have gotten the semantics right in sumMultiples below). Then I'd implement the OR concept as another function that clearly expresses what it is doing.

#include <stdio.h>

///////////////////////////////////////////////////////////
// Find the sum of the multiples of a divisor 'd' in
// the range [1, N).
// TODO: Include a reference as to why this math works. 
int sumMultiples (int N, int d)
{
    N--;
    int nMultiples = (N / d);
    int maxMultiple = nMultiples * d;
    int sum = nMultiples * (d + maxMultiple) / 2;
    return sum;
}


///////////////////////////////////////////////////////////
// Find the sum of the multiples of divisors d1 OR d2
// in the range [1, N).  Uses Inclusion-Exclusion
// principle.
int sumMultiplesOR (int N, int d1, int d2)
{
    int sumOR = sumMultiples(N, d1)
              + sumMultiples(N, d2)
              - sumMultiples(N, d1*d2);

    return sumOR;
}


int main(){
    int d1 = 3, d2 = 5, N = 1000;
    printf("%d", sumMultiplesOR(N, d1, d2));
    return 0;
}

I can here the performance folks saying "but the function call overhead!". Nonsense. Always prefer correctness and readability over all else until you really need it. Incidentally, I complied this in Release mode using VC++ 11 (VS2012) and the compiler optimized away both functions, and calculated the solution to the problem at compile time! The resulting assembly was essentially:

push  233168
push  <format-string>
call  printf
ret   0

I can also hear the 'minimal typists' saying 'but that's so much more code!'. Also nonsense. Too bad. More people will read the code than will type it. Most good coders I know are also good typists.

\$\endgroup\$
  • \$\begingroup\$ I hope any real "performance folks" know that compilers aggressively inline functions small, and that constant propagation can happen after inlining. A compiler that didn't do that wouldn't be worth using! I would suggest making the helper static inline though, to make sure the compiler knows it doesn't have to emit a stand-alone definition of the function. Otherwise that's only possible with LTO (which you should use). And (in case you're compiling this into a Unix shared lib) that symbol interposition can't override it, so inlining into a caller in the same file is still allowed. \$\endgroup\$ – Peter Cordes Jun 28 at 2:59
2
\$\begingroup\$

I wouldn't call this a programming solution to the puzzle; it's more of a program that happens to print the correct result. Basically, you've already solved the problem, and are using the computer as a fancy calculator. You might as well do the work on a two-dollar calculator that you can buy at the corner store.

There are, of course, situations where you have to apply a certain amount of ingenuity in order to translate the problem into an algorithm to be implemented. For example, when factoring numbers, it's common to only try odd factors, knowing that 2 is a special case. At some point, though, you have to decide how much work to do in the programmer's brain vs. how much work to give to the CPU. How to make the tradeoff will be guided by your desire for fast runtime performance vs. the elegance of the code.

In this case, a modern computer can solve this problem by "brute force" in almost the same amount of time as your "smart" summation using the inclusion-exclusion principle. Here's how a brute-force solution would look like:

#include <stdio.h>
int main() {
    int sum = 0;
    for (int i = 0; i < 1000; i++) {
        if ((i % 3 == 0) || (i % 5 == 0)) {
            sum += i;
        }
    }
    printf("sum is: %d\n", sum);
    return 0;
}

It expresses the problem exactly as stated. There is no room for programming error, no mysterious constants, no formulas. If the requirements change (for example, to find the sum of all multiples of 3 or 7 below 10000), it's trivial to adjust the program. The engineering trade-off definitely favours simplicity over runtime performance. (If it takes you more than one second to write the cleverer code, you've already lost!)


As I said, though, there are times when human ingenuity has to be built into the program, usually because a brute-force solution cannot yield acceptable performance. In those situations, your job as a programmer is to express the shortcuts while sacrificing as little code maintainability as possible.

One trick is to let the preprocessor and compiler do the work. The proposal below is much more readable and flexible than your original. In fact, if you inspect the assembler output, you'll see that this solution generates identical code to your original solution. Both of them embed the answer right into the executable as a constant!

#include <stdio.h>

#define COUNT_MULTIPLES(m, limit) (((limit) - 1) / (m))
#define MIN_MULTIPLE(m, limit) (m)
#define MAX_MULTIPLE(m, limit) (COUNT_MULTIPLES(m, limit) * (m))
#define SUM_MULTIPLES(m, limit) (COUNT_MULTIPLES(m, limit) * \
                                 (MIN_MULTIPLE(m, limit) + MAX_MULTIPLE(m, limit)) / 2)

int main() {
    int limit = 1000;
    int sum_mult_3 = SUM_MULTIPLES(3, limit);
    int sum_mult_5 = SUM_MULTIPLES(5, limit);
    int sum_mult_15 = SUM_MULTIPLES(15, limit);

    /* Sum using the inclusion-exclusion principle */
    int sum = sum_mult_3 + sum_mult_5 - sum_mult_15;
    printf("sum is: %d\n", sum);
    return 0;
}

Everything is named to enhance understanding. Repetition of code (the summation formula) is eliminated. Best of all, no magic numbers!


Update: Actually, you don't have to use preprocessor macros to get good performance. If you write the macros as functions instead, clang -O2 and gcc -O2 will both do the entire calculation at compile time, exactly as with preprocessor macros.

Considering the problems with macros (lack of type safety and re-evaluation of arguments), I think that changing them to functions is a better solution.

/* Compilation with optimization level -O2 or better is suggested */

#include <stdio.h>

int count_multiples(m, limit) {
    return (limit - 1) / m;
}

int min_multiple(m, limit) {
    return m;
}

int max_multiple(m, limit) {
    return count_multiples(m, limit) * m;
}

int sum_multiples(m, limit) {
    return count_multiples(m, limit) * (min_multiple(m, limit) + max_multiple(m, limit)) / 2;
}

int main() {
    int limit = 1000;
    int sum_mult_3 = sum_multiples(3, limit);
    int sum_mult_5 = sum_multiples(5, limit);
    int sum_mult_15 = sum_multiples(15, limit);

    /* Sum using the inclusion-exclusion principle */
    int sum = sum_mult_3 + sum_mult_5 - sum_mult_15;
    printf("sum is: %d\n", sum);
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Indeed, inlining and constant-propagation are very powerful optimizations for code that's written generically and then called for specific use-cases with some or all args being constants. Of course for compile-time-constant loop bounds, a compiler will hopefully fully unroll and optimize away even the dumb brute-force loop, but that doesn't always happen if the heuristic thresholds aren't high enough. \$\endgroup\$ – Peter Cordes Jun 28 at 2:51

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.