learning lisp: prime numbers

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。こっちは井上さん向けに高速化の話を。

Koichi INOUE writes:

> ふふふ、間違ってました。
> せっかく先に偶数チェックをしておきながら、ループの中でも2の倍数で割ってま
> した。

そこまで気が付いたなら、

Koichi INOUE writes:

> ;;;ぐるぐる回す部分:
> (let ((i 1))
>   (while (<= i 1000)
>     (when (isprime i) (print i))
>     (setq i (1+ i))))

ここも改良しましょう。2以外の偶数は絶対に素数じゃないので、最後は 
(setq i (+ i 2)) で OK です。iは最初1なので、こうすれば奇数だけをチェッ
クするようになります。

それから、ゼロかどうかのチェックを (equal x 0) のようにやっていますが、
今の場合 x が数値であることがわかっているので、equal よりも = を使った
方が効率的です。特にある数値がゼロかどうかの判断なら (zerop x) が使え
ます。バイトコンパイルしたときは zerop が一番速くなるはずです。

あと、

> (upper (1+ (/ x 2))))

となってますが、本当の上限は (/ x 2) ではなくて、もっと小さい (sqrt x) 
です。

最後に、

> (if (>= i upper) t nil)

ですが、これは単なる (>= i upper) と完全に同等です。

;;;;;;;;;;

ここからは Lisp ではなくて素数の話ですから、適当に読み飛ばして下さい。

上の方で「2以外の素数は全部奇数である」こと利用して効率を上げる話をし
ましたが、実はもっと効率のいいやり方があります。それは

  「2と3を除くすべての素数は 6n±1 の形をしている」

という事実を利用するものです。ここでnは1以上の整数です。一応確認してみ
ましょう。

2と3を除く最小の素数は5ですから、5以上について考えます。まず、5以上の
すべての整数は、6n-1, 6n, 6n+1, 6n+2, 6n+3, 6n+4 のどれかの形で書けま
す。(剰余系で考えると 6n+5 は 6n-1 と同じことですし、6n+6 は 6n と同じ
ことです。6n+7 以降も同様。) このうち、6n+2 は 2(3n+1) ですから、2の倍
数すなわち偶数となり、素数になりえません。同様に 6n+3 = 3(2n+1) および 
6n+4 = 2(3n+2) ですから、これらはそれぞれ3の倍数、2の倍数となってやは
り素数になりえません。また 6n は6の倍数ですからもちろん素数ではありま
せん。つまり 6n-1 と 6n+1 の形をした整数だけを調べればいいことになりま
す。

ですから「井上ループ」を

(let ((i 6))
  (while (< i 1000)
    (isprime (1- i))
    (isprime (1+ i))
    (setq i (+ i 6))))

と変更し、isprime の中の upper を (sqrt x) に変えれば、ループで回る範
囲を大幅に縮小できます。

;;;;;;;;;;

と、なんだか偉そうなことを書いてますが、実は私は高校時代、ずっと数学に
は苦しめられてきました。数学は決して嫌いじゃないし、自分では好きなつも
りなんですが、テストの成績はいつも平均以下でした。国語と英語の成績が比
較的よかったこともあり、周囲の人間からは「なんでお前が理系を希望するん
だ?」と不思議がられたものです。

大学に入ってからも数学には苦しめられました。卒業に必要な最低限の単位を
ほぼ最低限の成績で何とかクリアしたというのが本当のところです。実は今も
統計学に苦しめられています。「専門は情報工学なんだから必要ないだろう」
と思って大学時代に選択しなかったことを、強く後悔しています。

数学関係で唯一成績がよかったのは、数学基礎論でした。自分で言うのも何で
すが、特に数理論理学だけはクラスの中でもぶっちぎりでした。でも私に言わ
せれば、あれは私がよくできたのではなくて、他の人達がよくわかっていない
だけです。なんでみんな論理学が苦手なんだろう。

-- 
TAKAHASHI Naoto
ntakahas@...
http://www.m17n.org/ntakahas/