余剰計算

Question

a * b

がオーバーフローするとき

(a * b) % c

を求めるプログラムを教えてください。

Comments

[swordone]

細かいですが、「余剰」ではなく「剰余」では

Answer 1

a = x + nc
b = y + mc
ここでx,yは0以上c未満の整数、n,mは整数とする。

ab = (x + nc) * (y + mc)
= xy + (xm + ny +nmc) * c

つまり、aの剰余、bの剰余を個別に先に計算してからかけても結果は変わらないといえます。

Answer 2

剰余演算にはいろいろな性質があります。

• ウィキペディア 剰余演算 https://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E6%BC%94%E7%AE%97

...
分配則
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a * b) mod n = (a mod n) * (b mod n)
...

Comments

[HogeAnimalLover]

(a * b) mod n = (a mod n) * (b mod n)
厳密にいうと、右辺はnを上回る可能性があるのでもう一回剰余計算が必要です。

[katoy]

あ！、そうです。
wikipedia の記事を引用するときに、copy & paste で手書きして, 間違えました。

[HogeAnimalLover]

あ、そうでしたか。自分の書き込み（2016/09/23 05:24　投稿）においてもこの説明を省略したので、数式化した際に漏れたのかとも思いました。