Vérifier une année bissextile avec 3 instructions

• Une fonction est implémentée pour déterminer si une année est bissextile avec seulement 3 instructions CPU
• Cette méthode fonctionne sans branchement traditionnel, en utilisant des opérations sur les bits et une multiplication
• Cette approche est exacte pour la plage de 0 à 102499
• Les benchmarks montrent des performances environ 3,8 fois plus rapides que la méthode classique

---

Vue d’ensemble et formulation du problème

• Pour les années comprises entre 0 et 102499, une fonction qui détermine si une année est bissextile en n’utilisant que 3 instructions CPU
  • La fonction effectivement utilisée est de la forme ((y * 1073750999) & 3221352463) <= 126976
• Explication du principe, du fonctionnement et de l’utilité concrète de cette technique de bit-twiddling

Méthode traditionnelle de détection des années bissextiles

• En général, la détection d’une année bissextile est implémentée avec des divisions modulo et des branchements conditionnels
  • On vérifie si l’année est divisible par 4, non divisible par 100, ou divisible par 400
  • Exemple de code :

    if ((y % 4) != 0) return false  
    if ((y % 100) != 0) return true  
    if ((y % 400) == 0) return true  
    return false  
    

Optimisation de l’approche standard

• Il est possible de remplacer le test (y % 100) par (y % 25) et le test (y % 400) par (y % 16)
  • La raison est qu’on a déjà divisé par 4 au préalable, ce qui permet de reformuler les relations via 25 et 16
• Une constante magique permet de transformer l’opération (y % 25) en multiplication et comparaison sans division
  • Par exemple : conversion possible en x * 3264175145 > 171798691
• En ajoutant un masque de bits, on peut remplacer des divisions par 4 ou 16 avec (y & 3) ou (y & 15)
• Les compilateurs automatisent ces transformations, mais elles peuvent aussi être exploitées manuellement dans d’autres langages

Implémentation sans branchement

• Il est également possible de convertir cela sous une forme sans branchement :

  return !(y & ((y % 25) ? 3 : 15))  
  

• Ce type d’approche convient bien au code golf, où l’on cherche à réduire la taille du code

Recherche des constantes magiques : approche bit-twiddling

• Pour rendre la formule de détection d’une année bissextile encore plus simple, une recherche combinatoire et le solveur SMT Z3 sont utilisés
  • Forme : ((y * f) & m) <= t
• Les constantes f, m, t satisfaisant les contraintes sont recherchées avec Z3
  • Cela permet de trouver des valeurs donnant un résultat exact sur l’intervalle 0~102499
  • Le résultat final est (y * 1073750999) & 3221352463 <= 126976

Explication du principe de la fonction et de sa structure interne

• En analysant les constantes en binaire, elles sont divisées en trois grandes zones de bits : A, B, C
  • Selon l’état des bits dans chaque zone, elles couvrent les 3 conditions de la détection d’une année bissextile
• Décomposition logique de la fonction :
  • Zone A : vérifie la condition de multiple de 4, notamment (y % 4) != 0
  • Zone B : filtre la condition (y % 100) != 0 à l’aide de divers motifs, par exemple des fins de nombre comme 14, 57, 71, etc.
  • Zone C : vérifie (y % 16) == 0, c’est-à-dire le fait d’être un multiple de 16
• Explication du mécanisme par lequel la multiplication combine plusieurs conditions sans calculer explicitement de reste
  • Lorsqu’on multiplie par la constante magique, des motifs de bits particuliers apparaissent pour les multiples de 100, etc.
  • L’analyse inclut aussi la structure mathématique interne liée aux erreurs de multiplication et à l’apparition de motifs sur plusieurs chiffres

Extension possible de la plage et de la largeur en bits

• En l’étendant à 64 bits, l’article présente aussi une méthode pour rechercher des combinaisons adaptées de constantes magiques
  • On peut faire varier les valeurs de f, m, t pour trouver la plage maximale
  • On trouve également sur StackExchange des exemples de combinaison optimale et de preuve utilisant Z3

Benchmarks et comparaison des performances réelles

• Résultats des benchmarks :
  • Pour des valeurs prévisibles comme 2025, la différence est presque nulle, avec 0,65 à 0,69 ns
  • Avec des entrées aléatoires, is_leap_year_fast affiche des performances environ 3,8 fois supérieures
  • Lorsque le schéma d’entrée rend les branchements imprévisibles, cette approche apporte un avantage significatif

Conclusion et pertinence en pratique

• Dans les cas réels où les valeurs sont prévisibles, le gain est faible, mais la méthode est très utile sur de grands volumes de données aléatoires
• Pour remplacer une bibliothèque standard en Python, C# ou ailleurs, un benchmark réaliste sur l’ensemble du programme reste nécessaire
• L’idée et la méthode d’implémentation sont intéressantes en elles-mêmes, et constituent dans certains contextes une solution attrayante du point de vue des performances

[chickendreamtree]

Un texte qui fait penser au fast inverse sqrt

[GN⁺]

Avis Hacker News

