乗算でのオーバーフロー回避

OUPCのFour Arithmetic Operationsの解説にも書いていたけど、忘れないようにまとめておく。
A*B を mod M (M>2^31)の世界で計算したくなったとする。当然、A,Bともに大きな値となり、そのままA*B%Mを計算したらA*Bの部分でオーバーフローが起こりうる。
じゃあどうやってそれを回避すれば良いかというと、まず掛け算を足し算で実装しなおすという手段が考えられる。このときはもちろんバイナリ法(蟻本の言葉でいえば繰り返し二乗法)を用いて毎回modをとる。
基本的にはこれで十分なことが多いのだけど、Mがあまり大きくないときには次のように計算することもできる。たとえばX*123456789012を計算するとき、
X*123456789012%M = (X*123456*10^6 + X*789012)%M = (X*123456%M*10^6 + X*789012)%M
とする。このとき、Mが10^12程度であればすべての計算は10^18以下におさまっていてオーバーフローせずに計算できる。バイナリ法に比べるとlog Mがなくなっているので10倍以上早く計算できることになる。また、Mが10^12程度というのは実際問題としてよく出てくる(素数関連で想定解法がO(sqrt(N))な問題でよく出てくる)。
上の方法で計算する時の注意点として、負の数を扱うときには少し気をつけた方が良い。それと、10のべきで分解するより2のべきで分解した方が割り算や剰余をとらずにシフト演算やAND演算で置き換えることができるので少し早くなる。