リスト修行素因数分解(2)

どうやら、前回の素因数分解にはバグがあったみたい(修正しました)

という訳で、素因数分解を速度アップしながら改善していこう〜

問題点

前回は、素数を作ってから、素因数分解してました。これだと必要とする全ての素数を作らないとダメ。

この問題点を改善していきたいと思います。

改善案

素数を全て見る必要は無いので、「素因数分解しながらふるいにかける」という作戦でいきたい。

リスト修行らしくなってきました!!

作戦

12の素因数分解について考えてみる。

まず2〜12までのリストを用意する
- (2 3 4 5 6 7 8 9 10 11 12)
- 前回はここで絞りすぎた。
いきなり素因数分解を始める。
- 12の時、2で割り切れるので、6。結果に2を加える。(2)
- 6の時、2で割り切れるので,3。結果に2を加える。(2 2)
- 3があったが、2で割り切れない。
ここで、先頭の2を切ってふるいにかける。
- (3 5 7 9 11)
- ふるいの中は半分に。
もう一回素因数分解する
- 3の時、3で割り切れるので1。結果に3を加える。(2 2 3)
1になったので、終了。

全てのリストをふるいにかける必要はなさそうだ。値が素数の時だけ、最後までふるいにかければいい。

コーディング

かなり頑張った。

(define (factor n)
  (define (primers-iter l)
    (filter
      (lambda (o)
        (not (zero? (modulo o (car l)))))
      (cdr l)))
  (define (iter m l)
      (cond ((= m 1) '())
            ((zero? (modulo m (car l)))
             (cons (car l)
                   (iter (/ m (car l)) l)))
            (else
              (iter m (primers-iter l)))))
  (iter n (iota (- n 1) 2)))

てすと。

(factor 1) ; ()
(factor 12) ; (2 2 3)
(factor 123) ; (3 41)
(factor 1234) ; (2 617)
(factor 12345) ; (3 5 823)
(factor 123456) ; (2 2 2 2 2 2 3 643)
(factor 1234567) ; (127 9721)

特に2のn乗の素因数分解が早い

(factor 4194304) ; (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)

まだまだ改善の余地がありそうだけど、バグは取れたし、高速化出来た。

検算について

そそ、素因数分解の検算は簡単。

(fold * 1 (factor 12)) ; 12

敵あらわる

factorハヤスギ

% factor 11111111111111111
11111111111111111: 2071723 5363222357

えぇぇぇぇ・・・一瞬で出たよ。

が・頑張る。

課題

速度の一番のウィークポイントは、素数リストの生成と、ふるい。ふるいをかけない2のn乗はやたら早い。

改善案として、素数リストをあらかじめ絞っておくというのもひとつの手だけど、桁を増やしたらすぐに対応出来なくなってしまう。
もうひとつの改善案として、素数リストの生成を、遅らせる。つまり、必要になってから、素数リストを作る。という方法があるように思うが、僕のSchemeレベルではまだ無理。

素数の旅はまだまだ続く。