Compute the sum of even numbers between two values

Question

Recently I was watching two YouTube videos criticizing a function which sums the even elements in an inclusive range, the original function looks like this:

int calculate(int bottom, int top) {
    if (top > bottom) {
        int sum = 0;
        for (int number = bottom; number <= top; number++) {
            if (number % 2 == 0) {
                sum += number;
            }
         }
         return sum;
     } else {
         return 0;
     } 
} 

original source video

While I agree the original function could be formatted better with less indentation and early returns, it seems the solutions proposed in C++, Rust & Haskell are making heavy use of their variations of .filter & .reduce like functional programming which seems like a lot of overhead for something like this...

Which led to me spending a bit too much time writing the following functions, with the intent to make the function blazingly fast, more concise and removing all layers of nesting (as intended by the source video).

The Math Approach

I remember learning a math formula for summing numbers in a sequence which I looked up for quick refresher, and found an even better solution for summing only even numbers:

n • (n + 1)

Where n is the number of numbers in the range. My initial attempts at just subtracting the total sum of evens from the top and bottom failed (more on this later), which led me to trying a different formula:

and after a bit more time than I like to admit, I arrived at the following solution:

int sumOnlyEvenNumbersInRange(int bottom, int top) {
    int x = bottom + (bottom & 1);   // next even if odd
    int y = top + (top & 1);         // previous even if odd
    return (y - x + 2) * 0.25 * ((x ^ y) + ((x & y) << 1));
}

Which I'll admit looks a lot worse than it really is, but was the product of me combing the math terms and then substituting bitwise operators where applicable. The issue I realized I encountered earlier is that when bottom is odd we need to start the sequence at the next even and likewise if top is odd we need to end at the previous even number. After discovering this I revisited my first attempt, and finally got the following to work:

int sumOnlyEvenNumbersInRange(int bottom, int top) {
   int x = (bottom + (bottom & 1)) >> 1;
   int y = (top - (top & 1)) >> 1;
   return y * (y + 1) - x * (x - 1);
}

Which to be honest I'm pretty happy about, even though I still dream of an inline function. Anyways, I would be pretty upset if I saw this in a code-review the way it is and I realize it still doesn't account for when top < bottom, so here is the finalized version:

int sumOnlyEvenNumbersInRange(int bottom, int top) {
    if (bottom > top) return 0;             // edge case
    int x = (bottom + (bottom & 1)) >> 1;   // first even number in range divided by 2
    int y = (top - (top & 1)) >> 1;         // last even number in range divided by 2
    return y * (y + 1) - x * (x - 1);       // difference of evens between x and y
}

I know it isn't the most readable code, but that wasn't really the goal here. This won't be used in production and is just for fun, so I'm pretty happy with it, but it would be awesome if there was a way to

1. Handle the first / last even in range more elegantly.
2. Inline the entire function.

Answer 1

The first implementation mixes integer and floating-point arithmetic. I definitely would avoid that.

The other two versions both use >> on a signed type (int), which is implementation-defined behaviour, so not a good choice for a portable program. Consider % 2 and / 2 instead of using bitwise operations, but remember which direction signed division rounds towards.

I think that testing bottom > top before applying the adjustment to make both numbers even is a mistake, and I think it causes erroneous results when bottom and top are the same odd value (which should return 0 as result).

In all cases, I would recommend adding a set of unit tests to ensure the correct results are returned. Make sure the tests include at least the following:

• an empty range
• a single even number
• a single odd number
• a range beginning with a positive even number
• a range beginning with a positive odd number
• a range beginning with a negative even number
• a range beginning with a negative odd number
• a range ending with a positive even number
• a range ending with a positive odd number
• a range ending with a negative even number
• a range ending with a negative odd number
• a range that includes 0

To answer your specific questions:

1. I don't think it can be much more elegant. You might choose to simply adjust the parameter values (with += or -=) rather than declaring new variables.

2. Any decent optimising compiler will inline such functions whenever the benefit is worth the cost. The whole point of high-level languages is to let the machine take such decisions rather than requiring the programmer to do so.

Answer 2

The Math

Pardon if you already know this, but: the usual way to solve for a closed-form solution for a series like this is to note that the sum of a series that grows at a linear rate will be quadratic. Since a quadratic sequence has three unknowns, take three terms of the sequence (such as m₀ = 0, m₂ = 2, m₄ = 6) amd turn them into a system of three linear equations with three unknowns (such as a0² + b0 + c = 0, a2² + b2 + c = 2, a4² + b4 + c = 6) and solve the system for the coefficients a, b and c.

To actually prove this, we use induction: first prove the base case that, when f(x) = ax² + bx + c, f(0) = m₀. Then prove the inductive case, that if mᵢ = f(i) = i²/4 + i/2 - mᵢ (for an even value of i), f(i+2) = (i²+4i+4)/4 + (i+2)/2 = f(i) + i + 2 = mᵢ₊₂.

How are You Defining this?

Is the interval open-ended or closed-ended? Is the sum of all the even numbers between 3 and 3 zero and the sum of all the even numbers between 4 and 4, 4?

What About Negative Numbers

These are legal values to pass into your version of the function. Does your formula work on them?

If the domain is supposed to be positive numbers only, why not use an unsigned type? If the domain includes negative numbers, you need branches to use the correct formula for both endpoints, based on their signs.

Use Static Single Assignments

This is one functional-programming technique we can do in C or C++. Your algorithm isn’t supposed to ever modify any of the local variables, so making them all const will let the compiler catch a bug. In some cases, it can also allow optimizations that wouldn’t otherwise be possible.

