Re: [bep] learning lisp: prime numbers

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。今日は七夕ですが、残念ながら曇っていて星は見えません。

Koichi INOUE writes:

>> (setq x '(a b c)) => (a b c)
>> (setq y x) => (a b c)
>> (eq x y) => t
>> 
>> ですが、
>> 
>> (setq x '(a b c)) => (a b c)
>> (setq y '(a b c)) => (a b c)
>> (eq x y) => nil

> ポインタ比較のような印象でしょうか。

まさにそのとおりです。さすが、Cを知っている人は理解が速い。私はCより前
に Lisp を知ったので、ここのところを理解するのに少々時間がかかりました。

> 後者の場合同じ(a b c)でもそれぞれのリストの参照ポインタは違う、みたいな。
> 片方のリストを後から変更したとしてももう一方には影響しないし。

そうです。後者の場合、実際には2つの異なる (a b c) が作られ、xとyはそれ
ぞれ別の (a b c) へのポインタを持つことになります。

> setq であるシンボルを評価した値を他のシンボルにバインドすると、ポインタ
> がコピーされるようなもので同一のオブジェクト(この場合は(a b c))のリス
> トをさすようになりますよね。

はい、そのとおりです。

>> あとこれは今思い付いたんですが、isprime の中で割り切れるか次々に試すと
>> き、合成数で割ってみる必要はありませんね。たとえば7で割り切れないなら、
>> 21で割り切れるはずがありませんから。逆に言うと、x が n*m で割り切れる
>> なら n*m より小さい n でも割り切れるはずです。つまり x が素数であるか
>> どうか調べるには、(sqrt x) 以下の素数で割り切れるかどうかだけを調べれ
>> ばいいことになります。
>> 
>> # これって本当? 今まで明示的にそう書いてあるのを読んだことがないような
>> # 気がしますが。

> 証明したくはないですがそうみたいですよね。

あのメールを書いてからしばらく考えていたら、直観的にも自明のような気が
してきました。まず (sqrt x) 以下の整数で割り切れるかどうか調べればいい
ことは x = m * n (x, m, n は整数) と書けるときの m, n の最大値が (sqrt
x) を超えないことから簡単に証明できます。次に合成数 m * n で割り切れる
なら m および n でも割り切れることは自明です。ということは、m * n の形
で表せない数、すなわち素数だけで割り切れる場合だけを調べればいいことに
なります。

> リストを使った効率のいい素数探し、後で考えてみます。
> リストの勉強になりそうです。

ぜひやってみて下さい。「2からx-1までの数で順番に割ってみる」という一番
シンプルな場合と比較してどのくらい速度が向上するか調べると、きっとびっ
くりすると思います。

>> あとどうでもいいことですけど、isprime ってCの訛が出ていますね。Lisp 方
>> 言なら primep でしょう。

> そうでした。(^^;)

あるいは prime-number-p ですね。井上さんならもう御存知だと思いますが、
Emacs Lisp においては、ある条件を満たしているかどうか判定する関数を作
るときの名前は、

・判定条件を表すのが一語なら、ハイフン無しで最後に p を付ける
・判定条件を表すのが2語以上なら、最後に -p を付ける

という習慣です。

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