Rubyで全ての約数を求めたい話のまとめ

 【Ruby】 約数を全て求めたい話 - Qiita
自然数が与えられたときその全ての約数をRubyで求めたい感じになり上記のリンク先でちょこっといろいろ書いたのですが、今回はその後日談とまとめを書こうと思いました。

提案メソッド

処理の大まかな流れとしては、
1. 素因数分解をして配列を得る。
2. 得られた素因数の組合せを全て考え、その各組合せの積の畳み込み演算結果が約数になる。
という感じです。

なお、ここでは与えられた自然数に対して全ての正の約数を得ることを考えます。

素因数分解の結果得た配列の要素に重複があった場合、自分はこの素因数の組合せを重複なく作る工夫が思いつかなかったのですが、コメントで提案していただいた方法ではそれが重複なく実現されていたので今回はそっちのみを紹介します。

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

require 'prime'   class Integer   def my_divisor_list     return [1] if self == 1     Prime.prime_division(self).map do |e|       Array.new(e[1]+1).map.with_index do |element, i|         e[0]**i       end     end.inject{|p,q| p.product(q)}.map do |a|       [a].flatten.inject(&:*)     end.sort   end end

Prime#prime_division について
この処理はPrime#prime_divisionで素因数分解ができることを前提にしているので、当然その速度にも影響されるかなあと思っていました。しかしどうやら Prime::Generator23.newで生成した擬似素数で順番に与えられた整数を割っていく処理をしているそうなので、その実装を見る限り（素因数分解でかかる時間のことは）あまり気にしなくていいかなと思いました。

Prime::Generator23

「2と3と、3 より大きくて 2 でも 3 でも割り切れない全ての整数を生成します。ある整数の素数性を疑似素数による試し割りでチェックする場合、このように低精度だが高速でメモリを消費しない疑似素数生成器が適しています。」

Ruby 1.9.3 リファレンスマニュアル　"class Prime::Generator23"　より引用
<http://docs.ruby-lang.org/ja/1.9.3/class/Prime=3a=3aGenerator23.html>
(2014/12/05 アクセス)

実行速度比較

これは与えられた数を2から順番に割っていって割り切れるなら約数、みたいに愚直にやる方法とどちらが速いのだろうと思ったので実行速度を比較してみました。前回はかなり雑な比較をしたので、ちょっとだけ正確(？)というか1〜10000までの結果をグラフに出力しました。これが正しいやり方なのかはわからないのであくまで参考程度に見てほしいです。

ちなみに比較対象の愚直メソッドは単純なものでこんな感じです。↓

?

1 2 3 4 5 6 7 8 9 10

class Integer   def divisor_list     devisors = [1]     2.upto(self/2) do |i|       devisors << i if self%i == 0     end     devisors << self     return devisors   end end

で以下の図が比較結果。縦軸がかかった時間で、横軸が計算する整数です。
ー 愚直メソッド
ー 提案メソッド

図１ 愚直メソッドと提案メソッドとの実行速度比較結果

提案メソッドの方は素因数分解の結果に左右されるのでかなりばらつきがありますが、結構安定して一定の範囲に収まってますね。

愚直メソッドの方は与えられた数の半分までひたすら割っているので数が増えるほど時間がかかるのは当たり前…。比較結果はわかりやすい感じになりましたが、いくらなんでも愚直メソッドの方が適当過ぎましたね。


というわけで第２ラウンド。愚直メソッドの方を若干手直しします。
今度は自然数nが与えられたとき√nまで愚直に割り算して割り切れるかを確認していきます。√nの値以上になったらそこで繰り返しは終了で、今度は与えられた数自身をそれまでに得た結果で割り、その商も約数というわけです。
愚直メソッド（改）

?

1 2 3 4 5 6 7 8

class Integer   def divisor_list2     return [1] if self == 1     (1..Math.sqrt(self).to_i).select do |i|       self%i == 0     end.map {|e| [e, self/e]}.flatten.uniq.sort   end end

約数には必ずペアがある的な話のやつです。ただし、例えば「81」などルートをとると整数になるものの場合、９☓９と同じ数が含まれてしまうのでその重複をなくすようにしています。



で、以下の図が結果です。
ー 愚直メソッド（改）
ー 提案メソッド

図2愚直メソッド（改）と提案メソッドとの実行速度比較結果

 

負けてしまった…。
y=x と y=x^(1/2) の差を痛感させられました。シンプルisなんとやらというわけでしょうか。
√nまでひとつひとつ割り切れるかを確認していますが、ここも擬似素数を使って素数だけチェックしていけばもっと速くなるんだろうなと。

おわりに

いや、でも自分は自分で考えた方法の方を使いたいと思います。使おうと思ってる部分ではそこまで大きな数を扱う予定も途方もなく繰り返しをする予定もないですし。

これは現在作ってるものの副産物なのですが、いろいろな計算方法を調べてる内にそういうものにとても興味がわきました。自分はしっかりとアルゴリズムの勉強をしたことがないので、これからしっかりやってみようかなという感じです。未熟者なので本文中よくわからないことを書いているかもしれませんが、どうか温かい目で。