3命令のCPU処理で済む高速なうるう年判定アルゴリズム - Faith and Brave - C++で遊ぼう

要約 この短いコードで、西暦102499年までのうるう年を判定できます。このマジックナンバーはz3というSMTソルバーで見つけ出されました。 bool is_leap_year_fast(uint32_t y) { return ((y * 1073750999) & 3221352463) <= 126976; } はじめに GCC (libstdc++) のうるう年判定のアルゴリズムが、以下のように変更になりました (commit)。 constexpr bool is_leap() const noexcept { - return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0; + const auto __y = static_cast<uint32_t>(_M_y) + 32800u; + return ((__y * 1073750999u)

[gengesa]

ErgoBo(dotnet の開発チームの主要メンバー)が実測したら閏年じゃないならyear%4!=0で終わるから速いとリプライしていた。非閏年が来るのは75%強だとするとこちらを遅くするのは期待値としてどうなのかという視点も要りそう。

[naoya2k]

だが68000ならどうかな? (詭弁のガイドラインにもあるごく稀な反例) → 従来アルゴリズムでは%25が遅いが25=5*5であることを利用してDIV命令を使わない最適化ができて72～170clock 。今回のものは32bit乗算が遅くて228clock固定

[NAPORIN]

“研究や職人技で見つけられていた高速化のためのマジックナンバーの発見を、だれでもできるような環境が整ったのだな、というのが今回の大きな発見・気づきでした。 z3を使った最適化は、コンパイラ開発などではすで

[mohno]

↓id:asakura-t ←早期リターンの補足は追記ですね（archive.orgより）/ライブラリの中なら最速を追求するのはいいけど、演習で「ツェラーの公式」とか使われると検索したよねってなる（今だと生成AI）。

[sgo2]

記事中に有るけど、近年のCPUではelseケースでのペナルティ(パイプライン再構築)が重い。https://qiita.com/aosho235/items/60bd41a5b41bcc3b6ea9

[asakura-t]

↓早期リターンについては記事にあるけど、あとで追記されたのかな？

[daruyanagi]

“すべての入力に対して正確な結果を返す、というのを諦めて範囲を狭めることで、うるう年判定をより高速化できるのではないか……実際、PythonやC#では西暦9999年までしかサポートされていない”

[wepon]

102500年問題

[aceraceae]

あとからみるとこういう謎技術にしかみえない高速化の話って好き。

[zu2]

MC6800だと乗算が遅いので…

[kirarapoo]

高速なう（帰省の道中）

[twmw]

うるう年判定界隈に革命が起こる🤔

[nakag0711]

さすがにこれだけ単純だとテーブルルックアップより速いかな

[nguyen-oi]

z3でマジックナンバー探させるの現代の黒魔術感あって面白いな。人間が理解できない最適化コードが標準ライブラリに増えていく未来