Mit drei Befehlen prüfen, ob ein Jahr ein Schaltjahr ist

 (hueffner.de)
13 Punkte von GN⁺ 2025-05-16 | 2 Kommentare | Auf WhatsApp teilen
  • Es wird eine Funktion implementiert, die ein Schaltjahr mit nur drei CPU-Befehlen bestimmt
  • Diese Methode arbeitet mit Bit-Operationen und Multiplikation ohne traditionelle Verzweigungen
  • Dieser Ansatz ist im Bereich von 0 bis 102499 Jahren korrekt
  • Benchmark-Ergebnisse zeigen gegenüber herkömmlichen Methoden eine rund 3,8-fach höhere Leistung

Überblick und Problemstellung

  • Für Jahre zwischen 0 und 102499 eine Funktion, die mit nur drei CPU-Befehlen ein Schaltjahr bestimmt
    • Die tatsächlich verwendete Funktion hat die Form ((y * 1073750999) & 3221352463) <= 126976
  • Erläutert werden Prinzip, Funktionsweise und praktischer Nutzen dieser Bit-Twiddling-Technik

Traditionelle Methode zur Schaltjahr-Prüfung

  • Üblicherweise wird die Schaltjahr-Prüfung mit Divisionen (modulo) und bedingten Verzweigungen implementiert
    • Geprüft wird, ob die Zahl durch 4 teilbar ist, nicht durch 100 teilbar ist oder durch 400 teilbar ist
    • Beispielcode: 
      if ((y % 4) != 0) return false  
if ((y % 100) != 0) return true  
if ((y % 400) == 0) return true  
return false

Optimierung des Standardansatzes

  • Die Prüfung (y % 100) kann durch (y % 25) ersetzt werden, und (y % 400) durch (y % 16)
    • Der Grund ist, dass zuvor bereits durch 4 geteilt wurde und sich die Beziehung daher auf 25 bzw. 16 umstellen lässt
  • Eine magische Konstante, um die Operation (y % 25) ohne Division in Multiplikation und Vergleich umzuwandeln
    • Beispiel: Sie kann in x * 3264175145 > 171798691 umgeformt werden
  • Durch zusätzliche Bitmasken lassen sich Divisionen durch 4 oder 16 durch (y & 3) bzw. (y & 15) ersetzen
  • Compiler automatisieren solche Umformungen, man kann sie aber auch direkt in anderen Sprachen nutzen

Branchless-Implementierung

  • Sie lässt sich auch in eine branchless Form umwandeln: 
    return !(y & ((y % 25) ? 3 : 15))
  • Solche Ansätze eignen sich gut für Code Golf, bei dem es um möglichst kurzen Code geht

Finden der magischen Konstanten: Bit-Twiddling-Ansatz

  • Um die Schaltjahr-Formel noch einfacher zu machen, werden kombinatorische Suche und der SMT-Solver Z3 genutzt
    • Form: ((y * f) & m) <= t
  • Mit Z3 werden Konstanten f, m, t gesucht, die die Anforderungen erfüllen
    • Es werden Werte gefunden, die im Bereich 0 bis 102499 korrekte Ergebnisse liefern
    • Das Endergebnis ist (y * 1073750999) & 3221352463 <= 126976

Erklärung des Prinzips und der internen Struktur der Funktion

  • Die Konstanten werden binär analysiert und in drei wesentliche Bit-Bereiche A, B, C unterteilt
    • Je nach Bitzustand in diesen Bereichen werden die drei Bedingungen zur Schaltjahr-Prüfung abgedeckt
  • Logische Zerlegung der Funktion:
    • Bereich A: Prüfung der Bedingung für Vielfache von 4, einschließlich (y % 4) != 0
    • Bereich B: Filtert (y % 100) != 0 über verschiedene Muster, etwa Endziffern wie 14, 57 oder 71
    • Bereich C: Prüfung von (y % 16) == 0, also ob ein Vielfaches von 16 vorliegt
  • Erläutert wird, warum die Multiplikation tatsächlich verschiedene Bedingungen ohne echte Restwertberechnung kombiniert
    • Beim Multiplizieren mit der magischen Konstante entstehen bei Vielfachen von 100 und ähnlichen Werten charakteristische Bitmuster
    • Zusätzlich wird die mathematische innere Struktur analysiert, einschließlich Multiplikationsfehlern und verschiedener Ziffernmuster

