ruby-dev

Yuguiです。

いしづかさん、ありがとうございます。

keiju ISHITSUKA さんは書きました:
>> == mathn.rbに入っている
>> 素数列挙は整数に閉じた計算でも必要になるものなので、mathn.rbがもたらす
>>  int / int => rational
>> は嬉しくないことがあります。
> 
> 分からないことはないです.
(snip)
> そのあたりが, lib/prime.rb でなく lib/math/prime.rb という遠慮になって
> いるような気がします.

そうですね。私もlib/prime.rbは大げさすぎると感じました。場所は他に適当な
ものを思いつかなかったのでlib/math/prime.rbにしたまでですが、分けていた
だけると助かります。



>> == インスタンスを生成する
>> 要するに、Primeオブジェクトは素数列挙に対する外部イテレータです。
>> これは少し奇妙に思えます。
> 
> 全然奇妙でもないと思いますが? 概念的には, Primeインスタンスが素数の集
> 合を表していると考えているからです. その素数集合から数え上げていると考
> えているのでこのようなインターフェースになっています.

素数の全体のインスタンスが複数存在し得るのはおかしいです。整数の全体に対
応するものがIntegerであるように、素数の全体に対応するのはPrimeであるほう
が自然だと感じました。

結局、素数の全体をRubyにおいてどうやって表すかという同じところについての
見解の相違に帰結するのでしょうが、
> for prime in Prime
>   # ...
> end
> 
> って書くとおかしい気がするので, 

私にはおかしくなく、こちらのほうが表記として自然だと感じられます。


素数全体というもののRuby表現が複数存在し得るようになっているのは、やはり
外部イテレータとしての機能を期待されていたがためではないでしょうか。
私としては、その機能を抜けば素数全体は唯一であるべきであると考えます。

そして、実装上の指摘3点について、
(1)
> 現行のPrimeから内部イテレータを実現する方法とYuguiさんの内部イテレータ
> からEnumertorを利用する方法とどちらが自然かといえば, 外部イテレータを
> 実現するためにFiberを用いている方がよっぽど不自然だと思います. 牛刀っ
> て感じがします.

牛刀といえばそうかもしれません。

(2)
> Enumeratorと外部イテレータとしてのPrimeインスタンスですが, Enumerator
> はスレッドの境界を越えられないという制約がありますので, そのような制約
> のないPrimeからわざわざダウグレードする必要はないです.

確かに。

(3)
> 次に, 実装的側面から, Yuguiさんの実装はでは, Integerのクラス変数として
>
>   @@primes
>   @@next_to_check
>   @@ulticheck_index
>   @@ulticheck_next_squared
>
> とうが, 導入されていますが, これはとても許せないですね. Integerのクラ
> ス変数としてはふさわしくないと思います.

これも確かに。

であれば、こういうのはどうでしょうか。

1. Prime::Generator という素数列挙の外部イテレータクラスを作成
  1.1. 互換性のため、また内部イテレータの提供者としてPrimeクラスを温存
2. Prime.each は Prime::Generator オブジェクトを呼び出して列挙
3. (optional) Integer.each_primeはPrime.eachに転送

このように変更してみたパッチを添付します。

理由としては、
1. わざわざ外部イテレータのクラスを新設するのは、実装上で指摘を頂いたデ
メリットは納得できる一方で、やはり素数全体を表すインスタンスが複数存在す
るのは違和感を持つためです。Primeのインスタンスが外部イテレータであるこ
とを避けられれば、インスタンス化はobsoleteにできます。

2. Prime.eachという用法は欲しいです。そして、これは単なる利便性のためだ
けではなく「素数全体」をあらわすのがPrime定数、つまり唯一であってほしい
からです。

3. Integer.each_primeはどうしても欲しいというほどではありませんが、素数
列挙機能があって整数クラスがあるならば、整数クラスに列挙機能が付いていた
方が自然であると感じます。

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

Attachments (1)

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

diff --git a/lib/math/prime.rb b/lib/math/prime.rb
new file mode 100644
index 0000000..36e6b26
--- /dev/null
+++ b/lib/math/prime.rb
@@ -0,0 +1,120 @@
+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
+
+  def Integer.each_prime(&proc)
+    Prime.each(&proc)
+  end
+end
+  
+class Prime
+  include Enumerable
+
+  def each(&proc)
+    Generator.new.each(&proc)
+  end
+
+  class << self
+    include Enumerable
+    # Return the prime cache.
+    def cache
+      Generator.cache
+    end
+    alias primes cache
+    alias primes_so_far cache
+    def each(&proc)
+      Generator.new.each(&proc)
+    end
+  end
+
+  class Generator
+    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
+
+
+    # Return the prime cache.
+    def self.cache
+      return @@primes
+    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 self unless block_given?
+      loop do
+	yield succ
+      end
+    end
+    alias with_index each_with_index
+    def rewind
+      @index = -1
+    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