うるう年判定

前にうるう年判定するアルゴリズムは x86 だと綺麗だとかいう話を雑談でしました。というわけで地味に綺麗なアルゴリズムシリーズ。(前回はライフゲーム)

 1. 西暦年が4で割り切れる年は閏年
 2. ただし、西暦年が100で割り切れる年は平年
 3. ただし、西暦年が400で割り切れる年は閏年

だそうです。 C とかで書くと、 y%4==0 ? (y%100==0 ? (y%400==0 ? 1 : 0) : 1) : 0 とかでしょうか。これはまぁ人間の考えてる定義通りの実装ですしまぁコードに落とすならそのままやるんがわかりやすいかと思います。

ただ、 1 と 3 と、飛び飛びでうるう年になる条件が出てくるのがややこしいと言えばややこしいので、少しだけひねってやると、

 1. 100 で割り切れるなら a = 400 、そうでないなら a = 4
 2. a で割り切れる年は閏年

と真になる地点を一箇所にまとめることができます。 C で書くなら y%(y%100>0?4:400)==0 という感じでしょうか。

でこの変形したバージョンが C はともかく、 x86 には綺麗にはまる。

.globl  leap
leap:
        mov 4(%esp), %eax
        mov $100, %ecx
        xor %edx, %edx
        idiv %ecx             ; とりあえず 100 で割ってみる
        cmp $0, %edx
        jne .l
        mov %eax, %edx        ; 割り切れたら商を余りのところに持っていく
.l:
        and $3, %edx          ; で 4 で割ってみれば終わり
        sete %al
        ret

タネは x86 では除算を計算すると %edx に余りが、 %eax が商が、という具合に二つが同時に計算されることにあって、 100 で割ってみて、割り切れたなら商を、割り切れなかったら余りを 4 で割れば、さっきのアルゴリズムが実現できる、というところにある。

とりあえず 100 で割ってみれば、割り切れた時に商を使えば 4 で割っても 400 で割ったのと同じ効果が得られるし、 x86 の div は元の値とかぶっこわしまくるけど、わざわざ元の値の復元とかしなくても、 100 は 4 の倍数なので、残った余りを単に 4 で剰余取っても結果は同じ、という。

別にこれは速度が速いということもなくて(たぶん逆数をかけた方が速いだろう)、直感的にわかりやすい定義でもないんだけど(人間は if 文連打は得意だし)、なんか綺麗におさまってて良い。

この論理は他の言語でもなかなか良くて、Brainfuck でうるう年を判定をした時 (この時はうるう年判定なんかはおまけで、 wday の方が大変だったけど) は、どうせ Brainfuck は 1 セルにおさまるのは 256 までなので、 100 進数で 2 セルを使って年を表現していて、下位の方が 0 じゃなかったらその数値を上位の方に持っていって、上位の方を 4 で割る、とかでだいぶ楽に計算できた。

あとは Ruby とか Perl で /00$|$/ を評価してから $` について 4 で割れるか調べる…なんていうのもなかなか。ゴルフで割と使われてました。

追記:

http://homepage1.nifty.com/herumi/diary/latest.html#15

x86 についてゴルフ的に最適じゃないとご指摘いただきました。 sete は故意にこうしてました。 cmovnz はぱっと見がわかりにくくなるかなと思ったんですが別に使ったら良かったなと思いました。 cdq はそもそも知りませんでした…てかカルトクイズに書いておられたのに忘れてた。