Be Sure Twiddling Bits Actually Helps

Quite a lot of the old tricks that worked on twentieth-century CPUs and optimizers are useless, or actively counterproductive, today.

For example, the line

int x = (bottom + (bottom & 1)) >> 1;   // first even number in range divided by 2

compiles on Clang 15.0.0 with -std=c++20 -march=x86-65-v4 -O3 to

        mov     ecx, edi
        and     ecx, 1
        add     ecx, edi
        sar     ecx

which is a pretty literal translation of what you wrote. However, this formula doesn’t work for negative numbers (because right-shift of a negative number does not have well-defined behavior in C/C++, and different CPUs will do different things), and for a positive number, it is more efficient just to write (bottom+1)/2, which takes only two instructions instead of four and uses only one register instead of two.

So the clever bit-twiddling is very, very slightly worse than a simpler approach with regular arithmetic. Not really by enough to worry about, but you might as well use the code that’s both simpler and faster.

The next line is

int y = (top - (top & 1)) >> 1;

Fortunately, this time, the compiler sees that the bit-manipulation is useless, and compiles it to

        sar     esi

In other words, it sees that - (top & 1) is useless, and does not perform it at all. Note that this also does not give the correct results for a negative number—but the C++ language Standard technically says C++ programs are allowed to give you a wrong answer when you right-shift a negative number, and C compilers take advantage of loopholes like that. Very aggressively.

Don’t Return Magic Values as Error Codes

In real-world use, there is no possible reason why a program would ever, in any situation, want to check the return value of the function to see whether the left endpoint it just passed in is greater than the right endpoint. It could more efficiently compare them itself before the call instead. Not only that, it wouldn’t even be able to tell anything from the return value, because 0 could be either an error code or a valid possible result!

A better way to catch bugs like this is to assert that the arguments are not the result of a logic error, or otherwise abort the program if you detect one.

If you really, truly must return a magic number as an error code, at least return a magic value that could not possibly be a valid result, and give it a symbolic name. If you actually had to do this for some reason, you could define #define BAD_INTERVAL (-1), which can never be a valid sum of even numbers. Other approaches are to return a wider type than the valid results, where error results are out of range, or to pass the function a pointer to the location where it should write the result and have it return a success-or-error code.

Write Test Cases

Always write unit tests for your code! You’ll be glad you did.

Here is a version actually in the correct language. First, an updated function:

unsigned sum_evens_in_interval(const unsigned a, const unsigned b)
{
    assert (b >= a);

    const unsigned m = (a+1U)/2;
    const unsigned n = b/2;

    return n*(n+1) - m*(m-1);
}

Then, some test library:

#include <stdio.h>
#include <stdlib.h>

void expect_test_helper( const long long got,
                         const long long expected,
                         const char* const sourcefile,
                         const int line )
{
   if (got == expected) {
       printf("Test at %s:%d passed.\n", sourcefile, line );
   } else {
      fflush(stdout);
      fprintf( stderr,
               "Test at %s:%d FAILED:\nExpected: %lld\nGot: %lld\n",
               sourcefile,
               line,
               expected,
               got );
      exit(EXIT_FAILURE);
   }
}

#define expect_test(x, y) expect_test_helper( (long long)(x), (long long)(y), __FILE__, __LINE__ )

Which enables the following testcases:

int main(void)
{
    expect_test(sum_evens_in_interval(0, 0), 0U);
    expect_test(sum_evens_in_interval(3,3), 0U);
    expect_test(sum_evens_in_interval(4, 4), 4U);
    expect_test(sum_evens_in_interval(0,6), 12U);
    expect_test(sum_evens_in_interval(1,6), 12U);
    expect_test(sum_evens_in_interval(0,7), 12U);
    expect_test(sum_evens_in_interval(1,7), 12U);
    expect_test(sum_evens_in_interval(8,10), 18U);
    expect_test(sum_evens_in_interval(7,10), 18U);
    expect_test(sum_evens_in_interval(8,11), 18U);
    expect_test(sum_evens_in_interval(7,11), 18U);

    expect_test(sumOnlyEvenNumbersInRange(3,3), 0);
    expect_test(sumOnlyEvenNumbersInRange(4,4), 4);
    expect_test(sumOnlyEvenNumbersInRange(1,7), 12);
    expect_test(sumOnlyEvenNumbersInRange(0,6), 12);
    expect_test(sumOnlyEvenNumbersInRange(1,6), 12);
    expect_test(sumOnlyEvenNumbersInRange(0,7), 12);
    expect_test(sumOnlyEvenNumbersInRange(8,10), 18);
    expect_test(sumOnlyEvenNumbersInRange(8,11), 18);
    expect_test(sumOnlyEvenNumbersInRange(7,10), 18);
    expect_test(sumOnlyEvenNumbersInRange(7,11), 18);

    return EXIT_SUCCESS;
}

You can try it out on Godbolt.

Answer 3

Just some corner thoughts

Overflow

sumOnlyEvenNumbersInRange(INT_MAX, INT_MAX) incurs signed integer overflow with (bottom + (bottom & 1)) and is undefined behavior (UB).

Consider:

// int x = (bottom + (bottom & 1)) >> 1;
int x = bottom/2 + (bottom >= 0 && bottom % 2);  // or the like

---

Incorrect functionality for the I don't get no respect encoding: ones' complement

C23 will likely say good-bye to non-2's complement, so until then:

bottom & 1 is an incorrect detection for odd values. Use proper code and let the compiler emit efficient code.

// bottom & 1
(bottom % 2 != 0)