HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

A faster way to calculate the day of the week (benjoffe.com)

200 pointsby gavide47 コメント

要約

この記事では、日付の通算日数(rata-die)から曜日(weekday)を計算するための、コンパイラの出力を超える高速な剰余演算テクニックを複数紹介しています。特に、単一の乗算と2サイクルで完了する低レイテンシの関数や、x86プラットフォームで高いスループットを発揮する3命令シーケンスなどが提示されています。これらの手法は、低レベルのビット操作やパフォーマンス最適化に関心のある開発者向けに解説されています。

全文翻訳

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

その他の日付/時刻関連記事:

コンパイラ出力を凌駕する、高速な剰余演算技術の数々

2026年8月17日

日単位のカウント("rata-die")を 曜日 *("weekday")に変換するというのは、あまりにも些細なことのように思えるため、語るべきことはほとんどないように思えます。しかし、調べてみると、これは驚くほど複雑な問題であることがわかります。

この記事全体を通して、さまざまな非常に高速な関数を紹介し、この問題を解決します。これらは、さまざまなユースケース(スループット対レイテンシ、異なるプラットフォームなど)に合わせて調整されています。各(フルレンジ32ビットアルゴリズム)は既存のソリューションを上回り、多くは乗算1回と2サイクルというレイテンシで動作します。驚くべき結果として、曜日はISO形式([1‥7]、[0‥6]ではなく)で、まったく同じ命令で、定数を調整するだけで(速度ペナルティなしで)計算できることが示されています。

その狂気の一端をお見せするために、ここでは私のお気に入りの関数をハイライトします。このクレイジーに見える3命令シーケンス(定数ロードを除く)は、フルサイン付き32ビット範囲で正確です(レイテンシが最も低いわけではありませんが、x86では最も高いスループットを持っています):

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

与えられたもの: input (rd = サイン付き32ビットUnix日単位カウント); 計算するもの: weekday [0‥6]:

  1. mov   eax, 613566756                u32 M = (1 << 32) / 7
    
  2. imul  ecx                          rd * M  
    
  3. lea   eax, [eax-1828716544+edx*4] u32  r = a + 4 * b + (Z = 0x93000000)
    
  4. shr   eax, 29                     weekday = r >> 29
    

このブログ記事を理解するために、アセンブリの事前知識は必要ありません。
この記事の終わりには、上記のコードがなぜ機能するのかを理解できるようになります。

上記の関数がどのようにして目的の出力を生成するかを視覚化したもの。3行目の定数は回転角度として機能します。

この記事は、低レベルのビット操作、高性能な日付ライブラリ/データベースエンジンの最適化、コンパイラ作者、そして一般的にクレイジーな人々を対象としています。ここで使用されているテクニックは、x % (2^N - 1)に一般化でき、x % 24やx % 60などの他の除数に対する新しい高速剰余演算技術を紹介しています。これは時刻計算に適用可能です。

ライブラリにコピー&ペーストしてベンチマークを実行したいだけなら、このページにあるすべてのコード例をコピー&ペーストできる「Function Explorer」にジャンプできます。C++用です。

最速のフルレンジ32ビットアルゴリズムの近似相対速度
AMD Ryzen 9およびApple M4 Proプロセッサでテスト済み
(数値が小さいほど高速)
このページにあるベンチマークセクション(benchmark section)で具体的な結果を確認してください。

**その他
(ダブルモジュロ、Rust:rem_euclid、Hinnant)
~1.5-3+倍

Neri*(2024)***

1倍

新しいアルゴリズム(2026)**

~0.3-0.5倍

記事セクション:

単純なアプローチ ディープリンク

与えられたもの: ***rd*** = *rata-die* (日単位カウント、サイン付き32ビット整数)、エポック 1970-01-01 = 木曜日(4) — 結果:

ダブルモジュロ (サイン付き "%" を持つ言語、例: C/C++)

  1. weekday = ((rd % 7) + 7 + 4) % 7
    

正のモジュロを持つ言語 (例: Rust)

  1. 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で表示 [画像]

  1. i32 a = (i64(rd + 4) * -1840700269) >> 32
    
  2. i32 b = rd + 4 + a                          
    
  3. i32 c = (b >> 2) + (u32(b) >> 31)
    
  4. i32 d = rd - c * 7                          
    
  5. i32 e = d + 4
    
  6. u32 weekday = e >= 0 ? e : d + 11
    

予想よりも多くのステップですね。

Hinnant ディープリンク

Howard Hinnantの技術(2014年)は、多くの日付ライブラリで採用されています(元の記事 [画像]を参照)。

Hinnantのアルゴリズム (ビットサイズ非依存)
範囲: INT32_MIN → INT32_MAX − 4

  1. weekday = rd >= -4 ? (rd + 4) % 7
    
  2.                    : (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ビット)

  1. weekday = (u32(rd) + (rd >= 0 ? 4 : 0)) % 7
    

