3つの命令でうるう年かどうかを判定する

• CPU命令3つだけでうるう年を判定する関数を実装
• この方法はビット演算と乗算を使い、従来の分岐なしで動作
• この方式は0〜102499年の範囲で正確
• ベンチマーク結果では既存手法と比べて約3.8倍高速

---

概要と問題提起

• 0年から102499年までの年に対して、わずか3つのCPU命令だけを使ってうるう年を判定する関数
  • 実際に使われる関数は ((y * 1073750999) & 3221352463) <= 126976 という構造
• このビットツイードリング(bit-twiddling)手法の原理と動作、実用上の有効性を説明

従来のうるう年判定方法

• 通常、うるう年判定は剰余(modulo)と条件分岐で実装する
  • 4で割り切れるか、100で割り切れないか、400で割り切れるかを調べる
  • 例示コード:

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

標準的なアプローチの最適化

• (y % 100) の検査を (y % 25) に、(y % 400) の検査を (y % 16) に置き換え可能
  • その理由は、先に4で割っているため、25および16との乗算関係に変換できるから
• (y % 25) 演算を除算なしで乗算と比較に変換するマジック定数
  • 例: x * 3264175145 > 171798691 に変換可能
• ビットマスクを加えることで (y & 3) や (y & 15) により4または16での除算判定を代替可能
• コンパイラはこうした変換を自動化するが、他の言語でも手動で活用できる

分岐なし(branchless)実装法

• 分岐のない形にも変換可能:

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

• このような方式はコードゴルフ(coding golf)のようにコード長を減らしたい場面にも向いている

マジック定数の探索: ビットツイードリング手法

• うるう年判定式をさらに単純化するため、組合せ探索とSMT Solverである Z3 を活用
  • 形式: ((y * f) & m) <= t
• 条件を満たす定数 f, m, t をZ3で探索
  • 0〜102499の範囲で正確な結果を得られる値を発見
  • 最終結果は (y * 1073750999) & 3221352463 <= 126976

関数の原理と内部構造の解説

• 定数を2進数で分析し、3つの主要ビット領域 A, B, C に区分
  • 各領域のビット状態によって、うるう年判定の3つの条件を包含
• 関数の論理的な分解:
  • A領域: (y % 4) != 0 かどうかをはじめとする4の倍数条件の確認
  • B領域: (y % 100) != 0 かどうかを、さまざまなパターン（例: 下2桁が14、57、71など）でフィルタリング
  • C領域: (y % 16) == 0、つまり16の倍数かどうかの確認
• 乗算によって実際に剰余計算なしで複数の条件を組み合わせる原理を解説
  • マジック定数を掛けると、100の倍数などで特徴的なビットパターンが形成される
  • さらに、乗算誤差や複数桁の数字パターンが現れる数学的な内部構造の分析も含まれる

追加の範囲とビット幅拡張の可能性

• 64ビットへ拡張する場合の適切なマジック定数の組合せ探索法も提示
  • f, m, t の値をさまざまに変えながら最長範囲を探せる
  • StackExchangeでも最適な組合せやZ3を用いた証明例がある

ベンチマークと実際の性能比較

• ベンチマーク結果:
  • 2025年のような予測しやすい値では0.65〜0.69nsで差はほとんどない
  • ランダム入力では is_leap_year_fast が約3.8倍高速
  • 入力パターンによって分岐(branching)方式の予測が難しい場合に大きな利点がある

結論と実際の適用可否

• 実際の応用では値が予測可能なら利点は小さいが、大量のランダムデータ環境では非常に有用
• 実際にPythonやC#などの標準ライブラリを置き換える際には、現実的なプログラム全体のベンチマークが必要
• アイデアと実装方法そのものが興味深く、特定の状況では性能面で魅力的な解決策となる

[chickendreamtree]

Fast inverse sqrt を思い出させる文章

[GN⁺]

Hacker Newsの意見

