ハクソク

世界を動かす技術を、日本語で。

うるう年の確認を3つの手順で

375日前原文(hueffner.de)

概要

  • is_leap_year_fast 関数は、3命令ほどで閏年判定を実現するビット演算トリックを利用
  • 標準的な閏年判定ロジックと比較しつつ、最適化・ビット操作の流れを解説
  • 魔法定数 の由来・役割、z3による探索方法、ビットパターンの意味を詳細に分析
  • 判定範囲（0～102499年）や、なぜこの範囲で正しいかの理由を説明
  • 実用性や他の高速化手法への言及も含め、ビット操作による最適化の楽しさを紹介

3命令で閏年判定？ビット演算と魔法定数の仕組み

標準的な閏年判定ロジック

  • グレゴリオ暦 （proleptic Gregorian calendar）を前提とし、年0～102499の範囲で判定することを想定
  • 標準的な実装例： 
    bool is_leap_year(uint32_t y) {
  if ((y % 4) != 0) return false;
  if ((y % 100) != 0) return true;
  if ((y % 400) == 0) return true;
  return false;
}
    • 4で割り切れなければ閏年でない（平年）
    • 100で割り切れなければ閏年
    • 400で割り切れれば閏年
    • それ以外は平年とする判定

標準ロジックの最適化

  • 既知の倍数性を活かし、 (y % 100) != 0 を (y % 25) != 0 に、 (y % 400) == 0 を (y % 16) == 0 に変換することが可能
    • 4の倍数でなければ判定終了、25の倍数でなければ閏年、16の倍数なら閏年
  • これにより、4や16での剰余判定はビットマスクで高速化できる（例：y & 3, y & 15）
  • 25での剰余判定も、 定数乗算+比較 で高速化できる（論文参照：Daniel Lemireら "Faster remainder by direct computation" など）

魔法定数によるビット演算判定

  • さらなる高速化を目指し、 ビット演算と定数乗算 による分岐無しの判定式を導出
    • 数式例：((y * f) & m) <= t
      • f, m, tは探索によって得られた「魔法定数」
  • z3などのSMTソルバーで定数を探索し、 0～102499 年の範囲で正しい判定式を発見
    • 実際の定数：
      • f = 1073750999u
      • m = 3221352463u
      • t = 126976u
    • 実装例： 
      bool is_leap_year_fast(uint32_t y) {
  return ((y * 1073750999u) & 3221352463u) <= 126976u;
}

ビット演算の意味と分解

  • 乗算後のビット列を3ブロック（A, B, C）に分けて判定を実施
    • Aブロック ：4の倍数判定（(y % 4) != 0）
    • Bブロック ：100の倍数判定（(y % 100) != 0）、ただし25の倍数性を利用
    • Cブロック ：16の倍数判定（(y % 16) == 0）、400の倍数判定に相当
  • 3つの条件を1つのビット比較にまとめ、 分岐無し・高速 な判定を実現
  • 実際のビット構造や、なぜこの範囲で正しいかは、定数の誤差許容量やビットパターンの周期性に基づく

範囲の限界と実用性

  • 102499年まで しか正確に判定できない理由：
    • 定数乗算による誤差が、ビットパターンの周期性と一致する上限であるため
    • それ以降は、100の倍数の検出が漏れるため誤判定が生じる
  • 実用上、多くのプログラミング言語やアプリケーションは 0～9999年 程度しか扱わないため十分
  • モダンなコンパイラは既に類似の最適化を自動で行う場合も多い

まとめ・応用

  • ビット演算・定数乗算 を活用することで、分岐無し・高速な閏年判定が可能
  • 魔法定数やビットパターンの分析は、 カレンダー計算や最適化技法 の面白さ・奥深さを示す好例
  • 他のカレンダー計算や周期性判定にも応用可能なテクニックであることを確認

参考文献・追加情報

  • Daniel Lemire, Owen Kaser, Nathan Kurz: "Faster remainder by direct computation: Applications to compilers and software libraries"
  • Cassio Neri, Lorenz Schneider: "Euclidean affine functions and their application to calendar algorithms"
  • David Turner: "Identifying leap years"
  • Jacob Pratt: "Optimizing with Novel Calendrical Algorithms"
  • z3 SMTソルバー：ビットベクトル制約の探索に利用可能

