Cómo encontrar el año bisiesto mediante programación en C

Escribí un programa en C para saber si el año ingresado es bisiesto o no. Pero lamentablemente no funciona bien. Dice que un año es bisiesto y el año anterior no es bisiesto.

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

Después de leer los comentarios edité mi código como:

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

Jul 11 '10 00:07

Su lógica para determinar un año bisiesto es errónea. Esto debería ayudarte a comenzar (de Wikipedia):

if year modulo 400 is 0
       then is_leap_year
else if year modulo 100 is 0
       then not_leap_year
else if year modulo 4 is 0
       then is_leap_year
else
       not_leap_year

x modulo ysignifica el resto de xdividido por y. Por ejemplo, 12 módulo 5 es 2.

Jul 10 '2010 17:07 Alok Singhal

Muchas respuestas hablan de rendimiento. Ninguno muestra ninguna medida. Una buena cita de la documentación de gcc __builtin_expectdice esto:

Los programadores son notoriamente malos a la hora de predecir cómo funcionan realmente sus programas.

La mayoría de las implementaciones utilizan el cortocircuito de &&y ||como herramienta de optimización y continúan prescribiendo el orden "correcto" para las comprobaciones de divisibilidad para obtener el "mejor" rendimiento. Vale la pena mencionar que el cortocircuito no es necesariamente una característica de optimización.

De acuerdo, algunas comprobaciones pueden dar una respuesta definitiva (por ejemplo, el año no es múltiplo de 4) y hacer inútiles las pruebas posteriores. Parece razonable regresar inmediatamente a este punto en lugar de seguir con cálculos innecesarios. Por otro lado, los retornos anticipados introducen sucursales y esto podría disminuir el rendimiento. (Consulte esta publicación legendaria ). La compensación entre una predicción errónea de una rama y un cálculo innecesario es muy difícil de adivinar. De hecho, depende del hardware, de los datos de entrada, de las instrucciones exactas de ensamblaje emitidas por el compilador (que pueden cambiar de una versión a otra), etc.

La secuela mostrará las mediciones obtenidas en quick-bench.com . En todos los casos, medimos el tiempo necesario para comprobar si cada valor almacenado en un std::array<int, 65536>es un año bisiesto o no. Los valores son pseudoaleatorios, distribuidos uniformemente en el intervalo [-400, 399]. Más precisamente, se generan mediante el siguiente código:

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

Incluso cuando es posible, no lo reemplazo %con &(por ejemplo, year & 3 == 0en lugar de year % 4 == 0). Confío en que el compilador (GCC-9.2 en -O3) lo hará por mí. (Lo hace.)

4-100-400 pruebas

Los cheques para años bisiestos generalmente se escriben en términos de tres pruebas de divisibilidad: year % 4 == 0, year % 100 != 0y year % 400 == 0. La siguiente es una lista de implementaciones que cubren todos los órdenes posibles en los que pueden aparecer estas comprobaciones. Cada implementación tiene como prefijo una etiqueta correspondiente. (Algunas órdenes permiten dos implementaciones diferentes, en cuyo caso, la segunda obtiene un sufijo b). Son:

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

Los resultados se muestran a continuación. (Véalos en vivo ).

Al contrario de lo que muchos han aconsejado, comprobar 4primero la divisibilidad no parece ser lo mejor que se puede hacer. Por el contrario, al menos en estas mediciones, las tres primeras barras se encuentran entre las cinco peores. El mejor es

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

25-04-16 pruebas

Otro consejo proporcionado (que debo confesar que pensé que era bueno) es reemplazarlo year % 100 != 0con year % 25 != 0. Esto no afecta la corrección ya que también verificamos year % 4 == 0. (Si un número es múltiplo de 4entonces la divisibilidad por 100es equivalente a la divisibilidad por 25). De manera similar, year % 400 == 0se puede reemplazar con year % 16 == 0debido a la presencia de verificación de divisibilidad por 25.

Como en la última sección, tenemos 8 implementaciones que utilizan comprobaciones de divisibilidad 4-25-16:

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

Resultados (en vivo aquí ):

Nuevamente, comprobar la divisibilidad 4primero no parece una buena idea. En esta ronda el ayuno es

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

4-100-400 pruebas (sin ramificaciones)

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):

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):

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):

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):

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.

Mar 12 '2020 02:03 Cassio Neri