Cómo comprobar si un año es bisiesto con 3 instrucciones

 (hueffner.de)
13 puntos por GN⁺ 2025-05-16 | 2 comentarios | Compartir por WhatsApp
  • Implementa una función que determina si un año es bisiesto usando solo 3 instrucciones de CPU
  • Este método funciona sin ramas tradicionales, utilizando operaciones de bits y multiplicación
  • Este enfoque es exacto en el rango de 0 a 102499 años
  • Los resultados del benchmark muestran un rendimiento aproximadamente 3.8 veces más rápido que el método existente

Descripción general y planteamiento del problema

  • Para años entre 0 y 102499, presenta una función que determina si un año es bisiesto usando solo 3 instrucciones de CPU
    • La función real utilizada tiene la forma ((y * 1073750999) & 3221352463) <= 126976
  • Explica el principio, el funcionamiento y la utilidad práctica de esta técnica de bit-twiddling

Método tradicional para determinar años bisiestos

  • Normalmente, la comprobación de año bisiesto se implementa con divisiones (módulo) y ramas condicionales
    • Se verifica si es divisible entre 4, si no es divisible entre 100 y si es divisible entre 400
    • Código de ejemplo: 
      if ((y % 4) != 0) return false  
if ((y % 100) != 0) return true  
if ((y % 400) == 0) return true  
return false

Optimización del enfoque estándar

  • La comprobación de (y % 100) puede reemplazarse por (y % 25), y la de (y % 400) por (y % 16)
    • La razón es que antes ya se dividió entre 4, por lo que puede transformarse usando la relación de multiplicación por 25 y 16
  • Una constante mágica para convertir la operación (y % 25) en multiplicación y comparación sin división
    • Por ejemplo, puede transformarse en x * 3264175145 > 171798691
  • También se puede sumar una máscara de bits para sustituir divisiones entre 4 o 16 con (y & 3) o (y & 15)
  • Los compiladores automatizan estas transformaciones, pero también pueden aprovecharse manualmente en otros lenguajes

Implementación sin ramas (branchless)

  • También puede convertirse en una forma sin ramas: 
    return !(y & ((y % 25) ? 3 : 15))
  • Este tipo de enfoque es adecuado para reducir longitud de código, como en code golf

Búsqueda de constantes mágicas: enfoque de bit-twiddling

  • Para hacer la expresión de año bisiesto aún más simple, se utilizó búsqueda combinatoria y el SMT Solver Z3
    • Forma: ((y * f) & m) <= t
  • Se buscaron con Z3 las constantes f, m y t que cumplen las condiciones requeridas
    • Se encontraron valores que dan resultados correctos en el rango de 0 a 102499
    • El resultado final es (y * 1073750999) & 3221352463 <= 126976

Explicación del principio de la función y su estructura interna

  • Al analizar las constantes en binario, se dividen en tres regiones principales de bits: A, B y C
    • Según el estado de los bits en cada región, se abarcan las 3 condiciones de la comprobación de año bisiesto
  • Descomposición lógica de la función:
    • Región A: verifica la condición de múltiplo de 4, incluida la comprobación de si (y % 4) != 0
    • Región B: filtra si (y % 100) != 0 mediante varios patrones (por ejemplo, terminaciones 14, 57, 71, etc.)
    • Región C: comprueba si (y % 16) == 0, es decir, si es múltiplo de 16
  • Explica cómo la multiplicación realmente combina varias condiciones sin calcular restos de forma explícita
    • Al multiplicar por la constante mágica, se forman patrones de bits característicos en múltiplos de 100 y otros casos
    • Además, incluye un análisis de la estructura matemática interna donde aparecen errores de multiplicación y patrones numéricos de varias cifras

Posible ampliación de rango y ancho de bits

  • También se presenta un método para buscar combinaciones adecuadas de constantes mágicas al extenderlo a 64 bits
    • Probando distintos valores de f, m y t, se puede encontrar el rango más amplio posible
    • En StackExchange también hay casos de prueba del uso de Z3 y de combinaciones óptimas

Benchmark y comparación de rendimiento real

  • Resultados del benchmark:
    • En valores predecibles como 2025, casi no hay diferencia, con 0.65~0.69ns
    • Con entradas aleatorias, is_leap_year_fast muestra un rendimiento aproximadamente 3.8 veces superior
    • Según el patrón de entrada, el enfoque con ramas puede volverse impredecible y aquí existe una ventaja considerable

Conclusión y aplicabilidad real

  • En aplicaciones reales, si los valores son predecibles, la ganancia es pequeña, pero es muy útil en escenarios con grandes volúmenes de datos aleatorios
  • Si se quiere reemplazar una biblioteca estándar real en Python o C#, hace falta un benchmark realista del programa completo
  • La idea y el método de implementación en sí son interesantes, y en ciertos casos son una solución atractiva en términos de rendimiento