このように、 is_leap_year_fast の魔法定数による閏年判定は、ビット操作・数値誤差・周期性を駆使した高度な最適化テクニックの一例であり、実用性とアルゴリズムの面白さを両立していることを確認。

Hackerたちの意見

こういう理解不能なマジックナンバーの最適化が大好きなんだ。見るたびに、昔アセンブリで内側のループを書いてた時に、こういう最適化をどれだけ見逃したのかなって考えちゃう。誰か、こういうののコレクション持ってる？

└

見逃してないよ。あの頃は最適化じゃなかったからね。掛け算は本当に高コストだったし。

└

スーパーコンパイルを見てみるといいよ。

└

ヘンリー・S・ウォーレン・ジュニアの「Hacker's Delight」があるよ。 https://en.wikipedia.org/wiki/Hacker's_Delight

└

ここに短いリストがあるよ: https://graphics.stanford.edu/~seander/bithacks.html リストには載ってないけど、#define CMP(X, Y) (((X) > (Y)) - ((X) 0はコンパイラによって(X > Y)に簡略化される。CMP(X, 0)に相当するsignum(x)関数は、アーキテクチャによっては比較操作なしで3〜4命令で実行できるよ: https://www.cs.cornell.edu/courses/cs6120/2022sp/blog/supero... これは有名な例だから、コンパイラはおそらくCMP(X, 0)をそれに最適化するけど、確認はしてない。偶然にも、CMP(X, 0)の展開がビットハックリストに載ってる。ここにはさらにいくつかの超最適化された数学的操作がリストされてるよ: https://www2.cs.arizona.edu/~collberg/Teaching/553/2011/Reso... アセンブリコードはMotorola 68000プロセッサ用のようで、エッジケースで設定されるフラグを利用しているみたい。最後に、OpenSolaris（私の知る限り）から始まったビット操作用の便利なマクロのリストがここにあるよ: https://github.com/freebsd/freebsd-src/blob/master/sys/cddl/... 以前はOpen Solarisのブログ投稿があったけど、Oracleが削除しちゃった。楽しんで！

ビット操作のセクションの途中で、「ここでソルバー使えないかな？」って思ったら、なんと著者がそのアプローチを取っててびっくりした！この投稿の細部へのこだわりが大好きだ！

もし6000年より前のうるう年を知りたいなら、インタラクティブな計算機とビジュアライゼーションを作ったよ [1]。これは3つ以上の機械命令を使うけど（投稿に含まれている数学的トリックも素晴らしいし）、それでもかなり早く何千もの計算ができるよ :) [1] https://calculang.dev/examples-viewer?id=leap-year

└

ビューポートの幅に合わせて内容を調整してほしいな、今のままだとモバイルで使いづらいよ :)

return ((y * 1073750999) & 3221352463) これってどういう仕組みなの？答えは驚くほど複雑だよね。このアルゴリズムの説明が複雑なのは誰も驚かないと思うけど :D

バイナリの数字を見てみると、面白いパターンが見えてくるよね。ちょっと当たり前に思えるかもしれないけど、2以外のすべての素数が1で終わるって気づいたときは興味深かったな。

└

ちょっと意地悪なこと言うつもりはないけど、それがなんで面白いの？奇数は1で終わるってことと、素数はその性質上偶数になれない（2を除いて）ってこと以上に何か見落としてる？

gccやclangのような現代のコンパイラは、is_leap_year1からis_leap_year2みたいなものを生成するから、Cのソースでこれをやる意味はあまりないけど、他のプログラミング言語では役立つかもしれない。コンパイラが達成できる最適化には本当に驚かされるよね。実際、util-linuxの最新バージョンのcalはCのソースでシンプルに保ってる：return ( !(year % 4) && (year % 100) ) || !(year % 400); https://github.com/util-linux/util-linux/blob/v2.41/misc-uti...

└

Linuxのやつは、最後の2つの条件を反転させる3つの連続チェックを行わないから、理解しやすいのがいいよね。これってデバッグする羽目になったら本当にイライラするやつだよ。

└

でもこれは間違ってるし、ユリウス暦からグレゴリオ暦に切り替えた特定の年以降の日付しか表せないよ！これについてもっと知りたいなら、曜日を計算する関数を読んで実装することをお勧めするよ [1]。そしたら、人間のカレンダーに対処しようとしている人たちの特別な狂気の地獄に私と一緒に入れるよ。そして、1582年10月4日木曜日から1582年10月15日金曜日までの日付のテストケースも実装すべきだね :) [1] https://en.m.wikipedia.org/wiki/Determination_of_the_day_of_...

