きままにものづくり

日々の気付いたことなんかを書いてます。

MOD乗算

MODをとる場合でも大きい数字の掛け算はオーバーフローしてしまうので、工夫をしなければならない。
片方の数字を2^nの足し算で表す。
 a \times b = a \times (b_02^0 + b_12^1 + b_22^2+...+b_N2^N)
ここで、b_nは2進数表記でのnビット目を示す。ただし、0ビットから始まるとする。
aを括弧内に入れる。
 \sum_{n=0}^N ab_n2^n
b_nは1か0しか値を取らないので、ビットが立っている部分の和が答えになる。
3\times5を例にとる。
3\times5 \\<br />
= 3 \times (1\times2^0 + 0\times2^1 + 1\times2^2)\\<br />
= 3 + 12 \\<br />
= 15<br />

広告を非表示にする