27
\$\begingroup\$

I come from a C background and have now just begun C++. This also means that I am not focussing on the algorithm, but more on C++ idioms.

Description:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

main.cpp:

#include <iostream>

#define UPPER_BOUND 1000

int main() {
    int sum = 0;

    for (int i = 1; i < UPPER_BOUND; ++i) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }

    std::cout << "The sum of the natural numbers below " << UPPER_BOUND << " that are multiples of 3 and 5 is " << sum;

    return 0;
}

I will add files to GitLab here and make changes to them as I receive feedback. Feel free to make changes to existing solutions.

\$\endgroup\$
  • 7
    \$\begingroup\$ Its worth mentioning that Project Euler focuses very heavily on mathematical algorithms. One of the other programming challenge sites might suit you better. codekata.com or hackerrank.com to name a few. \$\endgroup\$ – bruglesco Jun 21 '18 at 16:23
  • \$\begingroup\$ @bruglesco I realized that Project Euler is focussed on algorithms after completing the first challenge and looking ahead. I will do the code challenges from codekata.com for my next review. \$\endgroup\$ – FromTheStackAndBack Jun 22 '18 at 4:58
  • 5
    \$\begingroup\$ To add to @bruglesco's comment, adventofcode.com has language-agnostic puzzles that I find to be a great way to get to know a language, as it'll force you to use a wide variety of techniques and tools. \$\endgroup\$ – ZeroKnight Jun 22 '18 at 10:25
31
\$\begingroup\$

constexpr everything

Apart from the #define, your code is quite good. But you miss on a really simple optimization by not using constexpr, which has different meanings in different contexts:

constexpr variables are compile-time constants. They're a good replacement for constant defining macros.

#define UPPER_BOUND 1000 // bad, because preprocessing leads to a lot of bugs
constexpr int upper_bound = 1000; // good, safe

constexpr functions can be executed at compile-time if their arguments are known at compile-time; the compiler will then substitute a constant to the function call in the code.

So let's extract a function from your main() and declare it constexpr:

constexpr int sum_of_multiples_of_3_and_5_under(int upper_bound) {
    int sum = 0;
    for (int i = 1; i < upper_bound; ++i) {
        if ( i % 3 == 0 || i % 5 == 0 ) {
            sum += i;
        }
    }
    return sum;
}

Now, whenever you call it with an upper_bound you know at compile-time, it will run at compile-time.

Generalize your code

Running your function at compile-time means a lot, because if you can't and need your code to run fast at run-time, you'll have to implement better algorithms. As @Dannnno pointed out, you could have used the algorithm to compute an arithmetic progression, which is O(1) instead of O(n) for your code:

constexpr int sum_multiples_under(int ratio, int upper_bound) {
    int nb_val = (upper_bound - 1) / ratio;
    int high = nb_val * ratio;
    int extremes = ratio + high;
    return nb_val * extremes / 2;
}

You can then compute the sum of the multiples of 3 and 5 with:

auto sum = sum_multiples_under(3,  1000)
         + sum_multiples_under(5,  1000)
         - sum_multiples_under(15, 1000);

It's quite easy to implement, even if it consumes a bit more brain-power than the for-loop. But let's say that we want to generalize our code, and make it work for any number of divisors, for instance the sum of the multiples of 3, 5 and 7. Then it becomes a lot harder: you have to add all members of one set, then subtract all members of two sets, then add all members of three sets... etc. That means computing combinations, applying functions to arrangements, etc. Whereas our for-loop scales quite comfortably.

Use fold expressions

With fold expressions (which require C++17), you can generalize your code fairly easily:

template <typename... Multiples>
constexpr int sum_of_multiples_under(int upper_bound, Multiples... multiples) {
    int sum = 0;
    for (int i = 1; i < upper_bound; ++i) {
        if ( ( ... || (i % multiples == 0)) ) {
            sum += i;
        }
    }
    return sum;
}

Multiples is a variadic template parameter. It can stand for any number of arguments. You can then expand the arguments' pack inside your function. Fold expressions allow you to expand it around an operator. In this case, the operator is ||. ( ... || (i % multiples == 0)) will be expanded into:

   (i % multiples_1 == 0)
|| (i % multiples_2 == 0)
|| ...
|| (i % multiples_N == 0)

Conclusion