Lecturas relacionadas

2 comentarios

 
chickendreamtree 2025-05-19

Un texto que recuerda al fast inverse sqrt
 
GN⁺ 2025-05-16
Opiniones en Hacker News
  • Sorprende saber que compiladores modernos como gcc o clang optimizan automáticamente código como is_leap_year1 para convertirlo en algo como is_leap_year2, así que no parece muy necesario optimizarlo a mano en la etapa del código fuente en C, aunque todavía puede ser útil en otros lenguajes; en particular, impresiona lo simple que resuelve la verificación de año bisiesto el código fuente de la versión reciente del programa cal
    • Me gusta que el código de Linux invierta cada vez tres condiciones consecutivas y no use un valor de retorno por defecto, porque así es mucho más fácil de entender; cuando hay estructuras de código tan complejas, depurar se vuelve una locura
  • No sorprende en absoluto que la explicación de cómo funciona este código, ((y * 1073750999) & 3221352463) <= 126976, termine siendo complicada; más bien, es lo natural
  • Me encantan de verdad estas técnicas de optimización con números mágicos difíciles de entender; cada vez que veo algo así me pregunto cuántas técnicas de optimización me habré perdido de la época en que se escribían loops internos en ensamblador; si alguien tiene una colección de este tipo de trucos, que la comparta
    • Comparten enlaces a recopilaciones de trucos de manipulación de bits, al macro CMP(X, Y) eficiente para comparaciones al estilo UNIX, ejemplos de optimización de la función signum, ejemplos de código ensamblador para Motorola 68000 y colecciones de macros de bits originadas en OpenSolaris, entre otras técnicas de optimización; también mencionan con pena que el blog de Open Solaris ya no existe, y lo recomiendan a quienes se interesan por optimización de código
    • Recomiendan el libro "Hacker's Delight", lleno de trucos de bits y técnicas de optimización de bajo nivel
    • Sugieren buscar la técnica de supercompilation
    • En esa época no es que se perdieran estas técnicas; más bien, como la multiplicación era tan cara, cosas así eran precisamente la optimización
  • Nunca habría imaginado que verificar años bisiestos pudiera ser tan interesante; quizá los programadores de bajo nivel ya habían encontrado estos trucos hace mucho tiempo, pero no dejaron registro; da la impresión de que todavía podrían seguir escondidos en código antiguo, y si hubiera una colección de estas técnicas, de verdad daría ganas de explorarla
    • En los años 80 aprendí por mi cuenta algunas cosas con el z80 en casa, pero ya olvidé la mayoría; a veces se las muestro a mis hijos que están en sus 20 y parece como si estuviera haciendo magia
  • Si necesitas saber si un año es bisiesto antes del 6000, usa una calculadora interactiva y herramienta de visualización hecha por el propio autor; aunque usa algo más de instrucciones de máquina, puede procesar miles de cálculos muy rápido, y los trucos matemáticos también impresionan
  • Mientras leía el capítulo de manipulación de bits pensé "¿y si se pudiera usar un solver?", y me sorprendió que el autor efectivamente hubiera usado exactamente ese método; muy satisfecho con lo meticuloso del enfoque
  • Sugieren que sería bueno añadir una función de verificación de año bisiesto como esta a current-time-api
  • Cuando miras los números en binario aparecen patrones interesantes; llamó la atención que todos los números primos, salvo el 2, terminan en 1
    • Puede sonar curioso, pero como todos los números impares terminan en 1 y los primos, salvo el 2, por naturaleza no pueden ser pares, alguien cuestiona que eso tenga mucho significado
  • Aparece la observación de que en el problema de los años bisiestos no existe el 0; en realidad no hay "año 0", sino que se pasa directamente de 1 BC a 1 AD, así que comprobar 0 no tendría sentido
    • Al principio del artículo se explica que la premisa del algoritmo de año bisiesto usa el calendario gregoriano proléptico y numeración astronómica de años; sin esa condición, comprobar años bisiestos se vuelve complejo según la localidad
    • Si se usa la notación astronómica de años, sí aparece el año 0, y para manejar años/meses eso incluso resulta más limpio; se propone usar notación astronómica en los datos internos y convertir solo la salida externa a BCE/CE
    • Los calendarios anteriores a la adopción del gregoriano tienen criterios ambiguos y varían según la región; en 1582 incluso hubo una "eliminación de 10 días" en un solo salto, así que los cálculos de fechas anteriores no son confiables; además, en tiempos romanos los sacerdotes ajustaban los años bisiestos arbitrariamente por superstición o sobornos, lo que complica aún más todo
    • La norma ISO8601 permite el año 0, y en el calendario astronómico el año 0 significa 1 BC; todos los años BCE quedan desplazados en -1
  • Es raro que un código fuente realmente te haga soltar una carcajada, así que fue una experiencia muy agradable