ruby-dev

Yuguiです。

mathn.rbに収録されているPrimeクラスの使い勝手がいまいち良くないので改善
を提案します。直したいのは3点です。

1. mathn.rbに入っている
2. インスタンスを生成する必要がある
3. そもそも独自のクラスが必要か?


== mathn.rbに入っている
素数列挙は整数に閉じた計算でも必要になるものなので、mathn.rbがもたらす
  int / int => rational
は嬉しくないことがあります。

ですから、素数を列挙する機能はmathn.rbに含まれているべきではありません。
添付のパッチでは仮にlib/math/prime.rbというファイルに追い出してみました。


== インスタンスを生成する
素数列挙機能は現在は次のようにして使う必要があります。
 Prime.new.each do |prime|
   # do something
 end
要するに、Primeオブジェクトは素数列挙に対する外部イテレータです。
これは少し奇妙に思えます。次のように書きたいです。
 Prime.each do |prime|
   # do something
 end

Primeクラスの実装を見ると
 * 外部イテレータとしてPrime#succを実装
 * それを用いて内部イテレータPrime#eachを実装
 * 更に、Prime#eachにブロックが与えられない場合はEnumeratorを生成
という奇妙なことになっています。

Primeクラスのインスタンスが保持している情報は列挙中のindexだけです。
アルゴリズムとして格別の理由があるならばともかく、Primeの場合は特に外部
イテレータを優先する理由はないように思えます。

今はEnumerable::Enumeratorがあるのですから、外部イテレータ生成のためだけ
に奇妙な振る舞いをさせる必要はありません。また、Rubyライブラリとしては内
部イテレータをまず提供するのがより自然ではないでしょうか。


== そもそも独自のクラスが必要か
こうなると、Primeという独自のクラスが必要かどうかが疑問になってきます。
 Integer.each_prime do |prime|
   # do something
 end

でよいのではないでしょうか。Primeという別個のクラスが用意されていたのは
外部イテレータを提供するためにインスタンスを生成する必要があったのだと思
われます。Enumeratorが組み込みになった今、素数列挙機能はIntegerクラスに
付加するのが自然だと思います。

というわけで、そのようにするパッチを書いてみました。添付します。

-- 
Yugui <yugui@yugui.jp>
http://yugui.jp
私は私をDumpする

Attachments (1)

prime.diff (5.74 KB, text/x-diff)

diff --git a/lib/math/prime.rb b/lib/math/prime.rb
new file mode 100644
index 0000000..dc0466e
--- /dev/null
+++ b/lib/math/prime.rb
@@ -0,0 +1,98 @@
+class Integer
+  def Integer.from_prime_division(pd)
+    value = 1
+    for prime, index in pd
+      value *= prime**index
+    end
+    value
+  end
+  
+  def prime_division
+    raise ZeroDivisionError if self == 0
+    value = self
+    pv = []
+    Integer.each_prime do |prime|
+      count = 0
+      while (value1, mod = value.divmod(prime)
+	     mod) == 0
+	value = value1
+	count += 1
+      end
+      if count != 0
+	pv.push [prime, count]
+      end
+      break if prime * prime  >= value
+    end
+    if value > 1
+      pv.push [value, 1]
+    end
+    return pv
+  end
+
+  @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
+  # @@next_to_check % 6 must be 1.  
+  @@next_to_check = 103            # @@primes[-1] - @@primes[-1] % 6 + 7
+  @@ulticheck_index = 3            # @@primes.index(@@primes.reverse.find {|n|
+                                   #   n < Math.sqrt(@@next_to_check) })
+  @@ulticheck_next_squared = 121   # @@primes[@@ulticheck_index + 1] ** 2
+
+  class << self
+    # Return the prime cache.
+    def prime_so_far
+      return @@primes
+    end
+    alias prime_cache prime_so_far
+  end
+  
+  def self.primes
+    return to_enum(:each_prime)
+  end
+  def self.each_prime
+    return to_enum(:each_prime) unless block_given?
+    index = 0
+    loop do
+      while index >= @@primes.length
+	# Only check for prime factors up to the square root of the potential primes,
+	#   but without the performance hit of an actual square root calculation.
+	if @@next_to_check + 4 > @@ulticheck_next_squared
+	  @@ulticheck_index += 1
+	  @@ulticheck_next_squared = @@primes.at(@@ulticheck_index + 1) ** 2
+	end
+	# Only check numbers congruent to one and five, modulo six. All others
+	#   are divisible by two or three.  This also allows us to skip checking against
+	#   two and three.
+	@@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil?
+	@@next_to_check += 4
+	@@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil?
+	@@next_to_check += 2 
+      end
+      yield @@primes[index]
+      index += 1
+    end
+  end
+end
+
+class Prime
+  include Enumerable
+  def initialize
+    warn "Prime class is obsolete. use Integer#each_prime"
+    @enum = Integer.each_prime
+  end
+  class << self
+    def cache
+      Integer.prime_cache
+    end
+    alias primes cache
+    alias prime_so_far cache
+  end
+  def succ
+    @enum.next
+  end
+  alias next succ
+  def each
+    return to_enum(:each) unless block_given?
+    loop do
+      yield @enum.succ
+    end
+  end
+end
diff --git a/lib/mathn.rb b/lib/mathn.rb
index ce1acc9..e5d0191 100644
--- a/lib/mathn.rb
+++ b/lib/mathn.rb
@@ -12,101 +12,7 @@
 require "complex.rb"
 require "rational.rb"
 require "matrix.rb"