Cassio Neri: 64ビット版
(範囲: フルサイン付き64ビット)

  1. weekday = (u64(rd) + (rd >= 0 ? 4 : -5)) % 7
    

かなり高速で、フルレンジで、あまり低レベルすぎないものを求めているなら、この関数が最適です。

Neriの主な動機は、Hinnantのアルゴリズムのオーバーフローを克服することでした。ここでオーバーフローを回避する本当のトリックは、作業を行う前に符号付きから符号なしへのキャストです。興味深いことに、32ビットバージョンでは、2^32 % 7 = 4であるため、負の数にはゼロの加算が適用され、4の加算はすでに組み込まれています。もしこれがゼロでなかった場合(例えば、日曜日を0としない場合)、速度は遅くなりません。この2番目の定数が異なるビット幅で何になるかを計算するには、- ((3 + 2^BIT_WIDTH) % 7)を使用します。

「かなり高速であるべきだと思いませんか?」
さらに高速化するには、アセンブリを見る必要があります。GCCとClangはどちらも以下の計算を行うアセンブリを出力します。

Neri、32ビット版 (コンパイルされた疑似コード相当) Godboltで表示 [画像]

  1. u32 a = u32(rd) + (rd >= 0 ? 4 : 0)
    
  2. u32 b = ((u64) a * 613566757) >> 32 
    
  3. u32 c = (((a - b) >> 1) + b) >> 2
    
  4. u32 weekday = a - c * 7            
    

行3には、a / 7の初期近似を修正するための、直列に依存する4つの操作が含まれていることに注意してください。このような修正項は、7が協調性のない除数であり、32ビットレジスタに収まらないマジック逆数乗数に32ビット以上を必要とするため必要です。

「libdivide」テクニック(ridiculousfishが2011年に発表 [画像])を使用すると、さらに高速な方法があります。これは、入力に飽和インクリメントを適用し、丸め込み乗数を使用することで、修正行全体を削除します。これを使用すると、私のテストでは約10%高速になりますが、さらに高速な方法もあります。まず、範囲要件を減らすことから始めましょう。

不合理に高速な乗算-加算-シフトアルゴリズム ディープリンク

制限されたが有用な範囲で、乗算、加算、右シフトだけで曜日を計算できることがわかりました。

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

32ビット版 (制限範囲)
入力範囲: -89,434,796 から 89,522,175
有効な日付: -242,895-11-06 (月: 1) から 247,073-05-23 (金: 5)

  1. const u32 M = (1 << 32) / 7 + 1
    
  2. const u32 Z = 0x94920000         
    
  3. weekday = (u32(rd) * M + Z) >> 29
    

C++バージョンについては、Function Explorerの#fn=32unix_narrowを参照してください。

わずか3つの操作です。明らかにこれは高速に実行されますが、どうやって機能するのでしょうか?

左側の関数が目的の出力をどのように生成するかを視覚化したもの。定数「Z」は回転角度として機能します。

剰余演算は通常、より多くのステップを必要とします。操作がこれほど少なく済む理由は、7がメルセン数、つまり2N − 1の形式であるためです。そのような数では、N % 7 = floor(N * 8 / 7) % 8のような恒等式を利用できます(この等式の証明については付録Bを参照)。

* 8 / 7を~1.142857...の乗算と右シフトで近似して実装します。通常、乗算シフトは上位ビットを取りますが、ここでは下位ビットを取り、右シフトがレジスタサイズより正確に3少なくなるようにします。最終的な% 8は、3ビットしか残らないという事実により、無料で提供されます。

結果にZの値を加えることで、Unixエポックが木曜日であることを調整して、出力値を効果的に回転させます。Z = 0x90000000の値は、出力値がバランスの取れた入力範囲を正確に±89,478,489(32ビット空間の1/24)でISO形式[1..7]になるように回転させます。Unix形式[0..6]バリアントの場合、私はZ = 0x94920000を選択しました。これはほぼ完璧にバランスの取れた範囲ではありませんが、下位2バイトがゼロであるため、ARMでのわずかな速度上の利点があります。

コードの右側にある図は、この乗数が円の8つの異なるセグメント(上位3ビット)にどのように当たるかを視覚的に示しており、サイクルごとに1つの値をスキップします。矢印はわずかに「扇形に広がって」います。これは、私たちの乗数が2^29 * 8 / 7の近似にすぎないことを表しています。最終的にこの広がりが誤った戻り値を引き起こすため、範囲が制限されます。

このアルゴリズムはどこでも超高速ですが、特にARMでは高速です。ARMでは、乗算と加算が単一のMADDアセンブリ操作に融合されます。さらに、ARMの多くの操作では融合された右シフトが可能であるため、後続のコードも>> 29項と融合する可能性が高いです。これは実際には、単一のARMアセンブリ操作にコンパイルされる可能性があることを意味します!

