素数マスターへの道(7)

お嬢さん、お名前は？

除算って遅いんです。

多少なりともプログラミングをやったことのある人にとっては「何を今さら」という内容ですが、あまりプログラミングを知らない方も読んでくださっているようなのでご容赦を。
で、どのくらい遅いのかということを一言で説明するのは少し難しいですが、今回取り組んでいるPrime Checkerのプログラムが実行されるSPOJサーバでは、32bit整数の除算時間は体感的に乗算の10倍以上です。フェルマーテストやミラー・ラビンテストも、除算の回数を大幅に減らすことで高速化をしているわけです。
すでに除算回数を減らす工夫をしているのですから、これ以上は出来なさそうに見えますが、もう少し改良の余地があります。

計算機上では、2^nで表すことのできる数に限り非常に高速な乗除算を行うことができます。たとえば、13は2進数で

1101

のように表すことができます。これを2倍した26は、

11010

となります。さらに2倍した52は、

110100

のように、右端に0を付け加えていくだけです。2で割りたければ、右端の数を1つずつ取り去っていけば良いということになります。普段私たちが使う電卓にはありませんが、プログラミングを行う場合にはビットシフトという演算を利用することができて、これを活用することで大幅に高速化できる場合があります。

剰余についても、2^nの場合に限って簡単に行うことができます。2^nを2進数で表すと、nビット目だけ1であとは0で表されます。この数から1を引いたものは、1〜(n-1)ビット目までがすべて1で、残りは0になっています。

例えば、2^4(=16)は

1000

2^4-1(=15)は

0111

のようになります。
2^nでの剰余は、2^n-1との論理積で求めることができます。

21を2^4(=16)で割った時の余りは

00111(=2^4-1=15)
10101(=21)

の論理積

00101(=5)

のようになります。要するに、下位の(n-1)ビットを切りだす作業をしているだけですね。簡単なビット演算で求めることができるので、これがもっと活用できれば、さらに高速化できそうですね。