natsugiri https://blog.hatena.ne.jp/natsugiri/ でも今日はSRMあるから https://natsugiri.hatenablog.com/ % を剰余演算子とする。 を2以上の2^31未満の整数とする。 をたくさん求めたいときに、 について前処理をしておけば除算・剰余算を使わずに計算できる場合がある。 とくに、 が定数であるがコンパイル時に決定できない場合に高速化することができる（コンパイル時に決定しているならばそもそも今回の手法と同程度に高速）。 2つの方法 Barrett Reduction と Montgomery Reduction を実装した。 まとめ コード https://ideone.com/sNBQTz 実装は4種: ナイーブな剰余演算子、Montgomery乗算、Barrett Reduction、Barret… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnatsugiri.hatenablog.com%2Fentry%2F2020%2F04%2F06%2F030559" title="高速なMOD演算 Barrett Reduction, Montgomery 乗算 - でも今日はSRMあるから" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-04-06 03:05:59 rich https://natsugiri.hatenablog.com/entry/2020/04/06/030559 1.0 100%