« 「1以上100未満の『2個の素数の積』である整数を列挙しなさい」 | トップページ | またまた、 Problem 1 »

2009年5月29日 (金)

素因数分解

あるブログで「素因数分解の速度」を競っているような話題が出ていました。

二人が仲がよくてただじゃれあっているのか、真剣に競い合っているのかは、私の知るところではないのですが、「素因数分解の速度」については思うところがあるので、私も記事を書いてみようかな……。

もし、二人が「素数列をつくる速度」を競っていて、その延長線上で「因数分解の速度」の話になったのなら的外れになるかもしれませんが……。


「素因数分解」の速度を上げようと思ったら、素数を探して割っていくより、対象の数を 2 で割り続けて奇数にした後に、単純に小さい順に奇数で割っていくほうが速いと思います。

なにせ、素数を求めること自体にけっこう時間がかかるのですから。

(さらに、5 以上の素数 p は必ず p = 6 * n - 1 または p = 6 * n + 1 と表せる事を利用するとさらに割る数が少なくなります)


と、いうことで奇数で割り続ける「素因数分解」の Ruby 版です。

# = factorize.rb class Integer def factorize return [] if self < 2 ans = Array.new n = self [2, 3].each do |i| c = 0 while n % i == 0 c = c + 1 n = n / i end ans.push([i, c]) if c > 0 end i = 5 add = 2 while true c = 0 while n % i == 0 c = c + 1 n = n / i end ans.push([i, c]) if c > 0 i = i + add break if n < i * i add = 6 - add end ans.push([n, 1]) if n > 1 return ans end end n = ARGV[0].to_i print "#{n.factorize}\n"
$ ruby -v ruby 1.9.1p129 (2009-05-12 revision 23412) [i686-linux] $ time ruby factorize.rb 111111111 [[3, 2], [37, 1], [333667, 1]] real 0m0.078s user 0m0.020s sys 0m0.012s

Scheme 版はこちら。(普段は "Chez Scheme" を使っているのですが、同じ条件で比較するために "Gauche" で動くようにしてみました)

(define factorize (lambda (n) (define result '()) (define factor-count (lambda (n i) (let loop ([n n] [c 0]) (cond ([zero? (remainder n i)] (loop (/ n i) (+ c 1))) (else (if [> c 0] (set! result (cons (cons i c) result))) n))))) (set! n (factor-count n 2)) (set! n (factor-count n 3)) (let loop ([n n] [i 5] [add 2]) (cond ([= n 1] (reverse result)) ([> (* i i) n] (reverse (cons (cons n 1) result))) (else (loop (factor-count n i) (+ i add) (- 6 add))))))) (define (main args) (print (factorize (string->number (cadr args)))))
$ gosh -V Gauche scheme interpreter, version 0.8.13 [utf-8,pthreads] $ time gosh factorize.scm 111111111 ((3 . 2) (37 . 1) (333667 . 1)) real 0m0.060s user 0m0.012s sys 0m0.016s

では、Gemma さんのコードを見てみましょう。

(ちなみにここに書いてあるコードは終了判定に問題があったようで、こちらに改訂版が書いてあります。以下の記事では改訂版をもとに話をします)

$ gosh -V Gauche scheme interpreter, version 0.8.13 [utf-8,pthreads] $ time gosh factStrm.scm 111111111 ((3 . 2) (37 . 1) (333667 . 1)) real 0m0.174s user 0m0.092s sys 0m0.008s

このコードのスピードは Ruby 版よりは遅いですが、まだまだ実用の範囲にあると思います。


ところで、こちらのコードはというと……

まず "primes.py" というファイルが無いとエラーが出ます。しかも "primes.py" には 997 までしか素数が書き込まれないので、理論的には 994009 以上の数は素因数分解できません。

実際に実効してみると…… 7884 以上では "RuntimeError: maximum recursion depth exceeded in cmp" が出てまともな答えが出ません。

そこでこのコードが使える範囲で速度を見てみると……

$ python -V Python 2.6.2 $ time python fact.py 7882 [2, 7, 563] real 0m0.383s user 0m0.332s sys 0m0.004s $ time python fact.py 7882 [2, 7, 563] real 0m0.326s user 0m0.252s sys 0m0.012s

"primes.py" が空の一回目も "primes.py" が書き込まれた後の二回目もあまりスピードが変わりません。

同じ数字を私の Ruby 版で試してみると……

$ time ruby factorize.rb 7882 [[2, 1], [7, 1], [563, 1]] real 0m0.062s user 0m0.024s sys 0m0.004s

Python 2.6 と Ruby 1.9 では処理系自体のスピードにも差があるのかもしれませんが、Python 版は Ruby 版の約 6 倍時間がかかっています。

使用できる範囲も狭いし、速度も遅い……少なくとも Project Euler クラスの問題を解くにはとても使えません。


※ Gemma さんやみずぴーさんのところのトラックバックをたどって来られる方がいらっしゃるようなので、新しく分かった事実などを元に、以前書いた記事を書き直しました。(2009/09/02)

※ 記事を書き直した際に、Scheme 版を書き忘れていたようなので、改めて最新版を載せました。(2009/10/19)

« 「1以上100未満の『2個の素数の積』である整数を列挙しなさい」 | トップページ | またまた、 Problem 1 »

Ruby」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45166708

この記事へのトラックバック一覧です: 素因数分解:

» [Python]素因数分解 [銀月の符号]
http://tsumuji.cocolog-nifty.com/tsumuji/2009/05/post-af3f.html を参考に作成。素数を求めて割るより、奇数で割ってしまったほうが早いとのこと。あと、 5 以上の素数は p = 6 * n ± 1 の形になるというのも利用。 factorize.py # coding: utf-8 u素因... [続きを読む]

« 「1以上100未満の『2個の素数の積』である整数を列挙しなさい」 | トップページ | またまた、 Problem 1 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