この手法の妥当性に関する別の視覚的なガイドは、以下の表です。ここでは、Unixモードで出力値111 (7)がサイクルごとにスキップされ、ISOモードで出力値000がスキップされていることがわかります。

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

rata_die

曜日

a = u32(rata_die

  • 613566757)

r = u32(
a + 0x94920000
(2,492,596,224))

rをバイナリで表示

r >> 29

正しいか?

5

2

3,067,833,785

1,265,462,713

01001011011011010110110110111001

2

パス

4

1

2,454,267,028

651,895,956

00100110110110110010010010010100

1

パス

3

0

1,840,700,271

38,329,199

00000010010010001101101101101111

0

パス

2

6

1,227,133,514

3,719,729,738

11011101101101101001001001001010

6

パス

1

5

613,566,757

3,106,162,981

10111001001001000100100100100101

5

パス

0

4

0

2,492,596,224

10010100100100100000000000000000

4

パス

-1

3

3,681,400,539

1,879,029,467

01101111111111111011011011011011

3

パス

-2

2

3,067,833,782

1,265,462,710

01001011011011010110110110110110

2

パス

-3

1

2,454,267,025

651,895,953

00100110110110110010010010010001

1

パス

日付ライブラリが±242,000年未満の範囲しかサポートしない場合、この手法を使用できる可能性があります。例として、RustのJiff日付/時刻ライブラリ [画像]があります。これは±10,000年の範囲をサポートしています。このアルゴリズムの採用 [画像]により、以前はRustのrem_euclid関数を使用していたnth_weekday_of_monthなどの上位関数の速度が40%向上しました。

この記事の残りの部分は、フルレンジ日付ライブラリで同様の速度を達成することを目指します。

64ビット拡張による高速フルレンジ ディープリンク

32ビット入力ドメイン全体に範囲を拡張する最も簡単な方法は、64ビットに拡張することです。

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

64ビット拡張バージョン
入力範囲: フル32ビット: -2^31 から 2^31-1
有効な日付: -5,877,641-06-23 (火: 2) から 5,881,580-07-11 (金: 5)

  1. const u64 M = 0x2492492493000000  
    
  2. const u64 Z = 0x9400 << 48
    
  3. weekday = (u64(rd) * M + Z) >> 61
    

C++バージョンについては、Function Explorerの#fn=32unix_widenを参照してください。

左側の関数が目的の出力をどのように生成するかを視覚化したもの。定数「Z」は回転角度として機能します。

[更新]このバリアントは、Webkit [画像]によって採用されました。 [ソース [画像]]

64ビット拡張バージョンは、調整された乗数を使用しています。ceil(2^64 / 7)の代わりにceil(2^40 / 7) × 2^24を使用しました。ここでも、ARMアセンブリをよりコンパクトにするために下位ビットはゼロにされています。試行錯誤により、必要な最小バイト数を見つけました。

円グラフの矢印がもはや扇形に広がっていないことに注意してください。これは、この手法によって提供される追加のビット精度によるものです。

