How to find leap year programmatically in C

Admin 1
Viewed 39777

I wrote a program in C to find whether the entered year is a leap year or not. But unfortunately its not working well. It says a year is leap and the preceding year is not leap.

#include <stdio.h>
#include <conio.h>

int yearr(int year);

void main(void) {
    int year;
    printf("Enter a year:");
    scanf("%d", &year);
    if (!yearr(year)) {
        printf("It is a leap year.");
    } else {
        printf("It is not a leap year");
    }

    getch();
}

int yearr(int year) {
    if ((year % 4 == 0) && (year / 4 != 0))
        return 1;
    else
        return 0;
}

After reading the comments I edited my code as:

#include <stdio.h>
#include <conio.h>

int yearr(int year);

void main(void) {
    int year;
    printf("Enter a year:");
    scanf("%d", &year);
    if (!yearr(year)) {
        printf("It is a leap year.");
    } else {
        printf("It is not a leap year");
    }

    getch();
}

int yearr(int year) {
    if (year % 4 == 0) {
        if (year % 400 == 0)
            return 1;
        if (year % 100 == 0)
            return 0; 
    } else
        return 0;
}
leap-year c
17 Answers

Many answers talk about performance. None shows any measurement. A nice quote from gcc's documentation on __builtin_expect says this:

Programmers are notoriously bad at predicting how their programs actually perform.

Most implementations use short-circuiting of && and || as an optimization tool and go on to prescribe the "right" order for the divisibility checks for "best" performance. It is worth mentioning that short-circuiting is not necessarily an optimization feature.

Agreed, some checks might give a definitive answer (e.g. year is not multiple of 4) and make useless the subsequent tests. It seems all reasonable to immediately return at this point rather than keeping going with needless calculations. On the other hand, early returns introduce branches and this might decrease performance. (See this legendary post.) The trade-off between a branch misprediction and an unnecessary calculation is very hard to guess. Indeed, it depends on the hardware, on input data, on the exactly assembly instructions emitted by the compiler (which might change from one version to another), etc.

The sequel shall show measurements obtained in quick-bench.com. In all cases, we measure the time taken to check whether each value stored in an std::array<int, 65536> is a leap year or not. The values are pseudo-random, uniformly distributed in the interval [-400, 399]. More precisely, they are generated by the following code:

auto const years = [](){
  std::uniform_int_distribution<int> uniform_dist(-400, 399);
  std::mt19937 rng;
  std::array<int, 65536> years;
  for (auto& year : years)
    year = uniform_dist(rng);
  return years;
}();

Even when possible, I do not replace % with & (e.g. year & 3 == 0 instead of year % 4 == 0). I trust the compiler (GCC-9.2 at -O3) will do that for me. (It does.)

4-100-400 tests

Checks for leap years are, usually, written in terms of three divisibility tests: year % 4 == 0, year % 100 != 0 and year % 400 == 0. The following is a list of implementations covering all possible orders in which these checks can appear. Each implementation is prefixed with a corresponding label. (Some orders allow two different implementations, in which case, the 2nd one gets a suffix b.) They are:

b4_100_400  : year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)
b4_100_400b : (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
b4_400_100  : year % 4 == 0 && (year % 400 == 0 || year % 100 != 0)
b100_4_400  : (year % 100 != 0 && year % 4 == 0) || year % 400 == 0
b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0
b400_4_100  : year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)
b400_100_4  : year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)
b400_100_4b : (year % 400 == 0 || year % 100 != 0) && year % 4 == 0

The results are shown below. (See them live.)

4-100-400 tests

Contrarily to what many have advised, checking divisibility by 4 first does not seem to be the best thing to do. At the contrary, at least in these measurements, the three first bars are among the worst five. The best is

b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0

4-25-16 tests

Another provided tip (which I must confess I thought was a good one) is replacing year % 100 != 0 with year % 25 != 0. This doesn't affect correctness since we also check year % 4 == 0. (If a number is multiple of 4 then divisibility by 100 is equivalent to divisibility by 25.) Similarly, year % 400 == 0 can be replaced with year % 16 == 0 due to the presence of divisibility check by 25.

As in the last section, we have 8 implementations using 4-25-16 divisibility checks:

b4_25_16  : year % 4 == 0 && (year % 25 != 0 || year % 16 == 0)
b4_25_16b : (year % 4 == 0 && year % 25 != 0) || year % 16 == 0
b4_16_25  : year % 4 == 0 && (year % 16 == 0 || year % 25 != 0)
b25_4_16  : (year % 25 != 0 && year % 4 == 0) || year % 16 == 0
b25_16_4  : (year % 25 != 0 || year % 16 == 0) && year % 4 == 0
b16_4_25  : year % 16 == 0 || (year % 4 == 0 && year % 25 != 0)
b16_25_4  : year % 16 == 0 || (year % 25 != 0 && year % 4 == 0)
b16_25_4b : (year % 16 == 0 || year % 25 != 0) && year % 4 == 0

Results (live here):

4-25-16 tests

Again, checking divisibility by 4 first does not look a good idea. In this round the fast is

b25_16_4  : (year % 25 != 0 || year % 16 == 0) && year % 4 == 0

4-100-400 tests (no branching)

As previously mentioned branching might degrade performance. In particular, short-circuiting might be counterproductive. When this is the case, a classical trick is replacing logical operators && and || with their bit-wise counterparts & and |. The implementations become:

nb4_100_400  : (year % 4 == 0) & ((year % 100 != 0) | (year % 400 == 0))
nb4_100_400b : ((year % 4 == 0) & (year % 100 != 0)) | (year % 400 == 0)
nb4_400_100  : (year % 4 == 0) & ((year % 400 == 0) | (year % 100 != 0))
nb100_4_400  : ((year % 100 != 0) & (year % 4 == 0)) | (year % 400 == 0)
nb100_400_4  : ((year % 100 != 0) | (year % 400 == 0)) & (year % 4 == 0)
nb400_4_100  : (year % 400 == 0) | ((year % 4 == 0) & (year % 100 != 0))
nb400_100_4  : (year % 400 == 0) | ((year % 100 != 0) & (year % 4 == 0))
nb400_100_4b : ((year % 400 == 0) | (year % 100 != 0)) & (year % 4 == 0)

Results (live here):

4-100-400 tests (no branching)

A noticeable feature is that performance variation is not as pronounced as in the branching case and it makes difficult to declare a winner. We pick this one:

nb100_400_4  : ((year % 100 != 0) | (year % 400 == 0)) & (year % 4 == 0)

4-25-16 tests (no branching)

To complete the exercise, we consider the no-branching case with 4-25-16 divisibility tests:

nb4_25_16  : (year % 4 == 0) & ((year % 25 != 0) | (year % 16 == 0))
nb4_25_16b : ((year % 4 == 0) & (year % 25 != 0)) | (year % 16 == 0)
nb4_16_25  : (year % 4 == 0) & ((year % 16 == 0) | (year % 25 != 0))
nb25_4_16  : ((year % 25 != 0) & (year % 4 == 0)) | (year % 16 == 0)
nb25_16_4  : ((year % 25 != 0) | (year % 16 == 0)) & (year % 4 == 0)
nb16_4_25  : (year % 16 == 0) | ((year % 4 == 0) & (year % 25 != 0))
nb16_25_4  : (year % 16 == 0) | ((year % 25 != 0) & (year % 4 == 0))
nb16_25_4b : ((year % 16 == 0) | (year % 25 != 0)) & (year % 4 == 0)

Results (live here):

4-25-16 tests (no branching)

Once again, it's difficult to define the best and we select this one:

nb25_16_4  : ((year % 25 != 0) | (year % 16 == 0)) & (year % 4 == 0)

Champions League

It's now time to pick the best of each previous section and compare them:

b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0
b25_16_4    : (year % 25 != 0 || year % 16 == 0) && year % 4 == 0
nb100_400_4 : ((year % 100 != 0) | (year % 400 == 0)) & (year % 4 == 0)
nb25_16_4   : ((year % 25 != 0) | (year % 16 == 0)) & (year % 4 == 0)

Results (live here):

Champions League

This chart suggests that short-circuiting is, indeed, an optimization but divisibility by 4 should be the last to be checked rather then the first. For better performance one should check divisibility by 100 first. This is rather surprising! After all, the latter test is never enough to decide whether the year is leap or not and a subsequent test (either by 400 or by 4) is always required.

Also surprising is that for the branching versions using simpler divisors 25 and 16 is not better than using the more intuitive 100 and 400. I can offer my "theory" which also partially explains why testing for 100 first is better than testing for 4. As many pointed out, the divisibility test by 4 splits execution into (25%, 75%) parts whereas the test for 100 splits it into (1%, 99%). It doesn't matter that after the latter check, the execution must carry on to another test because, at least, the branch predictor is more likely to guess correctly which way to go. Similarly, checking divisibility by 25 splits execution into (4%, 96%) which is more challenging for the branch predictor than (1%, 99%). It looks like that it is better to minimize the entropy of the distribution, helping the branch predictor, rather than maximizing the probability of early return.

