整数除算を浮動小数点演算に移行するのは容易である

2026年8月10日 整数除算 q=(x/y) と（ユークリッド除算の）剰余 r=(x%y) のハードウェア演算は、現在のハードウェアでは非常に残念な性能です。通常、レイテンシが非常に長く、スループットも低いです。対照的に、浮動小数点除算はかなり良好です。レイテンシが短く、スループットが高く、さらに演算を実行するための実行ユニットが多いこともよくあります。そのため、一部の整数除算/剰余演算を浮動小数点演算に移行することが興味深い場合があります。しかし、それは面倒な作業ですよね？実際には簡単だと思います。 数学は非常に単純なので、もし間違いがあればすぐにわかるはずです。私の主張は次のとおりです。53/24ビット（それぞれdouble/single精度）に収まる2つの整数xとy（符号付きまたは符号なし）について、両方を浮動小数点数に変換すると、以下のようになります。 // 浮動小数点数: // d は整数除算 x / y と同じ整数になります // m は整数剰余 x % y と同じ整数になります // （標準的な丸めモード：最近接丸め、偶数への丸め） d = trunc(x/y); // 符号なし整数の場合、floorでも同じです m = -fma(d,y,-x); // fmaが必要 // 注意：もし 'd' のみが必要で、それが整数に変換される場合、 // 浮動小数点から整数への変換では、切り捨てまたは床関数は // 無料で実行されます。 ここからは、符号付き整数は最大値の範囲が狭いため、より難しいケースである符号なし整数のみを考慮します。ただし、浮動小数点数は符号付きの絶対値として実質的に格納されることを覚えておいてください。 いくつかの実用的な点：これは、丸めモードをゼロ方向への丸めに設定し、完了後に元に戻すことで機能しますが、制御ワードにアクセスすることはしばしば非常に高コストです。一部のハードウェアには、除算などの一部の操作で丸めモードを選択できる除算オペコードがあります。例として、AVX-512には組み込み関数 _mm_div_round_sd があり、例としてリストされているレイテンシは14サイクルです。 整数から浮動小数点数への変換、およびその逆にはコストがかかります。（注意：x64 CPUの大多数は、符号なし整数から浮動小数点数への変換、およびその逆のオペコードを持っていません。したがって、これは実装上の懸念事項です。） 明らかに、浮動小数点数の精度 $p$ は、整数の幅の上限を決定します。これが $p$ で機能する場合、それより小さいすべての幅でも自明に機能します。例としては、double精度（$p=53$）での32ビット整数、single精度（$p=24$）での16ビット整数があります。 この場合、整数から浮動小数点数への変換を回避する「トリック」が存在する可能性があります。最も有望なケースは、オーバーヘッドを償却するためにSIMDで作業する場合です。定数除数については、コンパイラが最適化してくれるはずです。実行時にわかっていて数回再利用される除数については、libdivideのようなソフトウェアソリューションがあります。 証明済みの方法（参照：Formally verified 32- and 64-bit integer division using double-precision floating-point arithmetic）が存在することに注意してください。 標準の丸めモードは、最近接丸め（偶数への丸め）であり、最初の重要な観察事項は「偶数への丸め」の部分です。タイ（tie）は、操作の正確な結果が2つの浮動小数点数のちょうど中間にある場合に発生します。浮動小数点除算（この場合の基数2および同じ作業精度）では、中間値は存在しません（参照：Midpoints and exact points of some algebraic functions in floating-point arithmetic section 6.1, corollary 1）。したがって、タイが発生することは決してなく、最近接丸め部分のみが適用されます。 4ビット精度の浮動小数点フォーマットを使用して、正確な結果が1未満だが、丸めアップに最も近いすべての可能な構成を例として見てみましょう。 | GRS x = don't care .1111|0xx .1111 (丸めなし) .1111|100 タイケースは不可能 .1111|101 1.000 (丸めアップ) .1111|11x 1.000 (丸めアップ) 丸め処理の前に、ハードウェアはガードビット（G）、ラウンドビット（R）、スティッキービット（S）の3つの追加ビットを計算しますが、タイケースは不可能なので、Gのみを知る必要があります。したがって、正確な結果が小数部 $r$ ビットを持つフォーマットでは、次の整数への丸めが発生するには、小数部が少なくとも $r+1$ 個の連続した1を持つ必要があります。 これは合法的な入力では不可能であると主張します。小数部のみを考慮すればよいので、$x/y$ の正確な結果を整数部 $n$ と小数部に分解してみましょう。 \[\frac{x}{y} = n + \frac{a}{b}\] （ここで、$b=y$ とするのは見栄えを良くするためです）明らかに次のようになります。 \[\frac{a}{b} \in \left[0,1\right)\] $p$ 精度のバイナリ浮動小数点フォーマットでは、除算は $d$ ビットの整数を生成し、残りの $r$ ビットを剰余のために残します。 \[\begin{align*} d & = \left \lfloor \log_2 \left(n \right)+1 \right \rfloor \\ r & = p-d \\ \end{align*}\] $r$ ビットの小数部について、その値の範囲の下限と上限を $b$ について定義できます。 \[\begin{align*} \func{b_l}{r} & = 2^r \\ \func{b_u}{r} & = 2^{r+1}-1 \\ \end{align*}\] この時点で、$p$、$n$ およびそれから導出される $d$ についてはほぼ完了です。私たちは、$r$ ビットで可能な最大小数部を知りたいのです。下限値で1に最も近い値は次のようになります。 \[\begin{align*} \frac{2^r-1}{2^r} = \sum_{i=1}^r \frac{1}{2^i} \end{align*}\] この合計は、そのバイナリ展開で $r$ 個の連続した1を生成する最小の数であることを示しています。次に、上限値で1に最も近い値で繰り返し、連続した1が $r+1$ 個ある最小の数（$r+1$ の下限）と比較します。 \[\begin{align*} \frac{2^{r+1}-2}{2^{r+1}-1} &< \frac{2^{r+1}-1}{2^{r+1}-0} \end{align*}\] ここで、マイナスゼロは式を整列させ、パターンを強調するためです。いずれにせよ、この不等式は、上限値が $r$ 個の連続した1を持つことに限定されることを意味します。 実際、下限と上限のバイナリ展開について具体的に述べることができます。下限は $r$ 個の1で、終端します。上限の正確な値は、周期が $r+1$ で、 $r$ 個の1の後に1個のゼロが続く、純粋に循環的です。最初の4つについての表を以下に示します。 $r$ | 下限のバイナリ展開 | 上限のバイナリ展開 --|-------------------|------------------- 1 | $\frac{1}{2}$ .1 | $\frac{2}{3}$ .(10) 2 | $\frac{3}{4}$ .11 | $\frac{6}{7}$ .(110) 3 | $\frac{7}{8}$ .111 | $\frac{14}{15}$ .(1110) 4 | $\frac{15}{16}$ .1111 | $\frac{30}{31}$ .(11110) しかし、いずれにしても重要な部分です。合法的な入力の場合、$x/y$ は、次の整数への丸めを引き起こすほど大きな小数部を生成することはできません。したがって、浮動小数点結果の整数部分は、整数結果と同一になります。 いくつかの除数について、部分をまとめてみましょう。除数： 1：正しいです。 2：指数のみを変更し、いかなる丸めも発生しません。 3：$r=1$ で、最大の $x \% 3$ は $2$ なので、最大小数部は $\frac{2}{3}$ です。次の整数への丸めはできません。 $\{4,5,6,7\}$ は $r=2$ を持ちます。正確な除数は関係ありません。なぜなら、すべて .110x で始まるからです。 そして、すべての可能な除数について同様です。 worst case $a$,$b$ ペアをテストするコード：godbolt for both binary32 and binary64。 Comments math (36) integer (8)