-
-class Integer
-
-  def Integer.from_prime_division(pd)
-    value = 1
-    for prime, index in pd
-      value *= prime**index
-    end
-    value
-  end
-  
-  def prime_division
-    raise ZeroDivisionError if self == 0
-    ps = Prime.new
-    value = self
-    pv = []
-    for prime in ps
-      count = 0
-      while (value1, mod = value.divmod(prime)
-	     mod) == 0
-	value = value1
-	count += 1
-      end
-      if count != 0
-	pv.push [prime, count]
-      end
-      break if prime * prime  >= value
-    end
-    if value > 1
-      pv.push [value, 1]
-    end
-    return pv
-  end
-end
-  
-class Prime
-  include Enumerable
-  # These are included as class variables to cache them for later uses.  If memory
-  #   usage is a problem, they can be put in Prime#initialize as instance variables.
-
-  # There must be no primes between @@primes[-1] and @@next_to_check.
-  @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
-  # @@next_to_check % 6 must be 1.  
-  @@next_to_check = 103            # @@primes[-1] - @@primes[-1] % 6 + 7
-  @@ulticheck_index = 3            # @@primes.index(@@primes.reverse.find {|n|
-                                   #   n < Math.sqrt(@@next_to_check) })
-  @@ulticheck_next_squared = 121   # @@primes[@@ulticheck_index + 1] ** 2
-
-  class << self
-    # Return the prime cache.
-    def cache
-      return @@primes
-    end
-    alias primes cache
-    alias primes_so_far cache
-  end
-  
-  def initialize
-    @index = -1
-  end
-  
-  # Return primes given by this instance so far.
-  def primes
-    return @@primes[0, @index + 1]
-  end
-  alias primes_so_far primes
-  
-  def succ
-    @index += 1
-    while @index >= @@primes.length
-      # Only check for prime factors up to the square root of the potential primes,
-      #   but without the performance hit of an actual square root calculation.
-      if @@next_to_check + 4 > @@ulticheck_next_squared
-        @@ulticheck_index += 1
-        @@ulticheck_next_squared = @@primes.at(@@ulticheck_index + 1) ** 2
-      end
-      # Only check numbers congruent to one and five, modulo six. All others
-      #   are divisible by two or three.  This also allows us to skip checking against
-      #   two and three.
-      @@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil?
-      @@next_to_check += 4
-      @@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil?
-      @@next_to_check += 2 
-    end
-    return @@primes[@index]
-  end
-  alias next succ
-
-  def each
-    return to_enum(:each) unless block_given?
-    loop do
-      yield succ
-    end
-  end
-end
+require "math/prime.rb"
 
 class Fixnum
   remove_method :/

Thread

Prev Next

In This Thread

Prev Next