かわいいバイナリや論理のトリックがたくさんあるから、好きならHackers Delightやhttps://graphics.stanford.edu/~seander/bithacks.htmlを読んでみてね。十分に勉強したら、もっと簡単に思いつくようになるよ。注意：これは、ビット操作を深く理解していない人にとっては可読性の問題よりも、重要なパフォーマンスの違いをもたらす問題に遭遇する運がどれだけあるかによって、プログラマー仲間との人気が上がったり下がったりするかもしれない。さまざまな目的のために乗算とマスクを使うのは、私のコードでもよく使うことだよ。今は数十年前よりずっと魅力的だね、だって最近のほとんどのコンピュータは非常に速い乗算器を持ってるから。これらのフルワイド論理演算と乗算器は、単一の命令に非常に並列なコンピュータを詰め込んでいるようなもの。唯一の問題は、プログラムするのがちょっと難しいことかな。:) 少なくともこれは機械的に説明するのが簡単だったよ。一部のビットハックはp-adic数や数論の他の要素を説明するのに必要だね。

ちょっと関連する話。 >「じゃあ、Lotus 123のバグなの？」 >「うん、でも多分意図的なものだね。Lotusは640Kに収めなきゃいけなかったから。それはあまり多くないメモリだよ。1900年を無視すれば、与えられた年がうるう年かどうかは右端の2ビットがゼロかどうかを見るだけでわかる。これは本当に速くて簡単だよ。Lotusの人たちは、過去の2ヶ月間に間違っても問題ないと思ったんじゃないかな。Basicの人たちはその2ヶ月について厳密にしたかったみたいで、エポックを1日戻したみたい。」 https://www.joelonsoftware.com/2006/06/16/my-first-billg-rev...

└

すごく面白かった！シェアしてくれてありがとう！

これめっちゃクールだね！ちょっとした指摘だけど、実際にはこれは3つの操作で、指示じゃないよ。x86だと4つあるんだ：is_leap_year_fast: imul eax, edi, 1073750999 と eax, -1073614833 cmp eax, 126977 setb al ret ARMだと命令エンコーディングの関係でちょっと多くなるよ：is_leap_year_fast: ldr r1, .LCPI0_0 mul r0, r0, r1 ldr r1, .LCPI0_1 and r1, r0, r1 mov r0, #0 cmp r1, #126976 movwls r0, #1 bx lr .LCPI0_0: .long 1073750999 .LCPI0_1: .long 3221352463 コンパイラエクスプローラーのリファレンス: https://godbolt.org/z/7ajYqbT9z

└

setb と ret は、実際のうるう年チェックには含まれないって言えるかもね。例えば、コンパイルされたコードが呼び出し元でこうなってたら：if(is_leap_year_fast()) {...} そしたら、ret は明らかに必要なくなるし、setb も cmp の結果から直接条件付きの jmp を生成できるから、いらなくなるよね。

gcc と clang は、元の関数を -O3 でコンパイルするときにビット操作のトリックを使ってるみたいだね： https://godbolt.org/z/eshd9axod is_leap_year(unsigned int): xor eax, eax test dil, 3 jne .L1 imul edi, edi, -1030792151 mov eax, 1 mov edx, edi ror edx, 2 cmp edx, 42949672 ja .L1 ror edi, 4 cmp edi, 10737418 setbe al .L1: ret

└

数学的な同一性を使って簡略化するのが得意なことがあるよね。以下のコミットは実際にGCCの出力からインスパイアされたんだ： https://github.com/openzfs/spl/commit/8fc851b7b5315c9cae9255... ジェイソンは、PaX GCCプラグインが出力した符号なし整数オーバーフロー警告の解決策を探しているときに、GCCのアセンブリ出力が元のマクロと一致しないことに気づいたんだ（私の意見では誤りだと思う）。彼は、GCCのバージョンを安全に採用できるんじゃないかと推測したんだ。私はコミットメッセージの正当性の証明を彼に渡して、それがZFSに受け入れられたよ。証明からもわかるように、元のものから導出するのに4つのステップが必要だったんだ。GCCも似たようなプロセスを経て出力を導出したんだと思うよ。