素数の魅力
NHKの番組で素数が取り上げられて、ちょっとだけ周りでも盛り上がっていたので、素数の思い出？？？を書いてみようと思います。
素数に初めて触れるのは教科書的には中学なようですが、小学生高学年の時には知っていたような気がします。まあ小学生に中学生の数学の本をプレゼントしてくれる素敵なお知り合いの大学教授とかがいたので、どこで覚えたかは怪しいです。
通っていた中学も酷いカリキュラムで、確か中３の３学期も最後の方の自由課題で素数を探せというコンテストがあったような気がします。インターネットが無かったので、どこかで結果だけ探してきてコピペするわけにはいきません。何とか自力で計算する必要があります。さすがにマイコンなどはもうあったので、手計算という選択肢はありません。
最初のグループは、関数電卓やプログラミング可能な電卓で、ゴリゴリとコードを書いて計算するのですが、よほど工夫をしないと処理時間がかかりすぎて、ある程度の数までしか進みません。対象となる数の篩分けの後は、ほとんどMOD演算子の計算時間となるのですが、ここがいかんともし難い感じでした。
次のグループは、パソコンを駆使するパー研チームだったのですが、こちらもインタプリタであるBASICで処理すると遅すぎです。そこで当時、利用できた唯一のコンパイラであるPASCALで処理を書き、まあまあの速度で結果を得ることができました。ただこのPASCALはコンパイラと言ってもpCodeと呼ばれる仮想マシンの機械語に直すコンパイラなので、純粋な機械語で書かれたコードには太刀打ちできませんでした。
最後のグループが、マイコンで機械語を直接走らせる物理部チームで、ゴリゴリとアセンブラのコードを書いてハンドアセンブルしていたのですが、そもそも当時のCPUには割り算命令がありません。割り切れるかどうかは引いていくしかありません。汎用の割り算ルーチンは出回っていたようですが、どうも自力で書いていたようです。割り算が無いと言っても2の倍数で割る右シフト命令だけはあります。これを組み合わせて割れるかどうかを確かめるわけです。かなり手間取っていたようですが、最終的なコードは完成し抜群の速度を誇りましたが、結果が正しいかどうか今一つ自身が持てなくて、他の手段で検証する羽目にはなったようです。
コンピュータで計算する場合、当時の整数演算は基本16ビットのみで、さらにBASICの場合は符号付きしか無かったので、最大でも32767までです。アセンブラであれば符号なしの処理ができるのですが、それでも65535が最大です。レジスタも16ビットまでしか無かったですしね。
32ビットの割り算にも挑戦したかったのですが、少なくともインタプリタで書いても遅いばかりでお話になりません。アセンブラで書こうとしても、なにせ引き算しか無いのですから、気が遠くなるばかりでした。
素数というのは何故か人を引き付ける魅力があり、この時に関連する考え方や公式などを覚えた気がします。整数の世界は文字通り割り切れる感じがして、コンピュータ好きとの相性は良かったのかもしれません。実は数学自身はあまり得意とは言えなかったのですが、整数論であるとか論理学、集合などはバッチリだったんですよ。
この時に覚えたモロモロが、後に暗号や証明書の理解の基本となり、思ったよりも役に立っています。まあ若いうちにちゃんと手を動かしておくことは本当に大事です。
おまけ
そういえば、その物理部で開発していたオリジナルマイコンボードの名前は伝統的に素数の数字を使うようで、最近聞いた時はもう２桁の最後の方だったような。自分たちの時はようやく２桁になったくらいだったのに。
この本は必読書です！
これはさすがに買ってません^^;。
ヘッダ画像は1000までの素数一覧の一部。