• Surprise de constater que les compilateurs modernes comme gcc ou clang optimisent automatiquement un code comme is_leap_year1 en quelque chose comme is_leap_year2, ce qui donne à penser qu’il n’est généralement pas nécessaire d’optimiser soi-même au niveau du code source C ; cela peut toutefois rester utile dans d’autres langages, et il est particulièrement impressionnant de voir à quel point la vérification des années bissextiles est traitée simplement dans la version récente du code source de cal
  • J’aime le fait que le code Linux inverse à chaque fois trois conditions consécutives et n’utilise pas de valeur de retour par défaut, ce qui le rend bien plus facile à comprendre ; avec ce genre de structure de code complexe, le débogage devient vraiment infernal
• Rien d’étonnant au fait que l’explication du fonctionnement de ((y * 1073750999) & 3221352463) <= 126976 soit forcément compliquée ; c’est même parfaitement normal
• J’adore vraiment les techniques d’optimisation à base de nombres magiques difficiles à comprendre ; chaque fois que je vois ça, je me demande combien de techniques d’optimisation j’ai dû manquer à l’époque où j’écrivais des boucles internes en assembleur ; si quelqu’un a une collection de ce genre de techniques, je suis preneur
  • Partage de liens vers diverses techniques d’optimisation : recueil de bit hacks, macro CMP(X, Y) efficace pour les comparaisons à la UNIX, exemple d’optimisation de la fonction signum, exemple de code assembleur pour Motorola 68000, ensemble de macros bit à bit issues d’OpenSolaris, etc. ; avec aussi le regret que le blog Open Solaris ait disparu ; recommandé à tous ceux qui s’intéressent à l’optimisation du code
  • Recommandation du livre "Hacker's Delight", rempli d’astuces sur les bits et de techniques d’optimisation bas niveau
  • Suggestion d’aller regarder la technique de supercompilation
  • À l’époque, on ne passait pas à côté de ces techniques ; la multiplication coûtait simplement tellement cher que ce genre de chose était justement l’optimisation
• Je ne m’attendais absolument pas à ce que la vérification des années bissextiles soit aussi intéressante ; je me dis que les programmeurs bas niveau avaient probablement déjà trouvé ce genre d’astuces depuis longtemps sans forcément les documenter, et j’ai l’impression qu’il en reste peut-être encore cachées dans de vieux codes ; j’aimerais vraiment explorer une collection de ces techniques
  • J’avais appris moi-même ce genre de choses sur z80 dans les années 80, mais j’en ai oublié la plupart ; de temps en temps, quand je les montre à mes enfants d’une vingtaine d’années, ça donne l’impression de faire de la magie
• Si vous avez besoin de connaître les années bissextiles avant l’an 6000, utilisez un calculateur interactif et un outil de visualisation faits maison ; même si le nombre d’instructions machine est un peu plus élevé, cela permet d’effectuer très rapidement des milliers de calculs, et l’astuce mathématique est elle aussi admirable
• En lisant le chapitre sur les manipulations de bits, je me suis dit « on pourrait peut-être utiliser un solveur », et j’ai été surpris de voir que l’auteur avait justement employé cette méthode ; approche minutieuse très satisfaisante
• Suggestion d’ajouter ce type de fonction de vérification d’année bissextile à current-time-api
• En regardant les nombres en binaire, on voit des motifs intéressants ; j’ai trouvé amusant que tous les nombres premiers, sauf 2, se terminent par 1
  • Ça peut sembler amusant, mais comme tous les nombres impairs se terminent par 1 et qu’un nombre premier, par nature, ne peut pas être pair sauf dans le cas de 2, certains se demandent si cela a vraiment une signification particulière
• Quelqu’un fait remarquer qu’il n’y a pas de 0 dans le problème des années bissextiles ; en réalité, il n’existe pas d’« an 0 », on passe directement de 1 BC à 1 AD, donc vérifier 0 n’aurait pas de sens
  • Comme expliqué au tout début de l’article, l’algorithme de calcul des années bissextiles part de l’hypothèse qu’on utilise le calendrier grégorien proleptique ainsi que la numérotation astronomique des années ; sans cela, la vérification des années bissextiles devient complexe selon la locale
  • Avec la notation astronomique des années, l’an 0 existe bel et bien, et pour la gestion des années/mois, c’est même souvent plus propre ; proposition : utiliser la notation astronomique en interne, puis convertir en BCE/CE uniquement pour l’affichage externe
  • Les calendriers antérieurs à l’adoption du calendrier grégorien reposent sur des bases floues et varient selon les régions ; en 1582, il y a même eu une « suppression de 10 jours » en sautant dix dates d’un coup, ce qui rend les calculs sur les dates antérieures peu fiables ; à l’époque romaine, les prêtres ajustaient parfois les années bissextiles de manière arbitraire pour des raisons de superstition ou de corruption, ce qui complique encore davantage les choses
  • La norme ISO8601 autorise l’an 0, et dans le calendrier astronomique, l’an 0 correspond à 1 BC ; toutes les années BCE sont donc décalées de -1
• Il est rare qu’un code source provoque réellement un éclat de rire, donc c’était une expérience très agréable