For the no branching versions, simplified divisors do offer better performance. In this case the branch predictor plays no role and, therefore, the simpler the better. Generally, the compiler can perform better optimizations with smaller numbers.

Is this it?

Did we hit the wall and found out that

b100_400_4  : (year % 100 != 0 || year % 400 == 0) && year % 4 == 0

is the most performant check for leap years? Definitely not. We haven't for instance, mixed branching operators && or || with no branching ones & and |. Perhaps... Let's see and compare the above with two other implementations. The first is

m100_400_4 : (year % 100 != 0 || year % 400 == 0) & (year % 4 == 0)

(Notice the mix of branching || and non-branching & operators.) The second is an obscure "hack":

bool b;
auto n = 0xc28f5c29 * year;
auto m = n + 0x051eb850;
m = (m << 30 | m >> 2);
if (m <= 0x28f5c28)
  b = n % 16 == 0;
else
  b = n % 4 == 0;
return b

Does the latter work? Yes it does. Instead of giving a mathematical proof I suggest comparing the code emitted for the above with the one for this more readable source:

bool b;
if (year % 100 == 0)
  b = year % 16 == 0;
else
  b = year % 4 == 0;
return b;

in Compiler Explorer. They are almost identical, the only difference being that one uses an add instruction when the other uses a lea. This should convince you that the hack code does work (as long as the other does).

Benchmark results (live here):

Final

Hold on, I hear you say, why not using the more readable code in the picture above? Well, I've tried and learned another lesson. When this code is inserted into the benchmark loop, the compiler looked at the source as a whole and decided to emit different code than when it sees the source in isolation. The performance was worse. Go figure!

And now? Is this it?

I don't know! There are many things that we could explore. The last section, for instance, showed yet another version using an if statement rather that short-circuiting. That could be a way to get even better performance. We could also try the ternary operator ?.

Be aware that all measurements and conclusions were based on GCC-9.2. With another compiler and/or version things might change. For instance, GCC from version 9.1 introduced a new improved algorithm for divisibility checks. Hence, older versions have different performances and the trade-off between an unnecessary calculation and a branch misprediction have likely changed.

The points that we can definitely conclude are:

  1. Do not overthink. Prefer clear code over difficult to understand optimizations (unless you're a library writer offering higher level APIs for your users around very efficient implementations). After all, a hand-crafted snippet might not be the most performant option when you upgrade compiler. As ex-nihilo said in a comment, "There is little point in fussing over a piece of code like this unless it is known to be a performance bottleneck."
  2. Guessing is difficult and it's better to measure.
  3. Measuring is difficult but is better than guessing.
  4. Short-circuiting/branching can be good for performance but it depends on many things including how much the code helps the branch predictor.
  5. Code emitted for a snippet in isolation might be different when it's inlined somewhere.
user_11373880

Here are 2 more solutions that seem to beat previous ones on the quick-bench.com benchmark.

This one has a test but that compiles to branchless code with clang:

int isleap3(int year) {
    unsigned y = year + 16000;
    return (y % 100) ? !(y % 4) : !(y % 16);
}

This one uses a single modulo operation and no tests, and compiles to just 2 multiplications:

static unsigned char const leaptest[400] = {
    1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,
    0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,
    0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,
    0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,
    0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,
    0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,
    0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,
    0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,
    0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,
    0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,
    0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,
    0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,
    0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,
    0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,
    0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,
    0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,
};
int isleap4(int year) {
    unsigned y = year + 16000;
    return leaptest[y % 400];
}

clang 64-bit Assembly:

isleap3:                                # @isleap3
        add     edi, 16000
        imul    eax, edi, -1030792151
        ror     eax, 2
        cmp     eax, 42949673
        mov     eax, 15
        mov     ecx, 3
        cmovb   ecx, eax
        xor     eax, eax
        test    ecx, edi
        sete    al
        ret
isleap4:                                # @isleap4
        add     edi, 16000
        imul    rax, rdi, 1374389535
        shr     rax, 39
        imul    eax, eax, 400
        sub     edi, eax
        movzx   eax, byte ptr [rdi + leaptest]
        ret
leaptest:
        .asciz  "\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\000\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\000\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\000\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000\000\001\000\000"

Here is the are the benchmark results:

enter image description here

user_45932670

Calculate max/last day for month: 1..12, year: 1..3999

maxDays = month == 2 ?
  28 + ((year & 3) == 0 && ((year % 25) != 0 || (year & 15) == 0)) :
  30 + ((month & 1) ^ (month > 7));
user_68017590
Related