Please review my solution to Project Euler program 1

Question

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;
}

Answer 1

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;
}

Answer 2

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.

Answer 3

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;
}