Erweiterbarkeit auf größere Bereiche und Bitbreiten

  • Für eine Erweiterung auf 64 Bit wird ebenfalls eine Methode zur Suche nach geeigneten Kombinationen magischer Konstanten vorgestellt
    • Durch Variieren von f, m, t lässt sich der größtmögliche Bereich finden
    • Auch auf StackExchange gibt es Beispiele für optimale Kombinationen und Beweise mit Z3

Benchmarks und tatsächlicher Leistungsvergleich

  • Benchmark-Ergebnisse:
    • Bei vorhersagbaren Werten wie 2025 gibt es mit 0,65 bis 0,69 ns praktisch kaum Unterschiede
    • Bei zufälligen Eingaben zeigt is_leap_year_fast eine etwa 3,8-fach höhere Leistung
    • Je nach Eingabemuster gibt es deutliche Vorteile, wenn ein verzweigender Ansatz schlecht vorhersagbar ist

Fazit und praktische Einsetzbarkeit

  • In realen Anwendungen ist der Nutzen bei vorhersagbaren Werten gering, aber in Situationen mit großen Mengen zufälliger Daten sehr nützlich
  • Für den Austausch von Standardbibliotheken etwa in Python oder C# sind realistische Benchmarks des Gesamtprogramms nötig
  • Die Idee und die Implementierung selbst sind interessant und in bestimmten Situationen eine leistungsstarke Lösung

Verwandte Beiträge

2 Kommentare

 
chickendreamtree 2025-05-19

Erinnert an Fast inverse sqrt
 
