ruby-dev

Yuguiです。

keiju ISHITSUKA さんは書きました:
> では, 新案待っています(^^;

新しい案を書いてみました。パッチを添付します。

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

↑このあたりは第2案のままです。そして、

* ファイル名をlib/prime.rbにしました
* Prime.eachがありますが、
   > というかですね. クラスは基本として記述子であって, インスタンスではない
   > です. つまり, 素数全体を表すものもインスタンスであって欲しいです.

  を受けて、中田さん案のように特異メソッドを持つインスタンスにしました。

* 互換性のためPrime.newが可能で、これは外部イテレータを返します。且つ、
  Prime === Prime.new です。
* 中田さんのパッチを取り込んで、素数表の拡大をスレッドセーフにしました。
* ついでにtest/test_prime.rb を足しました。

ご検討を、何卒よろしくお願いします。

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

Attachments (1)

prime-refactoring-3.patch (9.38 KB, text/x-diff)

diff --git a/lib/mathn.rb b/lib/mathn.rb
index ce1acc9..2af2b83 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 "prime.rb"
 
 class Fixnum
   remove_method :/
diff --git a/lib/prime.rb b/lib/prime.rb
new file mode 100644
index 0000000..29ee0eb
--- /dev/null
+++ b/lib/prime.rb
@@ -0,0 +1,127 @@
+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 = []
+    for prime in 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
+
+  def Integer.each_prime(&proc)
+    Prime.each(&proc)
+  end
+end
+
+class << (Prime = Object.new)
+  include Enumerable
+
+  def new
+    warn("Prime class is obsolete. use Prime::each.")
+    return Generator.new
+  end
+
+  def ===(rhs)
+    return Prime.equal?(rhs) || Generator === rhs
+  end
+
+  def each(&proc)
+    Generator.new.each(&proc)
+  end
+
+  # Return the prime cache.
+  def cache
+    Generator.cache
+  end
+  alias primes cache
+  alias primes_so_far cache
+
+  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
+    @@lock = Mutex.new
+
+
+    # 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
+      if @index >= @@primes.length
+	@@lock.synchronize 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
+	end
+      end
+      return @@primes[@index]
+    end
+    alias next succ
+
+    def each
+      return self.dup 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/test/test_prime.rb b/test/test_prime.rb
new file mode 100644
index 0000000..93634b0
--- /dev/null
+++ b/test/test_prime.rb
@@ -0,0 +1,111 @@
+require 'test/unit'
+require 'prime'
+require 'stringio'
+
+class TestPrime < Test::Unit::TestCase
+  # The first 100 prime numbers
+  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, 103, 107, 109, 113, 127, 131, 
+    137, 139, 149, 151, 157, 163, 167, 173, 179, 
+    181, 191, 193, 197, 199, 211, 223, 227, 229, 
+    233, 239, 241, 251, 257, 263, 269, 271, 277, 
+    281, 283, 293, 307, 311, 313, 317, 331, 337, 
+    347, 349, 353, 359, 367, 373, 379, 383, 389, 
+    397, 401, 409, 419, 421, 431, 433, 439, 443, 
+    449, 457, 461, 463, 467, 479, 487, 491, 499, 
+    503, 509, 521, 523, 541,
+  ]
+  def test_each
+    primes = []
+    Prime.each do |p|
+      break if p >= 100
+      primes << p
+    end
+    # \pi(100) == 25
+    assert_equal PRIMES[0, 25], primes 
+    assert Prime.cache.length >= 25
+  end
+
+  def test_each_by_prime_number_theorem
+    3.upto(15) do |i|
+      max = 2**i
+      primes = []
+      Prime.each do |p|
+        break if p >= max
+        primes << p
+      end
+
+      # Prime number theorem
+      assert primes.length >= max/Math.log(max)  
+      assert primes.length <= (2..max).step(0.1).inject(0){|sum,x| sum + 0.1 / Math.log(x)} # Li(x)
+
+      assert Prime.cache.length >= primes.length
+    end
+  end
+
+  def test_each_without_block
+    enum = Prime.each
+    assert enum.respond_to?(:each)
+    assert enum.kind_of?(Enumerable)
+    assert enum.respond_to?(:with_index)
+    assert enum.respond_to?(:next)
+    assert enum.respond_to?(:succ)
+    assert enum.respond_to?(:rewind)
+  end
+
+  def test_new
+    buf = StringIO.new('', 'w')
+    orig, $stderr = $stderr, buf
+
+    enum = Prime.new
+    assert !buf.string.empty?
+    $stderr = orig
+
+    assert enum.respond_to?(:each)
+    assert enum.kind_of?(Enumerable)
+    assert enum.respond_to?(:with_index)
+    assert enum.respond_to?(:next)
+    assert enum.respond_to?(:succ)
+    assert enum.respond_to?(:rewind)
+
+    assert Prime === enum
+  ensure
+    $stderr = orig
+  end
+
+  def test_eqq
+    assert Prime === Prime
+  end
+
+  def test_enumerator_succ
+    enum = Prime.each
+    assert_equal PRIMES[0, 50], 50.times.map{ enum.succ }
+    assert_equal PRIMES[50, 50], 50.times.map{ enum.succ }
+    enum.rewind
+    assert_equal PRIMES[0, 100], 100.times.map{ enum.succ }
+  end
+
+  def test_enumerator_with_index
+    enum = Prime.each
+    last = -1
+    enum.with_index do |p,i|
+      break if i >= 100
+      assert_equal last+1, i
+      assert_equal PRIMES[i], p
+      last = i
+    end
+  end
+
+  class TestInteger < Test::Unit::TestCase
+    def test_prime_division
+      pd = PRIMES.inject(&:*).prime_division
+      assert_equal PRIMES.map{|p| [p, 1]}, pd
+    end
+
+    def test_from_prime_division
+      assert_equal PRIMES.inject(&:*), Integer.from_prime_division(PRIMES.map{|p| [p,1]})
+    end
+  end
+end

Thread

Prev Next

In This Thread

Prev Next