素数判定のプログラムを書いていると、
大きい数同士の割り算の余りを求めるところが難しい。
余りを求めるのも商を求めるのも本質的には変わらないので、
割り算が難しいと言っていいだろう。
前にそういうプログラムを書いたときも、
とても難しいと思って、
すごく効率の悪いプログラムを書いた覚えがある。
もうちょっと冷静に考えてみよう。
その処理系は、二桁しか持てない型しかないとする。
要するに変数は0〜99の整数しか値を持てない。
これで大きな割り算をする。
例えば、812 / 61の計算をして、余りを求める。
答えは暗算でも出て、19か。
各変数は1桁分持つことにする。
すなわち、
a2 : 8 a1 : 1 a0 : 2で812を、
b1 : 6 b0 : 1で61を表すこととする。
（ここでは、被除数は3桁まで、除数は2桁までと考える）
ここで、どう計算したらいいだろう。
まず、81を61で割って余りが20だから、
202を61で割ればよい。
だが、202はこの処理系ではまだオーバーフローしていて直接割れない。
そこで100を61で割った余りを求める。
これは99を割って、余りが38なので、1足して39となる。
余りが除数より1小さいときだけ例外で、このときは0となる。
200を割ったときは、とりあえず、39*2で78で、
これに残った2を足して、80。
これで100より小さくなったので直接割り算ができて、19。
こんな感じの流れだろうか。
しかし、これで本当にうまくいくのだろうか。
もうちょっと一般的に書いてみる。
変数は0〜e2-1を取れるとし、
a = a1e + a0
b = b1e + b0
とする。
まず、
a1 <- a1 % b
a2 <- a1 / e
a1 <- a1 % e
n0 <- e2 % b
n1 <- n1 / e
n0 <- n1 % e
として、
a1 <- a1 + a2n1
a0 <- a0 + a2n0
a2 <- a1 / e
a1 <- a1 % e
をa2が0になるまで繰り返す。
しかし、実際にはこれでうまくいくだろうか。