GN⁺ 2025-05-16
Hacker-News-Kommentare
  • Ich war überrascht, dass moderne Compiler wie gcc oder clang Code wie is_leap_year1 automatisch zu etwas wie is_leap_year2 optimieren, daher scheint es auf C-Quellcodeebene meist nicht mehr nötig zu sein, selbst zu optimieren; in anderen Sprachen kann das aber weiterhin nützlich sein, und besonders beeindruckend ist, wie schlicht die aktuelle Version des cal-Programms die Schaltjahr-Prüfung behandelt.
    • Mir gefällt, dass der Linux-Code die drei aufeinanderfolgenden Bedingungen jedes Mal invertiert und keinen Default-Return verwendet, weil er dadurch viel leichter zu verstehen ist; bei so komplexen Code-Strukturen wird Debugging wirklich zur Qual.
  • Es überrascht mich überhaupt nicht, dass die Erklärung, wie ((y * 1073750999) & 3221352463) <= 126976 funktioniert, zwangsläufig kompliziert ist; eigentlich ist das nur folgerichtig.
  • Ich liebe schwer verständliche Optimierungstechniken mit Magic Numbers; jedes Mal, wenn ich so etwas sehe, frage ich mich, wie viele Optimierungen ich früher beim Schreiben von inneren Schleifen in Assembler verpasst habe. Falls jemand eine Sammlung solcher Techniken hat, bitte teilen.
    • Geteilt wurde eine Link-Sammlung mit verschiedenen Bit-Manipulationstricks, einem für Vergleiche im UNIX-Stil effizienten CMP(X, Y)-Makro, einem Beispiel zur Optimierung der signum-Funktion, Assembly-Code-Beispielen für den Motorola 68000 sowie einer Sammlung von Bit-Makros aus OpenSolaris. Bedauert wurde auch, dass der Open-Solaris-Blog verschwunden ist; für alle mit Interesse an Code-Optimierung trotzdem sehr empfehlenswert.
    • Das Buch "Hacker's Delight" wird empfohlen; es ist voller Bit-Tricks und Low-Level-Optimierungstechniken.
    • Der Vorschlag, sich mit der Technik der Supercompilation zu beschäftigen.
    • Früher hat man solche Techniken nicht übersehen; Multiplikation war damals einfach so teuer, dass genau solche Dinge die eigentliche Optimierung waren.
  • Ich hätte nie gedacht, dass eine Schaltjahr-Prüfung so interessant sein kann; vermutlich haben Low-Level-Programmierer solche Tricks schon vor langer Zeit gefunden, aber nie dokumentiert. Vielleicht verstecken sich solche Dinge noch heute in altem Code; falls es eine Sammlung solcher Techniken gibt, würde ich sie liebend gern durchforsten.
    • In den 80ern habe ich auf dem Z80 zu Hause einiges selbst gelernt, aber das meiste vergessen; wenn ich so etwas gelegentlich meinen Kindern in den Zwanzigern zeige, wirkt es fast wie Zauberei.
  • Wer Schaltjahre vor dem Jahr 6000 bestimmen muss, kann einen selbstgebauten interaktiven Rechner samt Visualisierung verwenden; auch wenn dafür etwas mehr Maschinenbefehle nötig sind, lassen sich damit Tausende Berechnungen sehr schnell ausführen, und die mathematischen Tricks sind ebenfalls beeindruckend.
  • Beim Lesen des Kapitels über Bit-Manipulation dachte ich sofort: "Vielleicht kann man dafür einen Solver benutzen?" — und war dann verblüfft, dass der Autor genau diesen Ansatz gewählt hat; sehr zufrieden mit diesem sorgfältigen Vorgehen.
  • Vorschlag, eine solche Schaltjahr-Prüffunktion zu current-time-api hinzuzufügen.
  • Wenn man Zahlen binär betrachtet, erkennt man interessante Muster; spannend fand ich, dass alle Primzahlen außer 2 auf 1 enden.
    • Das mag interessant wirken, aber da alle ungeraden Zahlen auf 1 enden und Primzahlen außer 2 nun einmal nicht gerade sein können, sehe ich darin keine besondere Aussage.
  • Es wurde angemerkt, dass im Schaltjahr-Problem die 0 fehlt; tatsächlich gibt es kein "Jahr 0", weil direkt von 1 BC zu 1 AD übergegangen wird, daher ist eine Prüfung auf 0 bedeutungslos.
    • Gleich am Anfang des Artikels wird jedoch erklärt, dass die Schaltjahr-Algorithmen unter der Annahme eines proleptischen gregorianischen Kalenders und astronomischer Jahreszählung entworfen wurden; ohne diese Annahme würde die Schaltjahr-Prüfung je nach Locale deutlich komplizierter.
    • Mit astronomischer Jahreszählung gibt es sehr wohl ein Jahr 0, und für die Verwaltung von Jahr/Monat und Ähnlichem ist das sogar sauberer; vorgeschlagen wird, intern astronomische Zählung zu verwenden und nur für die Ausgabe nach BCE/CE umzuwandeln.
    • Kalender vor der Einführung des gregorianischen Kalenders sind ohnehin unscharf definiert und regional unterschiedlich; 1582 gab es sogar die "Streichung von 10 Tagen", sodass Berechnungen für frühere Daten kaum verlässlich sind. Römische Priester passten Schaltjahre teils aus Aberglauben oder wegen Bestechung willkürlich an, was alles noch komplizierter macht.
    • Der ISO8601-Standard erlaubt ein Jahr 0, und im astronomischen Kalender bedeutet Jahr 0 das Jahr 1 BC; alle BCE-Jahre sind also um -1 verschoben.
  • Da Quellcode einen nur selten tatsächlich laut lachen lässt, war das eine ausgesprochen erfreuliche Erfahrung.