HN 日本語サマリー

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

64ビット符号付き床除算を計算するための新しい高速アルゴリズム

A new faster algorithm to compute 64-bit signed floor division (benjoffe.com)

46 pointsby benjoffe4 コメント

要約

この記事では、コンパイル時に定数として知られている除数に対する、符号付き64ビット床除算を計算するための新しい高速アルゴリズムを紹介しています。既存の実装における課題と限界を詳述し、ARMおよびx86アーキテクチャでのパフォーマンス向上をベンチマークで示しています。また、過去の最適化手法や実用的なコード例も提供しています。

全文翻訳

コンパイル時定数による符号付き64ビット床除算の高速化手法

その他の最適化記事も参照:

Hacker's Delight の失われた章

2026年10月27日

符号付き整数床除算とは？
符号付き整数床除算とは、a/b を計算する際に、結果を −∞ の方向に丸めるのに対し、標準的な（「切り捨て」）符号付き除算は 0 の方向に丸めます。Hacker's Delight には、「床除算の方が望ましい結果を与えることが多いだろう」と書かれています。

この記事は、除数がコンパイル時にわかっている場合の、フルレンジ床除算についてです。

この関数の有用性にもかかわらず、整数床除算の世界は混乱しています：

  • 主要なコンパイラや多くの言語ではネイティブで提供されていません（例: C/C++/Go/Swift）。
  • それを実装している言語やソフトウェアライブラリは、最速のアルゴリズムをほとんど使用していないようです。
  • 少なくとも1つの非常に著名なソフトウェアライブラリには、4年以上もバグのあるオーバーフローする実装がありました！（後述）
  • 通常のオンライン検索やLLMへのプロンプトでは、遅いアルゴリズムしか見つかりません。
  • そして、Hacker's Delight（低レベルのコンピュータ数学のバイブルのようなもの）には、これに関する記述がほとんどありません！

このブログ記事は、高速アルゴリズムに光を当てるだけでなく、新しい高速アプローチを紹介することを目指しています。これは、理想的なコンパイルにおいて：

  • ARM では、ほとんどの64ビット除数に対して既存のアルゴリズムよりもスループットが10〜20%高速（時折同等）、レイテンシは同等かそれ以上です。
  • x86 では、
    • 約80%の正の64ビット除数（60%の負の除数）でスループットが約5〜10%高速です。
    • 残りのx86ケースでは遅くなりますが、レイテンシは（競争力はあるものの）通常は悪化します。

ベンチマーク セクションには、多くのプラットフォームでスループットとレイテンシの除数ごとの結果を示す詳細な概要があります。

これはすべてのビット幅で機能し、一部の32ビットまたはSIMDアプリケーションでも使用される可能性がありますが、最大のメリットは64ビットにあります。また、より高速な正の剰余演算や、「ユークリッド」除算（負の除数では床除算と異なります）にも使用できます。

床除算は、おそらくあなたが思っているよりもずっと高速になる可能性があります。
以下は、1日あたりの秒数である86400で除算した場合のスループットベンチマークのスナップショットです。これは、ほとんどの言語の組み込みメソッドを使用した場合のパフォーマンスと、この記事で概説されている高速な代替手段との比較です。

注：棒グラフでは、低い方が高速です。

ARM x86

床除算 86400 スループット - ARM64 チップMacBook Pro M4 Pro
および Snapdragon X1-26-100 でテスト済み

**共通
(Rust extit{、Zig など)

~2倍

**Robison extit{}(2005)

~1.1倍

**Granlund-
Montgomery extit{}(1994)

1倍

New Algo extit{}(2026)

~0.8倍

ARM x86

床除算 86400 スループット - X86 チップAMD Ryzen 9 9950X3D
および Intel Core i7 (MacBook Pro 2016) でテスト済み

**共通
(Rust extit{、Zig など)

~2倍

**Granlund-
Montgomery extit{}(1994)

1.05倍

**Robison extit{}(2005)

~1倍

New Algo extit{}(2026)

~0.95倍

extit{Rust は「div_euclid」を提供しており、これは正の除数に対して床除算と一致します。40以上の除数にわたる詳細な比較については、[ベンチマークセクション](https://www.benjoffe.com/fast-floordiv#benchmarks)を参照してください。}

このページにアクセスする方の中には、コードをコピー＆ペーストしたいだけの方もいらっしゃるでしょう。そのため、右側にあるこの関数ビルダーから始めます。

新しい高速除算関数:ビット幅: 64ビット32ビット16ビット8ビット
除数:

  1. inline int64_t fast_i64_floordiv_86400(int64_t x) {

  2.   const int64_t M = ((__int128(1) << 79) / 86400 + 1);

  3.   const int64_t m = M + (x >> 63);

  4.   return (__int128) x * m >> 79;

  5. }

誤解を避けるために、コメントとコードをそのままコピー＆ペーストした場合にのみライセンスが適用されます。同じロジックをコードに書き直す場合はライセンスは不要です。

テスト
64ビット用の-32768から32767までの65535個の除数セットを、単一の自己完結型C++ファイルに生成できます。これには、同じファイル内に境界テストも含まれています。
ビルドと実行方法については、ダウンロードの先頭にあるコメントを参照してください。

この形式を使用すると、任意のビット幅と任意の除数を選択して、すぐに使用できるコピー＆ペースト可能な関数を取得できます。

また、参照アルゴリズム ［画像］（追加のマイクロアーキテクチャパフォーマンス調整を備えた再利用可能なC++テンプレート）もあります。

ご覧のとおり、このテクニックは非常にシンプルなので、誰かが以前にこれを行ったことがあると予想されますが、私は探しましたがどこにも文書化されていませんでした。もし以前に行われたことが判明した場合でも、少なくともこのページで発見できるようになるでしょう。

残りの皆さんのために、床除算に関する物語をカバーします。これは私の発見のプロセスに沿ったものです...そして、高速ライブラリやコンパイラ/言語実装を作成したい場合は、これがワンストップショップになります。

歴史の教訓をスキップしたい場合は、新しい情報に直接ジャンプできます。

記事セクション:

切り捨て（標準）除算から始める ディープリンク

Unixタイムスタンプ（秒単位）をラタ・ディエ（日数カウント）に変換したいとしましょう。そして、これを正しく行う方法を忘れ、標準の「切り捨て」除算を使用したとします。

86400（60×60×24）で割る必要があります。64ビットタイムスタンプを使用します。32ビットタイムスタンプは約±68年しか保持できないためです。

右側のこの実装には、1970年より前のタイムスタンプが渡されるまで、非常に満足するでしょう。

C++ 標準除算（床除算ではない）入力: x — 符号付き64ビット整数

  1. const int64_t rd = x / 86400;

  2. return rd;

上記の関数は、ほとんどの負の値に対して不正な結果を返します。

もちろん、タイムスタンプ、角度の回転、タイルの位置など、繰り返しパターンを追跡するのに役立つ種類の除算である床除算を使用すべきです。これは、関連する`