---
tags: 競プロ
---
# $\bmod p$ で掛け算をするときの高速化の余地について

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">これめちゃくちゃ高速化の余地だよな <a href="https://t.co/AOpexViDUj">pic.twitter.com/AOpexViDUj</a></p>&mdash; tatyam (@tatyam_prime) <a href="https://twitter.com/tatyam_prime/status/1495613144755933185?ref_src=twsrc%5Etfw">February 21, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

$\bmod p$ で掛け算をするとき、以下のようなコードが現れます。

uint32_t mod_mul(uint32_t a, uint32_t b, uint32_t p){
    return static_cast<uint64_t>(a) * b % p;
}

$p$ が 32 bit であるとき、$a \times b \bmod p$ を計算するコードです。$a, b$ が 32 bit なので、$a \times b$ を 64 bit で計算する必要があります。

これをコンパイルした結果のアセンブリを見てみましょう。

[Compiler Explorer](https://godbolt.org/) を使用します :bow:


`movl` は 32 bit の代入、`xorl` は 32 bit の XOR 、`imulq` は 64 bit の符号付き乗算、`divq` は 64 bit の符号なし除算を表します。
64 bit で $a \times b$ を計算するのでまあこうなりますよね。

命令は https://www.felixcloutier.com/x86/ のようなところを見るといいです。

さて、ここで `divq` 命令を詳しく見てみましょう。

https://www.felixcloutier.com/x86/div

> Unsigned divide RDX:RAX by r/m64, with result stored in RAX ← Quotient, RDX ← Remainder.

`RDX` と `RAX` を繋げた 128 bit を引数 64 bit で割って、商を `RAX` に、余りを `RDX` に入れると書いてあります。
64 bit 除算は 128 bit / 64 bit をしているんですね〜

ということは 32 bit 除算で十分なのでは？
64 bit 除算と 32 bit 除算では速度が格段に違うので、できれば 32 bit 除算を使いたいところです。

## 実装

`divl`

> Unsigned divide EDX:EAX by r/m32, with result stored in EAX ← Quotient, EDX ← Remainder.

に対して `mull`

> Unsigned multiply (EDX:EAX ← EAX ∗ r/m32)

がちょうど `EDX:EAX` を共有しているので、これをまとめて最適化しましょう。
コンパイラは最適化をしてくれないようなので、インラインアセンブリで頑張ります。
(コンパイラが最適化しないのにはちゃんと理由があって、$a = 2^{16}, b = 2^{16}, p = 1$ とか入れると $a \times b / p$ の商が 32 bit に収まらなくなって RE を起こします。$a, b < p$ が保証されている場合は、32 bit 除算に最適化することができます。)

https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html


`"a"` は `EAX` を使うことを、`"d"` は `EDX` を使うことを、`"r"` はコンパイラに選んでもらうことを表します。

これで、32 bit 除算を使うことができました。

u32 mod_mul(u32 a, u32 b, u32 p){
    asm("mull\t%3" : "=a"(a), "=d"(b) : "a"(a), "r"(b));
    asm("divl\t%4" : "=a"(a), "=d"(b) : "a"(a), "d"(b), "r"(p));
    return b;
}

## 実測

https://wandbox.org/permlink/kPy0KLjU6EZvHNPQ

1.2 倍くらい速い　思ったより速くならなかった　たぶん `divq` が賢いことをやってる

64 bit もやってみる

$p$ が小さい : https://wandbox.org/permlink/EmkZpkRb3wzXlyCm
$p$ が大きい : https://wandbox.org/permlink/9kvKEATjx60Ew1MW

1.1 – 1.2 倍くらい速い　$p$ によって速度が劇的に変わる　これは何か賢いことをやっていますね…

## おわり

この高速化は https://ei1333.github.io/luzhiled/snippets/string/rolling-hash.html で初めて見ました

基本ジャッジは x86-64 だから動くんだけど、ARM のジャッジってあるのかな