Function Explorerには、64ビット入力用に調整されたバリアントがあります(#fn=64unix_narrowを参照)。ここでは、非丸め込み乗数がより広い範囲に使用され、100万億年以上に及びます(誰にとっても十分でしょう)。

「不合理に高速」 - 事前作業

この記事のために調査している間に、このメルセンヌ数トリックに気づいたのは私が最初ではないことを発見しました。これに非常に似た手法が最初にHacker's Delight(§10–20、Remainder by Multiplication and Shifting Right)に登場しました。この本には次のような例があります。

**Hacker's Delight - 非符号整数 N mod 7 技術 (部分範囲)
(非符号32ビット範囲の3.125%で正確)
与えられたもの: x 整数 [0 .. 134,217,734] — 結果:

  1. u32 n = u32(x * 613566756) >> 29
    
  2. x_mod_7 = n & (i32(n - 7) >> 31)    
    

この本では、すべてのケースで丸め込み乗数ではなく、丸め込み解除乗数を使用しています。この乗数は多くの場合(mod 7を含む)悪い範囲を与えるだけでなく、行2の修正が必要になります。これにより、この手法の速度上の利点の一部が失われます。

-- [2026年8月20日 - 更新] Neriもこのトリックに精通しており、メルセンヌトリックの修正なしの丸め込みおよび丸め込み解除バリアントを32ビット(制限範囲) [画像]および64ビット [画像]で実装していたことを知らされました。

この本『Hacker's Delight』に出会えてよかったと思います。なぜなら、フルレンジに拡張するための次の技術を学んだからです。

**Hacker's Delight - 非符号整数 N mod 7 技術 (フルレンジ)
与えられたもの: x (非符号32ビット整数) — 結果:

  1. u32 n = u32(x * 613566756 + (x >> 1) + (x >> 4)) >> 29
    
  2. x_mod_7 = n & (i32(n - 7) >> 31)    
    

強調表示された修正項は、「理想的な」乗数 2^32 / 7 = 613566756**.5714...** の小数部分に関連しています。
この小数部分は正確には4 / 7です。修正 (x >> 1) + (x >> 4) = 1/2 + 1/16 = **0.5625** は、「理想的な」不足分をよく近似しています。

これらの修正項を利用しますが、行2の修正マッピングを使用する代わりに、Z回転を引き続き使用します。

高速フルレンジ (バリアント1: シフト) ディープリンク

Hacker's Delightの修正項(丸め込み解除乗数と組み合わせて)を使用すると、次のようになります。

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

フルレンジ32ビット版 (バリアント1)
入力範囲: フル32ビット: -2^31 から 2^31-1
有効な日付: -5,877,641-06-23 (火: 2) から 5,881,580-07-11 (金: 5)

  1. const u32 M = (1 << 32) / 7
    
  2. const u32 Z = 0x95000000         
    
  3. const u32 a = u32(rd) * M + Z
    
  4. const u32 b = (rd >> 1) + (rd >> 4)
    
  5. weekday = (a + b) >> 29
    

C++バージョンについては、Function Explorerの#fn=32unixを参照してください。

左側の関数が目的の出力をどのように生成するかを視覚化したもの。定数「Z」は回転角度として機能します。

理論的には、これは単一の乗算プラス2サイクルという低レイテンシになることがあります。実際には、コンパイラがアセンブリ出力をどれだけうまく最適化するか(GCCが最適)、およびターゲットプロセッサのパフォーマンス特性によって異なります。

鍵となるのは、標準的な7による除算とは異なり、b = (rd >> 1) + (rd >> 4)のような修正項の計算は、入力値にのみ依存し、先行する計算には依存しないことです。これにより、rd * Mの乗算が行われている間にbを計算できます。

最新のx86プロセッサはスーパースカラーであり、通常、乗算と同時にシフトを実行できます。乗算は通常3サイクルかかるため、rd * Mとbは同時に準備ができます。LEAアセンブリ命令は、これらの2つの結果とZを1ステップで加算することを可能にします(ただし、一部のチップでは2サイクルかかる場合があります)。

このスーパースカラーの側面は、bの計算の有無によるベンチマークを観察することで確認できます。私のテストでは、多くの場合、レイテンシ結果は同じです。さて、日付ライブラリの日付範囲が小さい場合、それでも削減された範囲の32ビットアルゴリズムのいずれかを選択するかもしれません。レイテンシが削減されるからではなく、スループットが高いためです。これは、乗算が発生している間に、時刻計算の開始など、コードが他のことを行えることを意味します。

スーパースカラーx86アセンブリステップ

ステップ

計算1

計算2

1

a = rd * M

t1 = (rd >> 1)

2

mul-latency

t2 = (rd >> 4)

3

mul-latency

b = t1 + t2

4

a + b + Z (LEA命令)

5

... >> 29

ARMでは状況はさらに良くなります。
多くのARMアセンブリ命令では、同じ命令サイクルで融合された右シフトを実行できます。これにより、bの計算がわずか2サイクルで完了します。そのため、プロセッサはbを乗算の影に隠すためにスーパースカラー機能を持つ必要はありません。

これはRaspberry Pi Zeroで観察されており、bが含まれている場合と含まれていない場合で同じレイテンシを示します。

最後に、アルゴリズムは右シフトで終わるため、後続のコードが返された値の加算または減算を行う場合(月の日付のN番目の曜日を計算する場合など)、最後のシフトもその後続の操作と融合されます。

ARM最適アセンブリステップ

ステップ

並列ステップなし(乗算のオーバーラップを除く)

1

a = rd * M + Z(MADD命令)

2

t1 = (rd >> 1)

mul-latency

3

b = t1 + (rd >> 4) (融合シフト加算)

mul-latency

4

a + b

5

... >> 29 (次の操作と融合される可能性あり)

中間範囲バリアント

rd >> 4項をドロップし、rd >> 1のみを残した場合、関数はわずかに高いスループットを持ち、範囲は約±146万年になります。この性質の調整済みバリアントは、Function Explorerで見つけることができます。#fn=32unix_mediumを参照してください。

高速フルレンジ (バリアント2: 2回の乗算) ディープリンク

さらに高速な結果を得る方法があります。乗算は遅いですが、乗算が互いに依存しない場合は高いスループットを持つことを思い出してください。項 (rd >> 1) + (rd >> 4) を手作業で実装した除算に置き換えることで、新しい高速フルレンジバリアントが得られます。今回はレイテンシではなくスループットに最適化されています。

以下の関数は丸め込み乗数に切り替わるため、4 / 7を加算する代わりに、3 / 7を減算することを目指します。

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

フルレンジ32ビット版 (バリアント2)
入力範囲: フル32ビット: -2^31 から 2^31-1
有効な日付: -5,877,641-06-23 (火: 2) から 5,881,580-07-11 (金: 5)

  1. const u32 M = (1 << 32) / 7 + 1  
    
  2. const i32 N = i32(M * 4)
    
  3. const u32 a = u32(rd) * M + N    
    
  4. const u32 b = u64(rd) * N >> 32
    
  5. weekday = (a + b) >> 29
    

C++バージョンについては、Function Explorerの#fn=32unix_v2を参照してください。
注: i32(M * 4)はオーバーフローして負の乗数になり、3 / 7 * *rd*の減算につながります。

左側の関数が目的の出力をどのように生成するかを視覚化したもの。定数「Z」は回転角度として機能します。

単純なインオーダープロセッサであるRaspberry Pi Zeroの32ビットARMチップでさえ、これらの乗算をオーバーラップさせることができます。以下の表のステップで確認できます。表には2つの列がありますが、1つの行に2つの計算がある行はありません。

x86最適アセンブリステップ

ステップ

計算1

計算2

1

rd * N

2

a = rd * M

mul-latency

3

mul-latency

mul-latency

4

mul-latency

b = ... >> 32

5

a + b + u32(N) ("LEA")

6

... >> 29

ARM最適アセンブリステップ

ステップ

計算1

計算2

1

rd * N

2

a = rd * M + u32(N) ("MADD")

mul-latency

3

mul-latency

mul-latency

4

mul-latency

5

a + (b >> 32) (融合シフト加算)

6

... >> 29

レイテンシ対スループット

上記の表は6行ですが、前のセクションのアルゴリズム(バリアント1)は5行です。
しかし逆に、全体としての操作数は少なくなっています(X86: 6 → 5; ARM: 5 → 4)。
これはレイテンシを犠牲にしてスループットが向上することを示唆していますが、ターゲットプラットフォームとコンパイラの性能に大きく依存します。

コンパイラパフォーマンス
  • x86の場合: 残念ながら、GCCのみが高スループットの3成分LEA命令を活用します。
  • ARMの場合: Clangのみが最適な4命令シーケンス(定数ロードを除く)を生成します。そして、asm("" : "+r"(a));を挿入して強制した場合のみです。

最適でないコンパイラアセンブリにもかかわらず、これらのバリアントはすべて依然として非常に高速であり、おそらく可能なよりも1〜2サイクル遅いだけです。

バリアント2 - フルレンジ (GCC x86 アセンブリ)

  1. movsxd  rax, edi
    
  2. imul    edi, edi, 613566757
    
  3. imul    rax, rax, -1840700268
    
  4. sar     rax, 32
    
  5. lea     eax, [rdi-1840700268+rax]
    
  6. shr     eax, 29
    
  7. ret
    

x86をGodboltで表示 [画像]

バリアント2 - フルレンジ (強制Clang ARM アセンブリ)

  1. mov     w8, #18725           
    
  2. mov     w9, #9364
    
  3. movk    w8, #9362, lsl #16   
    
  4. movk    w9, #37449, lsl #16
    
  5. madd    w8, w0, w8, w9
    
  6. smull   x9, w0, w9
    
  7. add     x8, x8, x9, lsr #32
    
  8. lsr     w0, w8, #29
    
  9. ret
    

ARMをGodboltで表示 [画像]


高速フルレンジ (バリアント3: 上位ビット+下位ビット) ディープリンク

最後に、この記事の冒頭で示された例、3つのx86アセンブリ操作でのフルレンジに到達します。

Unix 曜日 [0‥6] ISO 曜日 [1‥7]

与えられたもの: input (rd = サイン付き32ビットUnix日単位カウント); 計算するもの: weekday [0‥6]:

  1. mov   eax, 613566756                u32 M = (1 << 32) / 7
    
  2. imul  ecx                          rd * M  
    
  3. lea   eax, [eax-1828716544+edx*4] u32  r = a + 4 * b + (Z = 0x93000000)
    
  4. shr   eax, 29                     weekday = r >> 29
    

これはC++実装がFunction Explorerの#fn=32unix_v3として利用可能です。

なぜ修正項を加算しているのかを思い出してください。乗数が2^32 / 7 = 613566756**.5714...**の小数部分を表現できないためです。

左側の関数が目的の出力をどのように生成するかを視覚化したもの。3行目の定数は回転角度として機能します。

これを次のように処理しました。

  1. 丸め込み解除乗数と修正を使用: (rd >> 1) + (rd >> 4) = 1/2 + 1/16 = **0.5625** ≈ 4/7
  2. 丸め込み乗数を使用し、乗数修正によって実質的に3/7rdを減算する。

別の方法として、丸め込み解除乗数に戻りますが、rd * (4. / 7.)の近似をパッチワークでつなぎ合わせる代わりに、N / 7の既存の近似を見つけてから4を掛けます。

そのような「既存の近似」をN / 7で見つけることができる場所はどこでしょうか?
それはずっと前からそこにありました。それは、私たちが常に計算しているものの上位32ビットの結果です: rd * M:

  • u32(*rd*) * *M*を計算する代わりに...
  • w = u64(*rd*) * *M* [操作#1] を計算します。
    • 低位の結果は*a* = u32(*w*)です。(32ビットx86では「eax」レジスタにアクセスすることで「無料」で抽出されます)
    • 上位の結果は*b* = *w* >> 32です。(32ビットx86では「edx」レジスタにアクセスすることで「無料」で抽出されます)
    • 次に: *r* = *a* + 4 * *b* + *Z* *— 単一のLEA操作
      [操作#2]
    • そして最後に: **weekday** = *r* >> 29 [操作#3]

*「LEA」操作は、a + 4 * b + Zの項に適合します。この演算子を初めて見た場合は、スーパーパワーのように見えるかもしれません。扱える範囲は非常に限定的です。2つのレジスタを取得し、そのうちの1つを(1、2、4、または8)で乗算し、別の定数と合計することができます。元々はメモリアクセスパターンを支援するために設計されましたが、低レベルのアルゴリズムで使用および悪用できます。

残念ながら、以前と同様に、テストしたコンパイラは最適アセンブリを生成しません(x86をGodboltで表示 [画像])。
そのため、導入部ではソースコードではなく、生のバイナリで提示しました。

Function Explorer ディープリンク

この記事全体で多くのコード例を見てきましたが、この下のウィジェットはそれらをすべて単一の「Function Explorer」にまとめています。ここでビット幅、エポック、範囲、バリアントを設定できます。合計280個の手動調整された順列があり、すべて完全にテストされています。


入力: サイン付き非符号 64ビット32ビット16ビット8ビット
範囲: フル (11.8M年) 中間 (2.9M年) 狭い (489K年)
バリアント: V1 (2シフト) V2 (乗算) V3 (上位ビット) 64ビット拡張
出力: [0‥6] [1‥7] エポック:

  1. inline uint8_t get_weekday_32unix(int32_t rd) {
    
  2.     const uint32_t M = (1ull << 32) / 7;  
    
  3.     const uint32_t Z = 0x95000000;
    
  4.     const uint32_t a = uint32_t(rd) * M + Z;
    
  5.     const uint32_t b = (rd >> 1) + (rd >> 4);
    
  6.     return uint32_t(a + b) >> 29; 
    
  7. }
    

上のチャートは、入力が円周上の理想化された角度から、8つのセグメント(最終計算の上位3ビットを表す)にどのようにマッピングされるかを視覚化します。
フォームの変更時にアニメーションします。

テスト

上記の関数の280個すべての順列をテスト目的で単一のファイルに生成できます。これはテストリポジトリにコピー&ペーストされます: https://github.com/benjoffe/fast-world-calendars [画像] (リポジトリにはすでにコピーがあります)。
ビット幅8、16、32の関数は、指定された範囲で網羅的にテストされます。
64ビット範囲の関数は網羅的にテストするには遅すぎるため、代わりに4つの10億日付チャンク(ゼロ付近、最大値まで、最小値まで、ランダム選択)でテストされます。


一般化 ディープリンク

この記事で紹介された手法は、他のメルセンヌ数(つまり、2^N - 1の形式)の剰余演算に一般化できます。例えば、D = 3, 15, 31...などですが、ただしD < 2^(BitWidth/2-1)である場合に限ります。これは32ビット空間ではD < 32,768を意味します。これはほとんどの実用的なユースケースには十分ですが、他のメルセンヌ数の場合は、別のオプションがあります。

以下の関数は、私が一般曜日問題に対する最初に見つけたソリューションです(Neriの技術を直接基盤としています)。

フルレンジ32ビット法 (最初の試み)

  1. u32 n = u32(rd) + (rd >= 0 ? 4 : (9 << 28))
    
  2. u32 q = (u64) n * 2454267027 >> 34           
    
  3. weekday = (n + q) & 7
    

ここには2つのトリックがあります。

トリック#1

  1. u32 n = u32(rd) + (rd >= 0 ? 4 : (9 << 28))  
    
  2. u32 q = (u64) n * 2454267027 >> 34
    

これはNeriの開始部分に似ていますが、0を加算する代わりに、大きな数9 × 2^28または0x90000000を加算しています。また、修正なしの7による除算を実装するために、丸め込みマジック乗数を使用しています。

この大きな加算を使用できるのは、次の理由によります。

  1. この数は4 (mod 7)に等しい(以前の0の値は2^32 = 4 (mod 7)と見なすことができます)。
  2. これは、[-2^31..-1]の範囲の負の数を、符号なし32ビット空間の連続したブロック[2^28.. 9×2^28-1]にマッピングします。つまり、ラップアラウンドポイントを気にする必要がありません。

なぜこれを行うのか?標準的な7による除算の丸め込みマジックは、32ビット入力範囲の80%を超える範囲でのみ正確です。これが、Neriのアルゴリズムのクリーンなバージョンが、7による除算の初期推定商を修正するために追加のアセンブリを出力する理由であり、以前にlibdivideスタイルのテクニックが最適化の可能性として提案された理由です。

この新しい手法により、rdは本来よりも小さい範囲にマッピングされ、nの全体の値は[4..9×2^28-1]の範囲内になります。この範囲は32ビット入力範囲の80%よりも小さいため、除算のために標準の丸め込みマジック番号を使用できます。コンパイラは、縮小された入力範囲を認識するほど賢くないため、カスタム乗算シフトによる除算を手作業で実装する必要があります。

では、なぜ9 × 2^28なのでしょうか?

この加算には他の多くの選択肢を選ぶことができます。最小のオプションは2^31 + 2 = 0x80000002でしょう。
その定数を使用すると、x86では同じくらい高速ですが、ARMプロセッサではこの定数をロードするために2つのアセンブリ操作が必要になります。
9 × 2^28は、下位16ビットがゼロであるため、ARMでは1つのアセンブリ操作でロードできる便利な数値です。

次に進みましょう。

トリック#2

  1. weekday = (n + q) & 7  
    

これは、乗算をビットマスクに置き換えることで、従来のn - n / 7 * 7ではなく、(n + n / 7) % 8を計算しています。

このトリックを「Nundinal Map」(記事1で紹介された「Julian Map」に似ています)と呼びます。
Nundinalは、古代ローマの8日週を指します。
基本的に、7日週が経過するたびに、nに1日分の仮想的な日をパディングします。n / 7が7を8に、14を16などに繰り上げることは、それほど難しくありません。
数値がこの偽の8日週にマッピングされたら、下位3ビットを調べるだけで実際の曜日を抽出できます。

これがx86で高速になる理由は明らかです。代替手段は通常、n + q - (q << 3)としてコンパイルされ、3サイクルではなく2サイクルかかります。ARMでこれも高速になる理由は、ARMにはMADDと呼ばれる融合乗算加算操作があり、n + q * -7を3サイクルのレイテンシで1つのアセンブリ命令で実行できますが、スループットはわずか1サイクルです。これも高速である理由は、ARMでは、この行が前のコードの行と部分的に融合し、n + (w >> 34)(ここでwは前の乗算結果)を単一のアセンブリ命令で実行できるためです。したがって、この最終行はARMでは真の単一サイクル操作です。ビットマスクだけです。

この特定の変換は以前には見たことがありません。

この数学的根拠は次のとおりです。

これは、次のような一般的な公式の特殊なケースです。

ここで、およびです。

この一般的な公式の証明は、付録B. - 2のべき乗パディングによる剰余の証明に記載されています。

この手法はメルセンヌ数に限定されません...

2N - 2K の形式の除数の高速剰余演算

上記の一般的な公式は、形式の数値に使用できます。

この形式の興味深いユースケースには、次のようなものがあります。

  • 時間の計算: x % 24 = (x + ((x / 24) << 3)) & 31
  • 分/秒の計算: x % 60 = (x + ((x / 60) << 2)) & 63

私の調査によると、これらの公式は新しいようです。これらは、特にx86プロセッサでLEAアセンブリ命令のおかげで高速です。これは、値を2、4、または8倍し、別の変数を加算することを単一サイクルで実行できます。

興味深いことに、x - x / 7 * 7という標準的なアプローチでさえ、技術的にはこの一般的な公式の特殊なケースです。2^32の2の補数では、-7 = 2^32 - 7です。


締めくくり ディープリンク

なぜこんなことをしたのか?
まあ、もうお分かりかもしれませんが、私はこれらのことが非常に面白いのです。7日週は私たちのカレンダーの中で最も古い部分であり、グレゴリオ暦さえも超える、最も真にグローバルなリーチを持つ部分です。文明の崩壊に直面したり、新しい惑星に移住したりした場合、カレンダーは変更されるかもしれませんが、7日週は変更されないかもしれません。

これらすべてにつながったウサギの穴は、コプト暦、特にヘブライ暦のような文化的なカレンダーの最適化を探求することでした。ヘブライ暦は、一般的な日付の計算で7日週を複数回使用します。将来の記事でこれらをカバーします。

このシリーズの次の記事は、上記の「高速剰余演算」技術を使用した高速時刻についてです。

この記事が興味深いと思われた方は、Xでフォロー [画像]して、日付とアルゴリズム関連の記事をさらに公開したときに通知を受け取ってください。

改訂履歴:

  • 2026年6月27日 - ソフトリリースドラフト
  • 2026年8月17日 - 初版リリース
  • 2026年8月20日 - 「不合理に高速」- 事前作業セクションにNeriの先行作業を追記。

オープンソース実装 ディープリンク

この記事で提示されたアイデアは、以下のオープンソースプロジェクトで採用されています。

付録A - ベンチマーク結果

この記事で主張されている範囲の網羅的なテストは、テストケースコードで確認できます: https://github.com/benjoffe/fast-world-calendars [画像] 。

同じリポジトリがベンチマークにも使用されており、大量のランダムな日付がメモリにロードされテストされます。レイテンシモードでは、並列実行を保証するために、結果を次の計算にビット単位XORでフィードします。

git clone git@github.com:benjoffe/fast-world-calendars.git
cd fast-world-calendars
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
./build/bin/weekday_bench
./build/bin/weekday_bench -latency
./build/bin/weekday_bench -batch

上記のコマンドは-repeat=5フラグと共に使用され、Raspberry Piのみ-count=256(他は65536個のランダムな日付)です。中央値の結果を表に保存しました。

表の括弧内の数値は、バッチ全体を処理するのにかかったナノ秒を表します。このシリーズのすべてのベンチマークと同様に、相対速度比は「ベースライン」を差し引いて計算されます。これにより、ループのオーバーヘッドが除去されます。数値が小さいほど高速です。

注: これらのベンチマークはスカラーパフォーマンスを測定します。Narrow、Medium、V1バリアントはプレーンな32ビット数学(下位ビットのみ)に準拠しており、きれいにベクトル化されるため、多くのプラットフォームでは、タイトなループで多数の日付を処理する場合(自動ベクトル化される)、ここで示されているよりもさらに差が開く可能性があります。V2およびV3の追加の32ビット上位半分数学は、一部のSIMDチップでオーバーヘッドを追加する可能性があります。

スループット レイテンシ

アルゴリズム:ベースラインナイーブRustHinnantNeri*狭い新しい中間*フル 64ビット拡張新しいフル (V1)新しいフル (V2)新しいフル (V3)(V3) 強制アセンブリ"最初の試み"
MacBook Pro 2024 (MacOS 15.6.1) Apple M4 Pro コンパイラ: Apple clang 17.0.0- (14640)2.78倍 (59014)1.32倍 (35634)2.84倍 (59889)1.00倍 (30587)0.17倍 (17388)0.23倍 (18387)0.18倍 (17465)0.39倍 (20788)0.35倍 (20266)0.25倍 (18624)0.36倍 (20331)0.48倍 (22304)
AMD Ryzen 9 9950X3D Ubuntu 24.04.3 LTS コンパイラ: GCC 14.2.0 (x86_64)- (5746)1.84倍 (72955)-2.92倍 (112071)1.00倍 (42185)0.27倍 (15478)0.42倍 (21012)0.33倍 (17870)0.55倍 (25608)0.59倍 (27395)0.50倍 (24010)0.48倍 (23191)-
AMD Ryzen 9 9950X3D Ubuntu 24.04.3 LTS コンパイラ: Clang 18.1.3 (x86_64)- (11556)2.30倍 (90156)1.72倍 (70542)3.90倍 (144980)1.00倍 (45787)0.23倍 (19556)0.31倍 (22334)0.28倍 (21301)0.47倍 (27721)0.53倍 (29548)0.41倍 (25722)0.41倍 (25738)0.57倍 (30965)
MacBook Pro 2016 (MacOS 12.7.6) Intel Core i7 @ 2.7 GHz コンパイラ: Apple clang 14.0.0- (23209)1.84倍 (171955)1.46倍 (141247)3.71倍 (323632)1.00倍 (104158)0.39倍 (54856)0.30倍 (47357)0.39倍 (54907)0.49倍 (63104)0.44倍 (58613)0.85倍 (91688)0.28倍 (45984)0.56倍 (68224)
Raspberry Pi Zero 32-Bit ARM Raspbian GNU/Linux 13 (trixie) コンパイラ: GCC 14.2.0 (armv6l)- (6222)1.30倍 (59627)1.03倍 (48624)0.96倍 (45630)1.00倍 (47294)0.75倍 (37029)0.75倍 (37016)0.85倍 (41138)0.70倍 (34961)0.85倍 (41140)0.55倍 (28802)0.56倍 (29086)0.65倍 (32954)
  • "Narrow" および "Full 64-Widen" は Neri によって最初に実装されました - x86 ベンチマークは彼の方法を反映しているはずです。これらのベンチマークされたバリアントは、この記事のARM用に調整された定数を使用したバージョンであり、ARMではNeriのアプローチよりもわずかに高速になります。

付録B. 2のべき乗パディングによる剰余の証明 ディープリンク

任意の整数、正の除数、および非負の整数に対して、ここで床除算を表します。

証明。
商と剰余で表します: 、ここで、およびです。

両辺のを取ります。

はの倍数なので、剰余演算で消去され、は次の理由で消去されません。


値は自由パラメータです。有用な選択肢は、を2のべき乗にする正の値であり、それによってビット単位のANDになります。

ケースはWarrenのHacker's Delight(§10–20、Remainder by Multiplication and Shifting Right)に登場し、次のような例を示しています。

Warrenは、この記事全体で使用されているような、乗算と右シフトによる高速な固定小数点定数の近似を示しています。
直接的な形式はHacker's Delightでは分析されていません。