constexpr is a really, really useful keyword, and is a sign of modern, optimized C++ code. Use it without moderation. If you want to know everything about it, there's a keynote on YouTube named "constexpr everyting".

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you referring to "constexpr ALL the Things"? \$\endgroup\$ – Rakete1111 Jun 21 '18 at 14:29
  • \$\begingroup\$ It's quite possible, I don't remember the exact title \$\endgroup\$ – papagaga Jun 21 '18 at 14:38
  • \$\begingroup\$ fold expressions are definitely new to me! I will take a closer look at them soon. \$\endgroup\$ – FromTheStackAndBack Jun 22 '18 at 5:08
  • \$\begingroup\$ Before you posted this answer, I was going to generalize the code by storing all modulo values in a vector and iterating through them in an if statement. I think your solution is much more cleaner than mine. \$\endgroup\$ – FromTheStackAndBack Jun 22 '18 at 5:09
  • 4
    \$\begingroup\$ "bad, because preprocessing leads to a lot of bugs" You should probably not do that preprocessing and only resort to the bug-free one. \$\endgroup\$ – bipll Jun 22 '18 at 5:50
28
\$\begingroup\$

I am not focussing on the algorithm, but more on C++ idioms.

Very good statement of what you want out of this. Great!

I suggest you familiarize yourself with the Core Guidelines being cataloged by Bjarne Stroustrup and Herb Sutter.

#define UPPER_BOUND 1000

Don't use #define for constants or "functions" (⧺ES.31).

This is one of the first things ancient C++ brought to the table! Instead of #define with all its problems, we got const and inline.

The loop itself is sound enough, even using the prefix increment. You would need additional (non-std) libraries to write that neater using a range-for.

But, you should not write the loop at all! Stroustrup’s videos will say: “Don’t ‘write code’ — use algorithms.” You want count_if, because you are asking “how many items satisfy this predicate”. (update: On closer reading I see you are not counting but totaling. This is exactly the hazard of extracting the high level meaning from a low-level loop!) But again, you just have counting numbers not a collection to go through, which is not the normal case. std::generate_n will produce the list of numbers, but not in a form that can be fed to the algorithms! It pushes, while count_if pulls.

Writing the for loop, even the legacy form, is just so easy that it is hard to argue for doing it differently.

But with additional libraries: Boost.Range v2, or the upcoming Range.v3, it will be simple. Many programmers use Boost or have their own counting range (see my own tutorial and the cartoon that goes with it ☺).

So, with library in hand, I might write something like:

auto r = int_range (1, upper_bound);
auto wanted = [](int i){return (i % 3 == 0 || i % 5 == 0); }
auto sum= accumulate (r|filtered(wanted));

Since the actual work here, sum+=i is so trivial that any elaboration on it makes it more code. But imagine a more realistic complex situation in business logic. The algorithm, accumulate, is named for what you are doing. The selection criteria is isolated in its own statement and named wanted, so it is easier to edit the logic later without breaking anything.

The two issues here are that the desired idioms are leading ahead of proper library/compiler support; and with a trivial program it seems artificial and convoluted to put any formal structure or “high engineering” around it.


What might be useful is to verify that your sum does not overflow. That’s something that I eyeballed when reviewing, so a comment to the effect that you considered that is a good idea.

// sum will be a subset of the sum of all numbers in the range,
// so must be < (n+1)*(n/2) ≈ 500'000, which is well within the range
// of a 32-bit int.
\$\endgroup\$
  • \$\begingroup\$ I like this style of coding. But can it be constexpred? Just adding constexpr in front of OP's code is enough to make it compile-time computable, that's an advantage you shouldn't give up only for coding style. \$\endgroup\$ – papagaga Jun 21 '18 at 10:56
  • \$\begingroup\$ Great answer! But I would argue that multipleOf3or5 is a better name for the filter than wanted. \$\endgroup\$ – Alex Reinking Jun 21 '18 at 18:29
  • \$\begingroup\$ Range V3 isn't "upcoming." It's already out. It's already a library.s You may be referring to the Ranges TS \$\endgroup\$ – Justin Jun 21 '18 at 19:30
  • \$\begingroup\$ @Justin I was referring to availability, usability, and widespread adoption. It will not work on Microsoft's compiler still, and has difficulties with error messages so a non-expert will have trouble using it, and various compiler nits. \$\endgroup\$ – JDługosz Jun 22 '18 at 6:42
4
\$\begingroup\$

Your coding style could be cleaner; it would be nice to break it up into a function, like so:

#include <iostream>

#define UPPER_BOUND 1000

int sum_of_sequence(int first_multiple, int second_multiple, int max_value)
{
    int sum = 0;
    for (int i = 1; i < max_value; ++i) {
        if (i % first_multiple == 0 || i % second_multiple == 0 ) {
            sum += i;
        }
    }
}

int main() {
    int sum = sum_of_sequence(3, 5, UPPER_BOUND);
    std::cout << "The sum of the natural numbers below " << UPPER_BOUND << " that are multiples of 3 and 5 is " << sum;
    return 0;
}

This has the added benefit of making it more configurable if you decided you wanted to use a different set of numbers.


I don't like that you're #defineing a constant, because you could really just make something const or constexpr - there is a difference between the two, but it doesn't matter here. Depending on the version of the C++ standard you're compiling against, you might be able to get the work done at compile-time if you use constexpr appropriately.


