[ruby-dev:35953] Re: Refactoring of enumerating prime numbers

けいじゅ＠いしつかです.

なんか, 送ったメイルがスパム扱いになったようなので, 再送します.

yuguiさんのとは意図しているところは大体同じだと思いますが...

In [ruby-dev :35883 ] the message: "[ruby-dev:35883] Re: Refactoring
of enumerating prime numbers ", on Aug/20 12:13(JST) Nobuyoshi Nakada
writes:

>なかだです。

>> 私もそうなのかなぁ? と思いつつも, では, 元のクラスの名前はどうするんだ? 
>> と思ったりもしてます.
>
>class << (Prime = Object.new); end で。

それも考えたんですが... Generator と絡みますので, そちらで.

>Enumerableは入れ忘れですが、Generatorのように別クラスを介する必
>要はないのではないかということです。

Generatorが一種類ならそれは言えると思うのですが, 豊福さんのメイルのよ
うに,単調増加で少なくともすべての素数が含まれる数列を用いる方が良い場
合もあるので, Generator は 別にあった方がよい気がしています.

>それがPrime自身の役割なんじゃないかなぁと。

私が言いたかったこととちょっとずれてるかも. 詳しくは添付のコードを見て
いただきたいのですが, @@class_var が多用されているのが気にくわないので, 
それをなくしたかったのです.

>> また, 微妙にスレッドセーフでない気もしたりもしているので, そこも解消で
>> きればなぁ. などと思ったりしています
>そこは問題ですね。Prime#succのループをsynchronizeさせればいいで
>しょうか。

いっておいて, 何なんですが(^^;; rubyのライブラリはほとんどがスレッドセー
フでないので, 気にしなくてもよい気になっています.

新案:

* Primeクラスは singleton.
* Primeクラスメソッドはインスタンスメソッドにデレゲートする.

* Prime::Generator 
  素数列のgenerator

* Prime::Generator23
  豊福さんのgenerator. 
  名前の由来: 2と3の倍数以外の数値なので.

* Prime::IncreaseSuperPrimeGenerator
  上記2つのgeneratorの抽象スーパークラス
  名前はいまいちなんですが, 昇順で, 素数集合のスーパーセットになる
  generator ということろからとっています.
  よい名前募集中

* Prime::PrimeSet
  素数生成の本体
  singletonにすることによって, クラス変数をなくしています

* Integer に追加されるメソッド
  実装は, Primeの方に移動

* Prime#prime_division. Prime.prime?
  generator が指定できるようにしてあります. 単発に使うなら豊福さんの方
  が早いと思いますが, キャッシュの効果がでることもあるので, 使い方によっ
  て変えられるようにと言う意図です

んで, コードは以下の感じになっています.

ご意見募集中!!

-- prime.rb
require "singleton"
require "forwardable"

class Integer

  def Integer.from_prime_division(pd)
    Prime.int_from_prime_division(pd)
  end
  
  def prime_division(generator = Prime::Generator23.new)
    Prime.prime_division(self, generator)
  end

  def prime?
    Prime.prime?(self)
  end
end
  
class Prime
  include Singleton
  include Enumerable

  class<<self
    extend Forwardable
    include Enumerable

    def method_added(method)
      #puts "method add: #{method}"
      (class<<self;self;end).def_delegator :instance, method
    end
  end

  def each(&block)
    Generator.new.each(&block)
  end

  def prime?(value, generator = Prime::Generator23.new)
    for num in generator
      return false if value % num == 0
      return true if value > num * num
    end
  end

  def int_from_prime_division(pd)
    pd.inject(1){|value, (prime, index)|
      value *= prime**index
    }
  end

  def prime_division(value, generator= Prime::Generator23.new)
    raise ZeroDivisionError if self == 0
    pv = []
    for prime in generator
      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

  class IncreaseSuperPrimeGenerator
    include Enumerable

    def succ
      raise NotImplementedError, "need to define `succ'"
    end

    def each(&block)
      return self unless block
      loop do
	block.call succ
      end
    end
    
  end
  ISPG = IncreaseSuperPrimeGenerator
  
  class Generator<ISPG
    def initialize
      @index = -1
    end
    
    def succ
      PrimeSet.instance[@index += 1]
    end
    alias next succ
  end

  class Generator23<ISPG
    def initialize
      @prime = 1
      @step = nil
    end
    
    def succ
      loop do
	if (@step)
	  @prime += @step
	  @step = 6 - @step
	else
	  case @prime
	  when 1; @prime = 2
	  when 2; @prime = 3
	  when 3; @prime = 5; @step = 2
	  end
	end
	return @prime
      end

    end
  end

  class PrimeSet
    include Singleton

    def initialize
      # 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
    end

    # Return the prime cache.
    def cache
      return @primes
    end
    alias primes cache
    alias primes_so_far cache

    def [](index)
      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
  end
end





__
---------------------------------------------------->> 石塚 圭樹 <<---
---------------------------------->> e-mail: [e-mail] <<---