週の曜日を計算するより速い方法

週の曜日を計算するより速い方法 コンパイラの出力を超える高速な剰余演算テクニックの数々 2026年8月17日 日付の通算日数（rata-die）を曜日に変換する（weekday）という作業は、非常に単純なものに思え、ほとんど語るべきことがないように感じられるかもしれません。しかし、実際には、この問題は驚くほど複雑であることがわかります。 この記事では、さまざまなユースケース（スループット対レイテンシ、異なるプラットフォームなど）に合わせて調整された、この問題を解決するための非常に高速な関数の数々を紹介します。それぞれが既存のソリューションを上回り、多くは単一の乗算と2サイクルというレイテンシを実現しています。驚くべき結果として、ISO形式（[0〜6]ではなく[1〜7]）の曜日を、わずかに定数を変更するだけで（速度ペナルティなしで）全く同じ命令で計算できることが示されています。 その狂気の一端を示すために、私のお気に入りの関数をここに紹介します。この一見奇妙な3命令シーケンス（定数ロードを除く）は、符号付き32ビットの全範囲で正確です（この記事で紹介されている全範囲アルゴリズムの中で最低レイテンシではないかもしれませんが、x86では最も高いスループットを持っています）。 Unix 曜日 [0〜6] ISO 曜日 [1〜7] 与えられたもの：入力（rd = 符号付き32ビットの日付通算日数）; 曜日 [0〜6] を計算する： mov eax, 613566756 ; 定数ロード: u32 M = (1 << 32) / 7 imul ecx ; rd * M (u32 a = 下位ビット、i32 b = 上位ビット) lea eax, [eax-1828716544+edx*4] ; u32 r = a + 4 * b + (Z = 0x93000000) shr eax, 29 ; weekday = r >> 29 このブログ記事を理解するために、アセンブリ言語の予備知識は必要ありません。 最後まで読めば、上記のコードがなぜ機能するのかが理解できるでしょう。 上記の関数がどのようにして目的の出力を生成するかを視覚化したもの。3行目の定数は回転角として機能します。 この記事は、低レベルのビット操作、高性能な日付ライブラリ/データベースエンジンの最適化、コンパイラ作成者、そして一般的にクレイジーな人々を対象としています。ここで使用されているテクニックは、x % (2^N - 1) に一般化でき、x % 24 や x % 60 のような他の除数に対する新しい高速剰余テクニックも紹介されており、これらは時間管理に適用可能です。 ライブラリにコピー＆ペーストしてベンチマークを実行したいだけの場合は、「Function Explorer」にジャンプできます。そこには、このページにあるすべてのコード例がC++でコピー＆ペースト可能な形式で用意されています。 最速アルゴリズムの相対速度（概算） AMD Ryzen 9 および Apple M4 Pro プロセッサーでテスト済み （数値が小さいほど速い） ベンチマークセクションで具体的な結果をご覧ください。 その他 （double-mod、Rust:rem_euclid、Hinnant） 〜1.5-3倍 Neri（2024） 1倍 新しいアルゴリズム（2026） 〜0.3-0.5倍 記事セクション： 単純なアプローチ Hinnant Neri 不合理に高速な乗算・加算・シフトアルゴリズム 64ビット幅拡張による高速な全範囲計算 高速な全範囲計算（バリアント1：シフト） 高速な全範囲計算（バリアント2：2回の乗算） 高速な全範囲計算（バリアント3：上位ビット＋下位ビット） Function Explorer 一般化 締めくくりの考察 付録A. ベンチマーク結果 付録B. 2のべき乗パディングによる剰余の証明 単純なアプローチ（ディープリンク） 与えられたもの：rd = rata-die（日付通算日数、符号付き32ビット整数）、エポック1970-01-01 = 木曜日（4） — その後： Double-mod（符号付き「%」を持つ言語、例：C/C++） weekday = ((rd % 7) + 7 + 4) % 7 特殊な正の剰余（例：Rust）を持つ言語 weekday = (rd + 4) POSMOD 7 — ここで: weekday ∈ [0〜6]（0 = 日曜日） これは、メンテナンスがマイクロ最適化よりも重要な、ほとんどのライブラリ以外のコードで推奨するものです。 Rustの例は、上位4つの入力でオーバーフローしますが、それらは気にしないと仮定します。 加算の4（または11 = 7 + 4）は、Unixエポック1970-01-01が木曜日であったことに起因します。曜日の番号付けが異なる場合や、異なるエポックを使用する場合は、これが異なる場合があります。 これらの「単純なアプローチ」は目的を果たしますが、Rustの正の剰余関数（rem_euclid）の場合でも、Cスタイルの疑似コードに変換すると以下のようになり、非常に遅いです。 Rustのrem_euclid（コンパイルされた疑似コード相当）Godboltで表示 i32 a = (i64(rd + 4) * -1840700269) >> 32 // 注意：この疑似コードは、符号付き加算のオーバーフローが i32 b = rd + 4 + a // Rustの定義（2の補数）に従うと仮定しています。 i32 c = (b >> 2) + (u32(b) >> 31) // C/C++では未定義ですが。 i32 d = rd - c * 7 i32 e = d + 4 u32 weekday = e >= 0 ? e : d + 11 予想よりも多くのステップがありますね。 Hinnant（ディープリンク） Howard Hinnantのテクニック（2014）は、多くの日付ライブラリで採用されています（元の記事を参照）。 Hinnantのアルゴリズム（ビットサイズ非依存） 範囲：INT32_MIN → INT32_MAX − 4 weekday = rd >= -4 ? (rd + 4) % 7 : (rd + 5) % 7 + 6 このアプローチは、シンプルさと柔軟性を重視して設計されているようです。ここからのアルゴリズムの中で、符号キャストやオーバーフローに依存せず、ビット幅にも依存しない唯一のものです。8ビットから64ビットまで、ロジックは同じです。 Hinnantは、このアルゴリズムが符号付き32ビットの全範囲をカバーしていると指摘していますが、上位4つの入力は例外です。これらはC/C++では極端な値（580万年以上先）で未定義の動作を引き起こします。実際には、2の補数マシンではこれらの値でも機能することが多いですが、コンパイラによって保証されているわけではありません。 このアルゴリズムは、最初の棒グラフでは非常に高速とは提示されていませんが、Raspberry Pi Zero（およびおそらく古いチップ）では非常に高速です。 Neri（ディープリンク） いつものように、Cassio Neriの研究は現代のゴールドスタンダードです。2024年にNeriは、この問題に対する非常にクリーンな全範囲ソリューションを発表しました（投稿を参照）： Cassio Neri: 32ビット版 （範囲：符号付き32ビット全範囲） weekday = (u32(rd) + (rd >= 0 ? 4 : 0)) % 7 Cassio Neri: 64ビット版 （範囲：符号付き64ビット全範囲） weekday = (u64(rd) + (rd >= 0 ? 4 : -5)) % 7 比較的高速で、全範囲をカバーし、あまり低レベルすぎないものを求めるなら、この関数が最適です。 オーバーフローを回避する本当のトリックは、作業を行う前に符号付きから符号なしへのキャストを行うことです。 興味深いことに、32ビット版では、負の数に対して加算ゼロが適用されます。これは、2^32 % 7 = 4 という性質によるもので、4の加算がすでに組み込まれているためです。もしこれがゼロでなかった場合（例えば、日曜日を0として扱わない場合）、速度は低下しません。異なるビット幅でこの2番目の定数が何になるかを計算するには、次を使用します：- ((3 + 2^BIT_WIDTH) % 7) これは、可能な限り高速であるように思えますね。 速度を上げるには、アセンブリを見る必要があります。GCCとClangは、以下の計算を行うアセンブリを出力します。 Neri、32ビット版（コンパイルされた疑似コード相当）Godboltで表示 u32 a = u32(rd) + (rd >= 0 ? 4 : 0) u32 b = ((u64) a * 613566757) >> 32 // ≈ a / 7（概算商） u32 c = (((a - b) >> 1) + b) >> 2 // 修正された商 u32 weekday = a - c * 7 // または: a + c - (c << 3) 注意：3行目には、最初の近似値をa / 7に修正するために、4つの逐次依存操作が含まれています。7は扱いにくい除数であり、32ビットレジスタに収まらないマジック逆数乗数が必要なため、このような修正項が必要です。 ridiculousfishが2011年に発表した「libdivide」テクニックを使用すると、さらに高速な方法があります。これは、入力に飽和インクリメントを適用し、丸めダウン乗数を使用することで、修正行全体を排除します。これを使用すると、私のテストでは約10％高速になりますが、さらに高速な方法もあります。まず、範囲要件を減らすことから探求してみましょう。 不合理に高速な乗算・加算・シフトアルゴリズム（ディープリンク） 限定的だが有用な範囲で、乗算、加算、右シフトだけで曜日を計算できることがわかりました。 Unix 曜日 [0〜6] ISO 曜日 [1〜7] 32ビット版（限定範囲） 入力範囲：-89,434,796 から 89,522,175 有効な日付：-242,895-11-06（月曜日：1）から 247,073-05-23（金曜日：5） const u32 M = (1 << 32) / 7 + 1 // 613,566,757 const u32 Z = 0x94920000 // 2,492,596,224 weekday = (u32(rd) * M + Z) >> 29 C++バージョンについては、Function Explorerの#fn=32unix_narrowを参照してください。 わずか3つの操作です。明らかにこれは高速に実行されるでしょうが、一体どうやって機能するのでしょうか？ 左側の関数がどのようにして目的の出力を生成するかを視覚化したもの。定数「Z」は回転角として機能します。 剰余演算は通常、より多くのステップを必要とします。私たちができる理由は