Re: [bep] 割り算の答えを小数で出すには？ <Re: learning lisp: while

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。

井上さんのアドバイスに従って、Emacs Lisp の話はこのままここで続けるこ
とにします。

Reiko TAKAHASHI  (高橋玲子)writes:

> } printの代わりに
> } (insert (format "%s\n" なになに))
> } とすれば今いるバッファに入ります。

> 　やってみました。
> ふつう、なにかを表示させたいときには、この形式を使うのが一般的ですか？

そうです。実用的なプログラムを書くときは大いに使うことになるので、覚え
ておいて損はありません。

> (let ((x 1000) (y 3))
>   (while 
>       (or (> x 3) (/= (% x 2) 0))
>     (while 
> 	(and (<= y (+ (/ x 2) 1))  
> 	     (/= (% x y) 0))
>       (setq y (+ y 1))
>       (when (= y (+ (/ x 2) 1)) 
> 	(insert (format "%s\n" x)))) 
>     (setq x (- x 1))
>     (setq y 3))
>   (insert (format "%s\n" 3))  
>   (insert (format "%s\n" 2)))

外側の while における条件 (or (> x 3) (/= (% x 2) 0)) は、多分望んでらっ
しゃるのとは違う働きをしていると思います。多分意図としては、「3より大
きくてかつ奇数の場合」だけループを実行しようということじゃないかと思う
んですが、違うでしょうか。

実際には、外側の while は次のように動くことになります。

1. xが1000から4の間は、xを1ずつ小さくしながらループを回る。

# 関数 or は、最初に t になった時点で残りを評価せずに終了します。です
# からxが3より大きい場合 (> x 3) は、後ろの /= は無視されます。

2. xが3のときは、or の第2式が t になるのでやはりループを実行する。

3. xが2になると、or の第2式が nil を返すので、外側の while が終了する。

つまり外側の while の条件式は、結局 (> x 2) と同じことになっています。

もし「3より大きくてかつ奇数の場合」だけを調べたいのなら、

(let ((x 999) (y 3))
  (while (> x 3)
    内側の while
    (setq x (- x 2))
    (setq y 3))
  最後の insert 2つ)

のようにします。最初を999という奇数で始め、それから2ずつ引いていけば奇
数だけをチェックするようになります。

次に内側のループですが、ここには無駄があります。最後の when とそれに続
く insert は、while の外に出せます。

(while
  (and (<= y (+ (/ x 2) 1))
       (/= (% x y) 0))
  (setq y (+ y 1)))
(when (= y (+ (/ x 2) 1))
(insert (format "%s\n" x))

この while ループは、y が上限値以下で、かつ x が y で割り切れない間ずっ
と続きます。反対に言うと、この while が終了するのは y が上限に達したか、
あるいは x が y で割り切れた場合です。while が終了した後も y は最後の
値を保持したままですから、ループの中で毎回 when のチェックをする必要は
ありません。ループが終わった後で1回やれば充分です。

それから他のスレッドで話題になっていますが、y で割り切れるかどうかチェッ
クするときの上限値は (+ (/ x 2) 1) ではなくて、(sqrt x) です。sqrt は
square root (平方根) の略です。x が2以上の場合、(sqrt x) は常に
(+ (/ x 2) 1) よりも小さくなりますから、ループを回る回数をさらに減らす
ことができます。

> } > 　どさくさで、
> } > (not (= (/ x y) (/ (float x) y)))
> } > としてみました。
> } 
> } やり方は何通りもあると思いますが、これは初めて見るパターンです。よく思
> } い付きましたね。

> 　おそろしく力任せですよね(^^;)。でも、思いついたときはちょっとうれしかっ
> たです。

でしょう。自分でなんとかやり方を見つけたときは嬉しいものです。

> 　3とか2は、とても悩ましいです。どうすればいいんでしょう……？
> 1は素数ではなかったんですね。ずるが一つ減らせてうれしいかも。

えーと、2とか3の場合ってそんなに面倒ですか?  素直に書けると思うのです
が…。ちょっとやってみましょう。

;; n高橋バカ正直バージョン
;; 2から1000まで全部調べる
;; xが素数かどうかは、2からx-1までの全部の数で割って調べる
(let ((x 2) y)                          ; 素数かどうか調べる数(x)の初期値は2
  (while (<= x 1000)                    ; xの最大値は1000
    (setq y 2)                          ; 最初に割ってみる数(y)は2
    (while (and (< y x) (/= 0 (% x y))) ; yがxより小さくてかつ割り切れない間は
      (setq y (1+ y)))                  ;   yを1増やして次のチェック
    (when (= y x)                       ; y=xならば全部のyで割り切なかったはず
      (insert (format "%s\n" x)))       ; つまりxは素数
    (setq x (1+ x))))                   ; 次のxを調べる

できているようなので、ちょっと高速化します。

;; n高橋スマートバージョン
;; 2は特別扱いして、奇数だけ調べる
;; xが素数かどうかは、(sqrt x) までの奇数で割って調べる
(let ((x 3) y limit)                    ; 3から調べ始める
  (insert "2\n")                        ; ここだけずるをする
  (while (<= x 1000)
    (setq y 3 limit (sqrt x))           ; 試し割りは3からルートxまで
    (while (and (<= y limit) (/= 0 (% x y))) ; limitも試すので<=と等号が必要
      (setq y (+ y 2)))                 ; 試し割りは奇数だけなので+2
    (when (> y limit)                   ; limitで割り切れたときは合成数
      (insert (format "%s\n" x)))       ;   だから>=でなくて>
    (setq x (+ x 2))))                  ; 次の奇数を試す

調子に乗ってさらに高速化。

;; n高橋爆速バージョン
;; 6n±1法 (2と3は特別扱い)
;; xが素数かどうかは、(sqrt x) までの素数で割って調べる
;; 関数呼び出しは重いので、+1と-1の両方の場合をインライン展開
(let* ((primes '(2 3))
       (tail (last primes))
       (x 6)
       x1 p limit)
  (insert "2\n3\n")

  (while (< x 1000)

    (setq x1 (1- x)
	  p primes
	  limit (sqrt x1))
    (while (and (<= (car p) limit) (/= 0 (% x1 (car p))))
      (setq p (cdr p)))
    (when (> (car p) limit)
      (setcdr tail (list x1))
      (setq tail (cdr tail))
      (insert (format "%s\n" x1)))
    
    (setq x1 (1+ x)
	  p primes
	  limit (sqrt x1))
    (while (and (<= (car p) limit) (/= 0 (% x1 (car p))))
      (setq p (cdr p)))
    (when (> (car p) limit)
      (setcdr tail (list x1))
      (setq tail (cdr tail))
      (insert (format "%s\n" x1)))

    (setq x (+ x 6))))

ループの回数は減っているけど、本当に速くなってるかなあ。オーバーヘッド
の方が大きかったりして。^_^;;

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