You could start the loop at the lowest multiple, and then increment from there; this will save you a handful of iterations.


You could have a much more clever algorithm. For an arithmetic sequence, the sum of the first \$ n \$ terms is $$ S_n = \frac{n(a_1 + a_n)}{2} $$

If we use that to compute the sum of the first 333 multiples of 3 and the first 199 multiples of 5 we'll get close to our answer (333 because the 334th multiple is greater than 1000, and the same logic for 199). The problem is that we'll have double counted things that are multiples of both 3 and 5, i.e. multiples of 15 (the least common multiple between 3 and 5). So if we were to compute this:

$$ \frac{333(3 + 999)}{2} + \frac{199(5 + 995)}{2} - \frac{66(15 + 990)}{2} $$

We would get our correct answer. You could express that with a few simple functions (probably simpler than they need to be, but this just shows the steps).

int num_multiples_below_max(int value, int max)
{
    return (max - 1) / value;
}

int largest_value(int value, count)
{
    return value * count;
}

int sum_arithmetic_sequence_below_max(int value, int max_value)
{
    return sum_arithmetic_sequence(value, num_multiples_below_max(value, max_value));
}

int sum_arithmetic_sequence(int value, int count)
{
    return count * (value + largest_value(value, count)) / 2;
}

int least_common_multiple(int a, int b)
{
    return a * b;
}

int sum_of_multiples_below_max(int first_multiple, int second_multiple, int max_value)
{
    int sum_first_multiple = sum_arithmetic_sequence_below_max(first_multiple, max_value);
    int sum_second_multiple = sum_arithmetic_sequence_below_max(second_multiple, max_value);
    int lcm = least_common_multiple(first_multiple, second_multiple);
    int sum_least_common_multiple = sum_arithmetic_sequence_below_max(lcm, max_value);

    return sum_first_multiple + sum_second_multiple - sum_least_common_multiple;
}

You can probably extend this to more than just 2 multiples, however I forget the exact algorithm and my Google-fu seems to be failing me at the moment. I'll leave that as an exercise to the user.

\$\endgroup\$
  • 6
    \$\begingroup\$ I think this is a bit of an overkill. I agree about code having to be generalized and expandable, but if you end up writing more than twice the lines of code (because you haven't got your main yet in there), you'd better have a real need for them. Also, OP specified more of an interest in C++ idioms rather than the algorithm. Your first piece of code looks a lot better and way more readable to me. \$\endgroup\$ – ChatterOne Jun 21 '18 at 7:27
  • \$\begingroup\$ I agree that it's overkill; as I mentioned this is split out into more functions than necessary. You can quite easily clean it up to take less space, but for the sake of explaining the algorithm I left it split up. \$\endgroup\$ – Dannnno Jun 21 '18 at 16:00
  • 1
    \$\begingroup\$ The way to extend it to more than two numbers would use std::lcm() from <numeric> to compute the least common multiple of the pairs of numbers, then the inclusion-exclusion principle to add the multiples of each number, subtract the multiples of the LCM of each pair of numbers, add back in the multiples of the LCM of each triple of numbers, and so on. \$\endgroup\$ – Davislor Jun 21 '18 at 22:25
  • \$\begingroup\$ @Davislor is correct, but note that the result takes time approximately Θ(2^k), where k is the number of "multiples", as opposed to approximately Θ(n k) for the naive version, where n is the upper bound of the sum. In this answer, we have k = 2, which is pretty clearly better in practice than a linear-time algorithm—but if you have 50 multiples and you're summing up to a million then you should take the naive algorithm. \$\endgroup\$ – wchargin Jun 21 '18 at 22:32
  • \$\begingroup\$ @wchargin Also note that you can still optimize the naive algorithm somewhat. For example, you can split the range into residues of the least common multiple of the factors. \$\endgroup\$ – Davislor Jun 21 '18 at 22:42
0
\$\begingroup\$

This is an error.

The task asks:

Find the sum of all the multiples of 3 or 5 below 1000.

But your program reports:

"The sum of the natural numbers below 1000 that are multiples of 3 and 5 is ..."

Your code calculates the correct sum, but that sum does not match what you say it represents!

This is a small optimization:

Given that the smallest of the two multiples is 3, you could start the for loop at 3 instead of at 1.

Obviously this doesn't save much here but just imagine a similar task that would deal with multiples of say 117 or 209.

for (int i = 3; i < UPPER_BOUND; ++i) {
    if (i % 3 == 0 || i % 5 == 0) {
        sum += i;
    }
\$\endgroup\$
  • \$\begingroup\$ It asks for or, not xor. "multiples of 3 and 5" are 0, 15, 30, ... \$\endgroup\$ – FromTheStackAndBack Jul 4 '18 at 3: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.