• gccやclangのような最新コンパイラが、is_leap_year1 のようなコードを is_leap_year2 のように自動で最適化してくれるという事実に驚いた。なので、Cのソースコード段階で自分で最適化する必要はあまりないのではと思うが、他の言語では依然として有用かもしれない。特に cal プログラムの最新版ソースコードで、うるう年チェックを非常に簡潔に処理している点が印象的だった
  • Linuxのコードが、3つの連続した条件を毎回反転させたりデフォルト値の返却を使ったりせず、ずっと理解しやすい点が気に入った。こういう複雑なコード構造があると、デバッグ時に本当に気が狂いそうになる
• ((y * 1073750999) & 3221352463) <= 126976 というコードがどう動くのかの説明が複雑にならざるをえないことには、まったく驚きはない。むしろ当然だと思う
• 理解しにくいマジックナンバー最適化の手法が大好きだ。こういうものを見るたびに、昔アセンブリで内部ループを書いていた時代にどれだけ多くの最適化手法を見落としていたのか気になる。もしこうしたテクニックをまとめたコレクションがあれば共有してほしい
  • さまざまなビット操作トリックのまとめへのリンク、UNIXスタイルの比較に効率的な CMP(X, Y) マクロ、signum 関数の最適化例、Motorola 68000向けアセンブリコード例へのリンク、OpenSolaris由来のビットマクロ集など、多様な最適化手法のリンクが紹介されていた。Open Solarisのブログが消えてしまったことへの残念さにも触れつつ、コード最適化に関心のある人にはおすすめとのこと
  • 『Hacker's Delight』という本のおすすめ。さまざまなビットトリックや低レベル最適化手法が満載とのこと
  • supercompilation という手法を調べてみるといいという提案
  • 昔はこうした手法を見落としていたわけではなく、当時は乗算が非常に高価だったので、そういうものこそが最適化だった
• うるう年チェックがこんなに面白いとはまったく思わなかった。おそらく低レベルプログラマたちはずっと以前にこうしたトリックを見つけていたが、記録を残していなかったのではないかと思う。こういうものが今でも古いコードの中に潜んでいるかもしれないという感じがするし、こうした手法のコレクションがあればぜひ探究してみたい
  • 80年代にZ80で家で独学したことがあったが、その大半は忘れてしまった。たまに20代の子どもたちに見せると、まるで手品のように感じられる
• 6000年以前のうるう年を知りたいなら、自作のインタラクティブ計算機と可視化ツールを使うとよい。機械命令の数は少し多いものの、非常に高速に何千回もの計算を処理できるし、数学的トリックも感心するポイントだ
• ビット操作の章を読んでいて「もしかしてソルバーが使えるのでは」と思ったが、実際に筆者がまさにその方法を使っていて驚いた。細やかなアプローチに満足した
• こうしたうるう年チェック関数を current-time-api に追加するとよいのでは、という提案
• 数字を2進数で見ると面白いパターンが見える。すべての素数は2を除けば1で終わる、という点が興味深かった
  • 面白く見えるかもしれないが、すべての奇数は1で終わり、素数は本質的に2を除けば偶数になれないのだから、特に意味は感じないという疑問
• うるう年問題では0がないという指摘があった。実際には「0年」はなく、1 BCからそのまま1 ADに移るので、0のチェックには意味がないという話
  • 記事の冒頭を見ると、うるう年アルゴリズム設計の前提として先発グレゴリオ暦と天文学的年数法を使うと説明されている。この条件がなければ、うるう年チェックはロケールごとに複雑になることを強調している
  • 天文学的年数表記を使えば0年が登場し、年や月の管理などではその方がむしろすっきりする。内部データは天文学的表記にし、外部出力だけBCE/CEに変換するという提案
  • グレゴリオ暦導入以前の暦は基準自体が曖昧で地域差もある。1582年には1日で10日分を飛ばした「10日削除」もあったので、それ以前の日付計算は信頼できない。ローマ時代の祭司たちは迷信や賄賂などでうるう年を恣意的に調整することもあり、さらに複雑になる
  • ISO8601標準では0年を許容しており、天文学的暦での0年は1 BCを意味する。BCEの年はすべて -1 ずつオフセットされる
• ソースコードが実際に声を出して笑ってしまうほど面白いことはめったにないので、とても楽しい体験だった