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

2009年5月24日 (日)

"math_tool.rb" by Ruby 1.9.1

しばらく、Scheme ばかり使ってきた反動か、最近は Ruby でコードを書きたい衝動にかられています。

私が使用している Ubuntu のパッケージで管理されているのは Ruby 1.8.7 と Ruby 1.9.0 なのですが、「やっぱりこれからは 1.9.1 でしょ」ということで、自前で Ruby 1.9.1 をインストールしてみました。

いや〜、1.9.1 は速くなりましたねぇ……。同じスクリプトを走らせても、普通に 2 〜 3 倍は速くなっている感じです。Shell からスクリプトとして実行した Chez Scheme のコードに引けを取らない速さにビックリです。

これからしばらくは、今まで Scheme で解いてきた Project Euler の問題を改めて Ruby で解いていきたいと思います。


そこで、今後使っていくことになるであろう自作のメソッドなどを、まとめて紹介しておきます。

私は、これらのメソッドを "math_tool.rb" という名前で保存して使っています。

# -*- coding: utf-8 -*- # # = math_tool.rb -- Methods for "Project Euler" # # Author:: ツムジ # class Integer # call-seq: # n.prime? -> bool # # * n が素数ならば true を返す。 ( 試し割法 ) # * 添付ライブラリの prime.rb を参考に改良。 # # === Example # 3.prime? # => true # def prime? return true if self == 2 or self == 3 return false if self.even? or self % 3 == 0 or self <= 1 limit = (self ** 0.5).to_i i = 5 add = 2 while limit >= i return false if self % i == 0 i = i + add add = 6 - add end return true end # call-seq: # n.fast_prime? -> bool # # * n が素数ならば true を返す。( Miller-Rabin test ) # * Wikipedia から引用 ( 一部改変 ) # # === Example # 3.fast_prime? #=> true # def fast_prime? n = self.abs() return true if n == 2 return false if n == 1 || n & 1 == 0 d = n-1 d >>= 1 while d & 1 == 0 10.times do a = rand(n-2) + 1 t = d y = pow(a,t,n) while t != n-1 && y != 1 && y != n-1 y = (y * y) % n t <<= 1 end return false if y != n-1 && t & 1 == 0 end return true end def pow(base, power, mod) result = 1 while power > 0 result = (result * base) % mod if power & 1 == 1 base = (base * base) % mod power >>= 1; end result end # call-seq: # n.to_a -> array # n.to_a(radix) -> array # # * n の各桁を要素とする配列を返す。 # * 基数を radix として指定できる。 # # === Example # 123.to_a => [1, 2, 3] # 123.to_a(2) => [1, 1, 1, 1, 0, 1, 1] # def to_a(radix = 10) n = self a = Array.new while (n >= radix) do n, r = n.divmod(radix) a.unshift(r) end return a.unshift(n) end # call-seq: # n.factorize -> array # # * n を素因数分解した結果を配列にして返す。 # # === Example # 120.factorize #=> [[2, 3], [3, 1], [5, 1]] # 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 # call-seq: # n.divisor -> array # # * n の約数を配列にして返す。 # # === Example # 12.divisor #=> [1, 2, 3, 4, 6, 12] # def divisor sq = self ** 0.5 sqi = sq.to_i d1 = (1 .. sqi).select{|i| self % i == 0} d2 = d1.map{|i| self / i} d1.pop if sq == sqi return d1.concat(d2.reverse) end # call-seq: # n.divisor2 -> array # # * n の約数を配列にして返す。 # * 素因数分解の結果を元に計算している。 # * n > 5000 で Integer#divisor より速度的に優位になる? # # === Example # 12.divisor2 #=> [1, 2, 3, 4, 6, 12] # def divisor2 f_arr = self.factorize.map{|f, i| (0 .. i).map{|j| f ** j}} f_arr = f_arr.inject([1]) do |pro, arr| pro = pro.map{|i| arr.map{|j| j * i}}.flatten end return f_arr.sort end # call-seq: # n.sum_of_divisors -> integer # # * n の「真の約数の和」を返す。 # * 詳しくは『数学ガール』を参照のこと。 # * self < 2 の場合は、本来 error にすべきだが 0 を返すように # してある。 # # === Example # 28.sum_of_divisors #=> 28 # def sum_of_divisors return 0 if self < 2 arr = self.factorize.map do |f, i| (f ** (i + 1) - 1) / (f - 1) end return arr.inject(:*) - self end # call-seq: # n.amicable_pair -> integer or nil # # * n と友愛数の組みになる整数を返す。 # # === Example # 220.amicable_pair #=> 284 # 221.amicable_pair #=> nil # def amicable_pair a = self.sum_of_divisors return false if a == self if self == a.sum_of_divisors return a else return nil end end # call-seq: # n.perfect? -> bool # # * n が完全数ならば true を返す。 # # === Example # 28.perfect? #=> true # def perfect? return false if self < 2 return self == self.sum_of_divisors end # call-seq: # n.abundant? -> bool # # * n が過剰数ならば true を返す。 # # === Example # 12.abundant? #=> true # def abundant? return false if self < 2 return self < self.sum_of_divisors end # call-seq: # n.deficient? -> bool # # n が不足数ならば true を返す。 # # === Example # 9.deficient? #=> true # def deficient? return false if self < 2 return self > self.sum_of_divisors end # call-seq: # n.factorial -> integer # n.factorial(m) -> integer # # * n の階乗または下降階乗冪を返す。 # * n.factorial == n! # * n.factorial(m) == n * (n - 1) * ... * (n - m + 1) # * n < m の場合、n.factorial(m) == 0 # # === Example # 5.factorial #=> 120 # 5.factorial(3) #=> 60 # def factorial(m = self) fact = (self - m + 1 .. self).inject(:*) return (fact or 1) end # call-seq: # n.permutation_size(r) -> integer # # * 順列 nPr の数を返す。 # # === Example # 5.permutation_size(3) #=> 60 # def permutation_size(r = self) return self.factorial(r) end # call-seq: # n.combination_size(r) -> integer # # * 組み合わせ nCr の数を返す。 # # === Example # 5.combination_size(3) #=> 10 # def combination_size(r) return self.permutation_size(r) / r.factorial end # call-seq: # n.pandigital? -> bool # # * n が Pandigital な整数ならば true を返す。 # # === Example # 35412.pandigital? #=> true # def pandigital? self.to_a.pandigital? end # call-seq: # n.palindromic? -> bool # # * n が回文数ならば true を返す。 # # === Example # 12321.palindromic? => true # def palindromic? str = self.to_s return str == str.reverse end # call-seq: # n.make_palindromic -> integer # n.make_palindromic(:odd) -> integer # n.make_palindromic(:even) -> integer # # * n を上位の桁とする回文数をつくる。 # * 引数が省略された場合、奇数桁の回文数をつくる。 # * 引数が :odd の場合、奇数桁の回文数をつくる。 # * 引数が :even の場合、偶数桁の回文数をつくる。 # # === Example # 123.make_palindromic #=> 12321 # 123.make_palindromic(:odd) #=> 12321 # 123.make_palindromic(:evne) #=> 123321 # def make_palindromic(flag = :odd) str1 = self.to_s str2 = str1.reverse str1.chop! if flag == :odd return (str1 << str2).to_i end # call-seq: # n.sum_of_digits -> integer # # * 各桁の和を返す。 # # === Example # 123.sum_of_digits #=> 6 # def sum_of_digits arr = self.to_s.split('') return arr.inject(0){|sum, st| sum + st.to_i} end end class Array # call-seq: # arr.to_i -> integer # arr.to_i(radix) -> integer # # * 配列の要素を各桁とする整数を返す。 # * 基数を radix として指定できる。 # # === Example # [1, 2, 3].to_i #=> 123 # [1, 1, 1, 1, 0, 1, 1].to_i(2) #=> 123 # def to_i(radix = 10) return self.inject(0){|sum, i| sum * radix + i.to_i} end # call-seq: # arr.pandigital? -> bool # # * arr が Pandigital な配列ならば true を返す。 # # === Example # [1, 2, 4, 3].pandigital? #=> true # def pandigital? self.sort.each_with_index do |a, i| return false unless a == i + 1 end return true end # call-seq: # arr.palindromic? -> bool # # * arr が回文配列ならば true を返す。 # # === Example # [1, 2, 3, 2, 1].palindromic? #=> true # def palindromic? return self == self.reverse end end # call-seq: # prime_list(n) -> array # # * n 以下の素数を配列にして返す。 # * エラトステネスの篩 : 加算版 # # === Example # prime_list(20) => [2, 3, 5, 7, 11, 13, 17, 19] # def prime_list(n) return [] if n < 2 return [2] if n == 2 limit = (n ** 0.5).to_i arr = (1 .. n).step(2).to_a arr[0] = 2 len = arr.size i = 0 while true i = i + 1 j = arr[i] next unless j break if j > limit k = 2 * i * (i + 1) while k < len arr[k] = nil k = k + j end end arr.compact! return arr end # call-seq: # pythagorean_triples(n) -> array # # * a < b < c, a + b + c = n, a² + b² = c² の条件を満たす # [a, b, c] を配列にして返す。 # # === Example # pythagorean_triples(90) #=> [[9, 40, 41], [15, 36, 39]] # pythagorean_triples(90).select do |a, b, c| # a.gcd(b).gcd(c) == 1 # 既約でないものを除く # end #=> [[9, 40, 41]] # def pythagorean_triples(n) return [] if n.odd? ans = Array.new 1.upto(n / 3) do |a| q, r = (n * n).divmod(2 * n - 2 * a) if r == 0 b = n - q break if a > b ans.push([a, b, n - a - b]) end end return ans end # call-seq: # amicable_numbers(min, max) -> array # # * min 〜 max の範囲に存在する友愛数の組を配列にして返す。 # # === Example # amicable_numbers(1, 2000) #=> [[220, 284], [1184, 1210]] # def amicable_numbers(min, max) min = 2 if min < 2 ans = Array.new (min .. max).each do |a| b = a.amicable_pair if b and a < b ans.push([a, b]) end end return ans end # call-seq: # phi(n) -> integer # # * オイラーのφ関数 # * 正の整数 n に対して、1 から n までの自然数のうち n と互いに # 素なものの個数(1 と n は互いに素と考える) # # === Example # phi(6) = 2 (1, 5 のみなので) # def phi(n) arr = (1 ... n).to_a.select{|i| i.gcd(n) == 1} return arr.size end

追記 < 2009/09/08/ > : prime_list にバグを見つけたので、修正しました。

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

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

Project Eulerですから、自作することに意味があるのかもしれませんが、素数周りは1.9.1には添付ライブラリprime.rbがあります。念のため。

Yugui さん、コメントありがとうございます。
私も以前から prime.rb の存在は知っていました。
今回発表したメソッドは、元々は、Chez Scheme 用に自作した手続きを Ruby に移植したものでした。
これらのメソッドを使っていたのは、Ruby 1.8 時代の素数まわりのメソッドが自作のメソッドより遅い印象があったからでした。
ご指摘を受けてから、改めて検証したところ、prime.rb の Prime#prime_division の方は、自作の Integer#factorize より若干速いようです。ただ、Prime#prime? より自作の Integer#prime? の方が若干速いでした。
今後は、prime.rb も積極的に使っていきたいと思います。

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: "math_tool.rb" by Ruby 1.9.1:

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

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            
フォト

最近のトラックバック

無料ブログはココログ