Ruby Forum Ruby-dev > Refactoring of enumerating prime numbers

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クラスに
付加するのが自然だと思います。

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

$B$1$$$8$e!w$$$7$D$+$G$9(B.

In [ruby-dev :35863 ] the message: "[ruby-dev:35863] Refactoring of
enumerating prime numbers ", on Aug/16 14:11(JST) "Yugui (Yuki
Sonoda)" writes:

>Yugui$B$G$9!#(B

>mathn.rb$B$K<}O?$5$l$F$$$k(BPrime$B%/%i%9$N;H$$>!<j$,$$$^$$$ANI$/$J$$$N$G2~A1(B
>$B$rDs0F$7$^$9!#D>$7$?$$$N$O(B3$BE@$G$9!#(B
>
>1. mathn.rb$B$KF~$C$F$$$k(B
>2. $B%$%s%9%?%s%9$r@8@.$9$kI,MW$,$"$k(B
>3. $B$=$b$=$bFH<+$N%/%i%9$,I,MW$+(B?

$B%$%s%?!<%U%'!<%9$NB&LL(B, $B5!G=$NB&LL(B, 
$B<B8=$NB&LL$+$i8+$F$_$?$$$H;W$$$^$9(B.


$B$^$:(B, $B%$%s%?!<%U%'!<%9>e$NB&LL$+$i(B.

>== mathn.rb$B$KF~$C$F$$$k(B
>$BAG?tNs5s$O@0?t$KJD$8$?7W;;$G$bI,MW$K$J$k$b$N$J$N$G!"(Bmathn.rb$B$,$b$?$i$9(B
>  int / int => rational
>$B$O4r$7$/$J$$$3$H$,$"$j$^$9!#(B

$BJ,$+$i$J$$$3$H$O$J$$$G$9(B.

$B$?$@(B, $B$=$b$=$b(B, Prime $B$O(B $B85!9(B, 
$BAG0x?tJ,2r$N$?$a$K(B mathn.rb $B$KF~$C$F$$(B
$B$k$b$N$G(B, mathn.rb 
$B$KF1:-$5$l$F$$$k$+$i$3$=I8=`E:IU$K$J$l$?$b$N$G(B, $B$=(B
$B$lC1FH$GI8=`E:IU$K$J$l$?$+$I$&$+(B? $B$?$V$s(B, 
$B$J$l$J$+$C$?$G$7$g$&(B.

>$B$G$9$+$i!"AG?t$rNs5s$9$k5!G=$O(Bmathn.rb$B$K4^$^$l$F$$$k$Y$-$G$O$"$j$^$;$s!#(B
>$BE:IU$N%Q%C%A$G$O2>$K(Blib/math/prime.rb$B$H$$$&%U%!%$%k$KDI$$=P$7$F$_$^$7(B
>$B$?!#(B

$B$=$N$"$?$j$,(B, lib/prime.rb $B$G$J$/(B lib/math/prime.rb 
$B$H$$$&1sN8$K$J$C$F(B
$B$$$k$h$&$J5$$,$7$^$9(B.

$B$$$^$5$i(B, 
$BJ,$1$?$iI8=`E:IU$+$i$O$:$;$H$b$$$o$l$J$$$H;W$$$^$9$N$G(B, $B>l=j(B
($B%U%!%$%kL>(B)$B$O$H$b$+$/J,$1$F$b$h$$$H;W$$$^$9(B.


>== $B%$%s%9%?%s%9$r@8@.$9$k(B
>$BAG?tNs5s5!G=$O8=:_$O<!$N$h$&$K$7$F;H$&I,MW$,$"$j$^$9!#(B
> Prime.new.each do |prime|
>   # do something
> end
>$BMW$9$k$K!"(BPrime$B%*%V%8%'%/%H$OAG?tNs5s$KBP$9$k30It%$%F%l!<%?$G$9!#(B
>$B$3$l$O>/$74qL/$K;W$($^$9!#(B

$BA4A34qL/$G$b$J$$$H;W$$$^$9$,(B? $B35G0E*$K$O(B, 
Prime$B%$%s%9%?%s%9$,AG?t$N=8(B
$B9g$rI=$7$F$$$k$H9M$($F$$$k$+$i$G$9(B. 
$B$=$NAG?t=89g$+$i?t$(>e$2$F$$$k$H9M(B
$B$($F$$$k$N$G$3$N$h$&$J%$%s%?!<%U%'!<%9$K$J$C$F$$$^$9(B.

>$B<!$N$h$&$K=q$-$?$$$G$9!#(B
> Prime.each do |prime|
>   # do something
> end

$B$=$l$O(B, $B%$%s%?!<%U%'!<%9>e$NLdBj$G(B, 
$BMxJX@-$+$i$=$$$&$b$N$,$"$C$F$b$h$$(B
$B5$$,$7$^$9$,(B.

for prime in Prime
  # ...
end

$B$C$F=q$/$H$*$+$7$$5$$,$9$k$N$G(B, 
$B$"$/$^$G$b$=$N$h$&$J%$%s%?!<%U%'%$%9$b(B
$BMQ0U$9$k$N$,$h$$$H;W$$$^$9(B.


>== $B$=$b$=$bFH<+$N%/%i%9$,I,MW$+(B
>$B$3$&$J$k$H!"(BPrime$B$H$$$&FH<+$N%/%i%9$,I,MW$+$I$&$+$,5?Ld$K$J$C$F$-$^$9!#(B
> Integer.each_prime do |prime|
>   # do something
> end
>
>$B$G$h$$$N$G$O$J$$$G$7$g$&$+!#(BPrime$B$H$$$&JL8D$N%/%i%9$,MQ0U$5$l$F$$$?$N$O(B
>$B30It%$%F%l!<%?$rDs6!$9$k$?$a$K%$%s%9%?%s%9$r@8@.$9$kI,MW$,$"$C$?$N$@$H;W(B
>$B$o$l$^$9!#(BEnumerator$B$,AH$_9~$_$K$J$C$?:#!"AG?tNs5s5!G=$O(BInteger$B%/%i%9$K(B
>$BIU2C$9$k$N$,<+A3$@$H;W$$$^$9!#(B

> Integer.each_prime do |prime|

$B$,%$%s%?!<%U%'%$%9>eM_$7$$$C$F$N$rH]Dj$9$k$D$b$j$O$J$$$G$9(B. 
$B@Q6KE*$K9N(B
$BDj$9$kMh$b$J$$$G$9$,(B.

$B<!$K(B, $B5!G=E*B&LL$+$i(B.

Enumerator$B$H30It%$%F%l!<%?$H$7$F$N(BPrime$B%$%s%9%?%s%9$G$9$,(B, 
Enumerator
$B$O%9%l%C%I$N6-3&$r1[$($i$l$J$$$H$$$&@)Ls$,$"$j$^$9$N$G(B, 
$B$=$N$h$&$J@)Ls(B
$B$N$J$$(BPrime$B$+$i$o$6$o$6%@%&%0%l!<%I$9$kI,MW$O$J$$$G$9(B.

$B<!$K(B, $B<BAuE*B&LL$+$i(B, Yugui$B$5$s$N<BAu$O$G$O(B, 
Integer$B$N%/%i%9JQ?t$H$7$F(B

  @@primes
  @@next_to_check
  @@ulticheck_index
  @@ulticheck_next_squared

$B$H$&$,(B, $BF3F~$5$l$F$$$^$9$,(B, 
$B$3$l$O$H$F$b5v$;$J$$$G$9$M(B. Integer$B$N%/%i(B
$B%9JQ?t$H$7$F$O$U$5$o$7$/$J$$$H;W$$$^$9(B.

> $B:#$O(BEnumerable::Enumerator$B$,$"$k$N$G$9$+$i!"30It%$%F%l!<%?@8@.$N$?$a$@$1(B
> $B$K4qL/$J?6$kIq$$$r$5$;$kI,MW$O$"$j$^$;$s!#$^$?!"(BRuby$B%i%$%V%i%j$H$7$F$OFb(B
> $BIt%$%F%l!<%?$r$^$:Ds6!$9$k$N$,$h$j<+A3$G$O$J$$$G$7$g$&$+!#(B

$B$H$"$j$^$9$,(B,

$B8=9T$N(BPrime$B$+$iFbIt%$%F%l!<%?$r<B8=$9$kJ}K!$H(BYugui$B$5$s$NFbIt%$%F%l!<%?(B
$B$+$i(BEnumertor$B$rMxMQ$9$kJ}K!$H$I$A$i$,<+A3$+$H$$$($P(B, 
$B30It%$%F%l!<%?$r(B
$B<B8=$9$k$?$a$K(BFiber$B$rMQ$$$F$$$kJ}$,$h$C$]$IIT<+A3$@$H;W$$$^$9(B. 
$B5mEa$C(B
$B$F46$8$,$7$^$9(B. $B$5$i$K(B, 
$B>e5-$G=R$Y$?$h$&$K5!G=E*$KNt$k$b$N$KCV$-49$($k(B
$BM}M3$O$J$$$H9M$($^$9(B.

$B;d$N7kO@$H$7$F$O(B:

* mathn.rb $B$+$i(B $BJ,N%FHN)$5$;$k(B => $B;?@.(B
* Prime.each $B$NF3F~(B => $B;?@.(B

* Integer.each_prime $B$NF3F~(B => $BI,MW@-$O$"$^$j46$8$J$$(B

* $B<BAu$K4X$7$F(B => $B8=>u$N$^$^$G$h$$(B.

$B$G$9(B.


__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

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はどうしても欲しいというほどではありませんが、素数
列挙機能があって整数クラスがあるならば、整数クラスに列挙機能が付いていた
方が自然であると感じます。

$B$1$$$8$e!w$$$7$D$+$G$9(B.

In [ruby-dev :35867 ] the message: "[ruby-dev:35867] Re: Refactoring
of enumerating prime numbers ", on Aug/17 23:13(JST) "Yugui (Yuki
Sonoda)" writes:

>Yugui$B$G$9!#(B
>$B$$$7$E$+$5$s!"$"$j$,$H$&$4$6$$$^$9!#(B

$B$$$($$$((B. $B$I$b$G$9(B.

$B$^$:(B, $B:G=i$K(B, $B:#2s$N0F$O$J$+$J$+$9$P$i$7$$$H;W$$$^$9(B. 
$B:#$N<BAu$h$j$b@0(B
$BM}$5$l$F$$$k5$$,$7$^$9(B. $B$?$@$7(B, $B$$$/$D$+%3%a%s%H$,(B:

>$B$=$&$G$9$M!#;d$b(Blib/prime.rb$B$OBg$2$5$9$.$k$H46$8$^$7$?!#>l=j$OB>$KE,Ev$J(B
>$B$b$N$r;W$$$D$+$J$+$C$?$N$G(Blib/math/prime.rb$B$K$7$?$^$G$G$9$,!"J,$1$F$$$?(B
>$B$@$1$k$H=u$+$j$^$9!#(B

$BJ,$1$k$N$O;d$b;?@.$7$^$9$,(B, $BL>A0$,$G$9$M$'(B.


  lib/prime.rb

$B$G$$$$$s$8$c$J$$$+$J$!(B. $B$@$l$+$i$bH?BP$,$J$1$l$P$G$9$,(B(^^;;


>>> == $B%$%s%9%?%s%9$r@8@.$9$k(B

>$BAG?t$NA4BN$N%$%s%9%?%s%9$,J#?tB8:_$7F@$k$N$O$*$+$7$$$G$9!#(B

$B$`!<(B.

>$B@0?t$NA4BN$KBP1~$9$k$b$N$,(BInteger$B$G$"$k$h$&$K!"AG?t$NA4BN$KBP1~$9$k$N(B
>$B$O(BPrime$B$G$"$k$[$&$,<+A3$@$H46$8$^$7$?!#(B

>$B7k6I!"AG?t$NA4BN$r(BRuby$B$K$*$$$F$I$&$d$C$FI=$9$+$H$$$&F1$8$H$3$m$K$D$$$F$N(B
>$B8+2r$NAj0c$K5"7k$9$k$N$G$7$g$&$,!"(B

$B$H$$$&$+$G$9$M(B. $B%/%i%9$O4pK\$H$7$F5-=R;R$G$"$C$F(B, 
$B%$%s%9%?%s%9$G$O$J$$(B
$B$G$9(B. $B$D$^$j(B, 
$BAG?tA4BN$rI=$9$b$N$b%$%s%9%?%s%9$G$"$C$FM_$7$$$G$9(B. Ruby
$B$G$O(B, $B$=$&$H$b0l35$K$$$($J$$$N$G$9$,(B, 
$B>/$J$/$H$b$o$?$7$,4X$o$C$F$$$k$b(B
$B$N$O(B, $B$=$&$"$C$FM_$7$$$G$9(B.

>$BAG?tA4BN$H$$$&$b$N$N(BRuby$BI=8=$,J#?tB8:_$7F@$k$h$&$K$J$C$F$$$k$N$O!"$d$O$j(B
>$B30It%$%F%l!<%?$H$7$F$N5!G=$r4|BT$5$l$F$$$?$,$?$a$G$O$J$$$G$7$g$&$+!#(B

$B$?$7$+$K(B, $B$=$l$O$$$($k$+$bCN$l$J$$$G$9(B.

>$B;d$H$7$F$O!"$=$N5!G=$rH4$1$PAG?tA4BN$OM#0l$G$"$k$Y$-$G$"$k$H9M$($^$9!#(B

$B$H$$$&$3$H$G(B, $B$3$&$$$&$H$-$K$O(B singleton 
$B%Q%?!<%s$rE,MQ$9$k$N$,$U$5$o(B
$B$7$$$H;W$&$N$G$9$,(B, $B$$$+$,$G$7$g$&(B?

$B$=$&$9$l$P(B, $BM#0l@-$bJ]$?$l$D$D(B, 
$B$A$c$s$H%$%s%9%?%s%9$G<B8=$G$-$^$9(B.

>$B$G$"$l$P!"$3$&$$$&$N$O$I$&$G$7$g$&$+!#(B
>
>1. Prime::Generator $B$H$$$&AG?tNs5s$N30It%$%F%l!<%?%/%i%9$r:n@.(B
>  1.1. $B8_49@-$N$?$a!"$^$?FbIt%$%F%l!<%?$NDs6!<T$H$7$F(BPrime$B%/%i%9$r29B8(B
>2. Prime.each $B$O(B Prime::Generator $B%*%V%8%'%/%H$r8F$S=P$7$FNs5s(B
>3. (optional) Integer.each_prime$B$O(BPrime.each$B$KE>Aw(B

$B%=!<%9$r8+$?46$8$J$+$J$+$h$$46$8$G$9(B.

$B$"$H$O(B, $B>e=R$N(B Singleton $B$N0F$bF~$l$F(B, 
$B$$$?$@$1$k$H$&$l$7$$$J$H(B.

$B$G$O(B, $B?70FBT$C$F$$$^$9(B(^^;


__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

$B$J$+$@$G$9!#(B

At Tue, 19 Aug 2008 12:43:04 +0900,
keiju ISHITSUKA wrote in [ruby-dev:35875]:
> >$B;d$H$7$F$O!"$=$N5!G=$rH4$1$PAG?tA4BN$OM#0l$G$"$k$Y$-$G$"$k$H9M$($^$9!#(B
> 
> $B$H$$$&$3$H$G(B, $B$3$&$$$&$H$-$K$O(B singleton $B%Q%?!<%s$rE,MQ$9$k$N$,$U$5$o(B
> $B$7$$$H;W$&$N$G$9$,(B, $B$$$+$,$G$7$g$&(B?
> 
> $B$=$&$9$l$P(B, $BM#0l@-$bJ]$?$l$D$D(B, $B$A$c$s$H%$%s%9%?%s%9$G<B8=$G$-$^$9(B.

Prime.instance.each$B$H$$$&$N$O>iD9$K46$8$^$9!#$I$&$;$J$i$=$N%$%s(B
$B%9%?%s%9<+BN$r(BPrime$B$H$$$&Dj?t$K$7$F$O$I$&$G$7$g$&$+!#(B

> 
> $B$G$O(B, $B?70FBT$C$F$$$^$9(B(^^;

Prime.each$B$rDI2C$9$k$@$1$G$$$$$h$&$J5$$b$7$J$/$O$J$$$G$9!#(B

def Prime.each(&block)
  ps = new
  if block
    ps.each(&block)
  else
    ps
  end
end

$BK-J!$G$9!#(B

on Aug/16 14:11(JST) "Yugui (Yuki Sonoda)" writes:
> mathn.rb$B$K<}O?$5$l$F$$$k(BPrime$B%/%i%9$N;H$$>!<j$,$$$^$$$ANI$/$J$$$N$G2~A1(B
> $B$rDs0F$7$^$9!#D>$7$?$$$N$O(B3$BE@$G$9!#(B

$B$3$N5!2q$K(B
[ruby-dev:30932] Re: Integer#prime_division $B$H(B Prime
[ruby-dev:30937] Re: Integer#prime_division $B$H(B Prime

$B$bF~$l$F$b$i$($^$;$s$+!#(B
---

$B$1$$$8$e!w$$$7$D$+$G$9(B.

In [ruby-dev :35877 ] the message: "[ruby-dev:35877] Re: Refactoring
of enumerating prime numbers ", on Aug/19 15:21(JST) Nobuyoshi Nakada
writes:

>$B$J$+$@$G$9!#(B

>Prime.instance.each$B$H$$$&$N$O>iD9$K46$8$^$9!#$I$&$;$J$i$=$N%$%s(B
>$B%9%?%s%9<+BN$r(BPrime$B$H$$$&Dj?t$K$7$F$O$I$&$G$7$g$&$+!#(B

$B;d$b$=$&$J$N$+$J$!(B? $B$H;W$$$D$D$b(B, $B$G$O(B, 
$B85$N%/%i%9$NL>A0$O$I$&$9$k$s$@(B?
$B$H;W$C$?$j$b$7$F$^$9(B.

>Prime.each$B$rDI2C$9$k$@$1$G$$$$$h$&$J5$$b$7$J$/$O$J$$$G$9!#(B
>
>def Prime.each(&block)
>  ps = new
>  if block
>    ps.each(&block)
>  else
>    ps
>  end
>end

$B$3$l$C$F(B, Yugui $B$5$s$NBh#20F(B:

+class Prime
+  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

$B$H6a$$$G$9$,(B, include Enumerable $B$,F~$C$F$$$^$;$s(B. Enuerable 
$B$G$"$kI,(B
$BMW$O$J$/(B each $B$@$1$"$l$P$h$$$C$F$3$H$G$9(B?

$B$"$H(B, $BJL7o$G5$$K$J$C$F$$$k$3$H$,(B... 
$B8=9T$G$b$=$&$G$9$,(B, $B7k9==EMW$J%/(B
$B%i%9JQ?t$N;H$o$lJ}$r$7$F$$$^$9(B. 
$B$3$l$i$N%/%i%9JQ?t$NAH$r35G0E*$K<h$j$^(B
$B$H$a$?%/%i%9$H$$$&$b$N$b9M$($i$l$=$&$H8@$&5$$,$7$F$$$^$9(B.

$B$^$?(B, $BHyL/$K%9%l%C%I%;!<%U$G$J$$5$$b$7$?$j$b$7$F$$$k$N$G(B, 
$B$=$3$b2r>C$G(B
$B$-$l$P$J$!(B. $B$J$I$H;W$C$?$j$7$F$$$^$9(B


__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

$B$J$+$@$G$9!#(B

At Wed, 20 Aug 2008 11:52:55 +0900,
$B@PDM7=<y(B wrote in [ruby-dev:35882]:
> >Prime.instance.each$B$H$$$&$N$O>iD9$K46$8$^$9!#$I$&$;$J$i$=$N%$%s(B
> >$B%9%?%s%9<+BN$r(BPrime$B$H$$$&Dj?t$K$7$F$O$I$&$G$7$g$&$+!#(B
> 
> $B;d$b$=$&$J$N$+$J$!(B? $B$H;W$$$D$D$b(B, $B$G$O(B, $B85$N%/%i%9$NL>A0$O$I$&$9$k$s$@(B? 
> $B$H;W$C$?$j$b$7$F$^$9(B.

class << (Prime = Object.new); end $B$G!#(B

> >Prime.each$B$rDI2C$9$k$@$1$G$$$$$h$&$J5$$b$7$J$/$O$J$$$G$9!#(B

> $B$3$l$C$F(B, Yugui $B$5$s$NBh#20F(B:
> $B$H6a$$$G$9$,(B, include Enumerable $B$,F~$C$F$$$^$;$s(B. Enuerable $B$G$"$kI,(B
> $BMW$O$J$/(B each $B$@$1$"$l$P$h$$$C$F$3$H$G$9(B? 

Enumerable$B$OF~$lK:$l$G$9$,!"(BGenerator$B$N$h$&$KJL%/%i%9$r2p$9$kI,(B
$BMW$O$J$$$N$G$O$J$$$+$H$$$&$3$H$G$9!#(B

> $B$"$H(B, $BJL7o$G5$$K$J$C$F$$$k$3$H$,(B...  $B8=9T$G$b$=$&$G$9$,(B, $B7k9==EMW$J%/(B
> $B%i%9JQ?t$N;H$o$lJ}$r$7$F$$$^$9(B. $B$3$l$i$N%/%i%9JQ?t$NAH$r35G0E*$K<h$j$^(B
> $B$H$a$?%/%i%9$H$$$&$b$N$b9M$($i$l$=$&$H8@$&5$$,$7$F$$$^$9(B.

$B$=$l$,(BPrime$B<+?H$NLr3d$J$s$8$c$J$$$+$J$!$H!#(B

> $B$^$?(B, $BHyL/$K%9%l%C%I%;!<%U$G$J$$5$$b$7$?$j$b$7$F$$$k$N$G(B, $B$=$3$b2r>C$G(B
> $B$-$l$P$J$!(B. $B$J$I$H;W$C$?$j$7$F$$$^$9(B

$B$=$3$OLdBj$G$9$M!#(BPrime#succ$B$N%k!<%W$r(Bsynchronize$B$5$;$l$P$$$$$G(B
$B$7$g$&$+!#(B

$B$R$H$^$:!"(BPrime$B4X78$rJL%U%!%$%k$K@Z$jJ,$1$k$H$3$m$^$G$d$C$F$7$^$C(B
$B$F$O$I$&$G$7$g$&$+!#(B


Index: lib/mathn.rb
===================================================================
--- lib/mathn.rb  (revision 18717)
+++ lib/mathn.rb  (working copy)
@@ -60,4 +60,5 @@ class Prime
                                    #   n < Math.sqrt(@@next_to_check) 
})
   @@ulticheck_next_squared = 121   # @@primes[@@ulticheck_index + 1] ** 
2
+  @@lock = Mutex.new

   class << self
@@ -82,4 +83,6 @@ class Prime
   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,
@@ -97,4 +100,6 @@ class Prime
       @@next_to_check += 2
     end
+      end
+    end
     return @@primes[@index]
   end

$B$1$$$8$e!w$$$7$D$+$G$9(B.

$B2?$+%a%$%k$,$?$^$C$F$7$^$C$F(B...
$B7h$7$FK:$l$F$$$k$o$1$G$O$"$j$^$;$s$N$G(B, > $BBT$C$F$$$kJ}(B

In [ruby-dev :35878 ] the message: "[ruby-dev:35878] Re: Refactoring
of enumerating prime numbers ", on Aug/19 17:39(JST) TOYOFUKU
Chikanobu writes:

>  $BK-J!$G$9!#(B

$B$4L5:;BA$7$F$$$^$9(B.

>$B$3$N5!2q$K(B
>[ruby-dev:30932] Re: Integer#prime_division $B$H(B Prime
>[ruby-dev:30937] Re: Integer#prime_division $B$H(B Prime
>
>$B$bF~$l$F$b$i$($^$;$s$+!#(B

$B$*!<(B. $B$9$C$+$jK:$l$F$$$^$7$?(B.

$B$7$+$7(B, 
$BAG?tNs$h$j$b5?;wAD?tNs$NJ}$,7W;;$,Aa$$$N$b2?$+2y$7$$5$$b$7$^$9(B
$B$M(B(^^;

$B$G$b(B, $B$3$l$O7k9==EMW$J$3$H$b8@$C$F$$$k5$$,$7$^$9$M(B. 
$BNc$($P(B, $BAG?t$+$I$&(B
$B$+H=Dj$9$k%a%=%C%I$b$3$A$i$NJ}K!$r;H$C$?J}$,$h$$$H8@$C$F$$$^$9$7(B...

__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

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 を足しました。

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

$B$1$$$8$e!w$$$7$D$+$G$9(B.

$B$J$s$+(B, $BAw$C$?%a%$%k$,%9%Q%`07$$$K$J$C$?$h$&$J$N$G(B, 
$B:FAw$7$^$9(B.

yugui$B$5$s$N$H$O0U?^$7$F$$$k$H$3$m$OBgBNF1$8$@$H;W$$$^$9$,(B...

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

>$B$J$+$@$G$9!#(B

>> $B;d$b$=$&$J$N$+$J$!(B? $B$H;W$$$D$D$b(B, $B$G$O(B, $B85$N%/%i%9$NL>A0$O$I$&$9$k$s$@(B? 
>> $B$H;W$C$?$j$b$7$F$^$9(B.
>
>class << (Prime = Object.new); end $B$G!#(B

$B$=$l$b9M$($?$s$G$9$,(B... Generator $B$HMm$_$^$9$N$G(B, 
$B$=$A$i$G(B.

>Enumerable$B$OF~$lK:$l$G$9$,!"(BGenerator$B$N$h$&$KJL%/%i%9$r2p$9$kI,(B
>$BMW$O$J$$$N$G$O$J$$$+$H$$$&$3$H$G$9!#(B

Generator$B$,0l<oN`$J$i$=$l$O8@$($k$H;W$&$N$G$9$,(B, 
$BK-J!$5$s$N%a%$%k$N$h(B
$B$&$K(B,$BC1D4A}2C$G>/$J$/$H$b$9$Y$F$NAG?t$,4^$^$l$k?tNs$rMQ$$$kJ}$,NI$$>l(B
$B9g$b$"$k$N$G(B, Generator $B$O(B 
$BJL$K$"$C$?J}$,$h$$5$$,$7$F$$$^$9(B.

>$B$=$l$,(BPrime$B<+?H$NLr3d$J$s$8$c$J$$$+$J$!$H!#(B

$B;d$,8@$$$?$+$C$?$3$H$H$A$g$C$H$:$l$F$k$+$b(B. 
$B>\$7$/$OE:IU$N%3!<%I$r8+$F(B
$B$$$?$@$-$?$$$N$G$9$,(B, @@class_var 
$B$,B?MQ$5$l$F$$$k$N$,5$$K$/$o$J$$$N$G(B,
$B$=$l$r$J$/$7$?$+$C$?$N$G$9(B.

>> $B$^$?(B, $BHyL/$K%9%l%C%I%;!<%U$G$J$$5$$b$7$?$j$b$7$F$$$k$N$G(B, $B$=$3$b2r>C$G(B
>> $B$-$l$P$J$!(B. $B$J$I$H;W$C$?$j$7$F$$$^$9(B
>$B$=$3$OLdBj$G$9$M!#(BPrime#succ$B$N%k!<%W$r(Bsynchronize$B$5$;$l$P$$$$$G(B
>$B$7$g$&$+!#(B

$B$$$C$F$*$$$F(B, $B2?$J$s$G$9$,(B(^^;; 
ruby$B$N%i%$%V%i%j$O$[$H$s$I$,%9%l%C%I%;!<(B
$B%U$G$J$$$N$G(B, $B5$$K$7$J$/$F$b$h$$5$$K$J$C$F$$$^$9(B.

$B?70F(B:

* Prime$B%/%i%9$O(B singleton.
* Prime$B%/%i%9%a%=%C%I$O%$%s%9%?%s%9%a%=%C%I$K%G%l%2!<%H$9$k(B.

* Prime::Generator
  $BAG?tNs$N(Bgenerator

* Prime::Generator23
  $BK-J!$5$s$N(Bgenerator.
  $BL>A0$NM3Mh(B: 2$B$H(B3$B$NG\?t0J30$N?tCM$J$N$G(B.

* Prime::IncreaseSuperPrimeGenerator
  $B>e5-(B2$B$D$N(Bgenerator$B$NCj>]%9!<%Q!<%/%i%9(B
  $BL>A0$O$$$^$$$A$J$s$G$9$,(B, $B>:=g$G(B, 
$BAG?t=89g$N%9!<%Q!<%;%C%H$K$J$k(B
  generator $B$H$$$&$3$H$m$+$i$H$C$F$$$^$9(B.
  $B$h$$L>A0Jg=8Cf(B

* Prime::PrimeSet
  $BAG?t@8@.$NK\BN(B
  singleton$B$K$9$k$3$H$K$h$C$F(B, $B%/%i%9JQ?t$r$J$/$7$F$$$^$9(B

* Integer $B$KDI2C$5$l$k%a%=%C%I(B
  $B<BAu$O(B, Prime$B$NJ}$K0\F0(B

* Prime#prime_division. Prime.prime?
  generator $B$,;XDj$G$-$k$h$&$K$7$F$"$j$^$9(B. 
$BC1H/$K;H$&$J$iK-J!$5$s$NJ}(B
  $B$,Aa$$$H;W$$$^$9$,(B, $B%-%c%C%7%e$N8z2L$,$G$k$3$H$b$"$k$N$G(B, 
$B;H$$J}$K$h$C(B
  $B$FJQ$($i$l$k$h$&$K$H8@$&0U?^$G$9(B

$B$s$G(B, $B%3!<%I$O0J2<$N46$8$K$J$C$F$$$^$9(B.

$B$40U8+Jg=8Cf(B!!

-- 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





__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

Yuguiです。

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

私が送ったコードも既存のPrime.newしているコードに配慮してはいますが、
互換性をより確実に提供するという意味ではPrimeがクラスで有り続けたほうが
良いかもしれません。

ただ、その意味では石塚さんの、Primeを完全にシングルトンパターンにしてし
まうのはPrime.newできないので困ると思います。



もう一度整理します。
1. 素数全体を表すEnumerableなオブジェクトは唯一であるべき(yugui)
   互換性のためにPrime.newできるのは仕方がないが、非推奨としたい
 => Primeを特異クラスを持つオブジェクトか、singletonパターン的なクラスに

2. 素数全体を表すものはインスタンスであるべき(石塚さん)
 => Primeがクラスというのはまずい。
    Primeへのメソッド呼び出しをPrimeのインスタンスへ委譲するならばありえる。

3. 素数列挙の途中の状態を保持する外部イテレータが必要
4. 疑似素数列を生成するGeneratorもほしい
   => Prime::Generator, Prime::Generator23, Prime::EratosthenesGenerator


Prime::*の定数スコープを提供するためにもPrimeは、私が書いたような
singletonなオブジェクトよりは、石塚さんのようなsingletonパターンのほうが
良さそうに思えます。

ただし、互換性のためにPrime.newも許容するようにしてみました。このバー
ジョンのprime.rbを添付します。

この他、
a) エラトステネスのふるいでGeneratorを書いてみたらとても速くなったので、
Prime::EratosthenesGeneratorを加えてあります。

      user     system      total        real
trial division
 17.060000  22.580000  39.640000 ( 39.556764)
eratosthenes
  2.270000   0.010000   2.280000 (  2.277945)


b) Prime.eachが上界をとるようにしてみました。そこに到達したら列挙を打ち
切ります。
c) Prime.eachの第2引数にgeneratorを指定できるようにしてみました。

d) Prime.eachとPrime.each.eachが同じオブジェクトであるために列挙状態を共
有してしまいます。generatorがselfではなくself.dupを返すようにしました。

e) Enumeratorに合わせて、Generatorにwith_indexとnextとrewindを足しました。


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

確かにこの名前には違和感がありますね。

PseudoPrimeGeneratorあたりではどうでしょうか。Generator23みたいに「疑
似」の精度が悪くても、逆に真にprimeであってもPseudoのサブセットにはなる
と思います。

$B$1$$$8$e!w$$$7$D$+$G$9(B.

In [ruby-dev :35983 ] the message: "[ruby-dev:35983] Re: Refactoring
of enumerating prime numbers ", on Aug/26 22:09(JST) "Yugui (Yuki
Sonoda)" writes:

>Yugui$B$G$9!#(B

$BCY%a%$%k$G$9$$$^$;$s(B.

>$B;d$,Aw$C$?%3!<%I$b4{B8$N(BPrime.new$B$7$F$$$k%3!<%I$KG[N8$7$F$O$$$^$9$,!"(B
>$B8_49@-$r$h$j3N<B$KDs6!$9$k$H$$$&0UL#$G$O(BPrime$B$,%/%i%9$GM-$jB3$1$?$[$&$,(B
>$BNI$$$+$b$7$l$^$;$s!#(B

$B$"$H$+$i$G$F$-$^$9$,(B, Generator$B$r30$+$i8F$Y$J$/$J$j$^$9$7$M(B.

>$B$?$@!"$=$N0UL#$G$O@PDM$5$s$N!"(BPrime$B$r40A4$K%7%s%0%k%H%s%Q%?!<%s$K$7$F$7(B
>$B$^$&$N$O(BPrime.new$B$G$-$J$$$N$G:$$k$H;W$$$^$9!#(B

$B$^$"(B, 1.9$BMQ$@$+$iNI$$$+$H;W$C$F(B(^^;;


>4. $B5?;wAG?tNs$r@8@.$9$k(BGenerator$B$b$[$7$$(B
>   => Prime::Generator, Prime::Generator23, Prime::EratosthenesGenerator

$B$O$$(B.

>Prime::*$B$NDj?t%9%3!<%W$rDs6!$9$k$?$a$K$b(BPrime$B$O!";d$,=q$$$?$h$&$J(B
>singleton$B$J%*%V%8%'%/%H$h$j$O!"@PDM$5$s$N$h$&$J(Bsingleton$B%Q%?!<%s$N$[$&$,(B
>$BNI$5$=$&$K;W$($^$9!#(B

$B$G$9$M(B.

>$B$?$@$7!"8_49@-$N$?$a$K(BPrime.new$B$b5vMF$9$k$h$&$K$7$F$_$^$7$?!#$3$N%P!<(B
>$B%8%g%s$N(Bprime.rb$B$rE:IU$7$^$9!#(B

$B$3$l$G(B, $B$$$$$s$8$c$J$$$G$7$g$&$+(B.

>$B$3$NB>!"(B
>a) $B%(%i%H%9%F%M%9$N$U$k$$$G(BGenerator$B$r=q$$$F$_$?$i$H$F$bB.$/$J$C$?$N$G!"(B
>Prime::EratosthenesGenerator$B$r2C$($F$"$j$^$9!#(B
>
>      user     system      total        real
>trial division
> 17.060000  22.580000  39.640000 ( 39.556764)
>eratosthenes
>  2.270000   0.010000   2.280000 (  2.277945)

$B$*!<(B.

(2**19-1)**2 $B$NAG0x?tJ,2r$G$b(B:

Generator23  0.450000   0.000000   0.450000 (  0.468806)
Generator  3.680000   0.430000   4.110000 (  4.145663)
Eratos  0.620000   0.000000   0.620000 (  0.635689)

$B$1$C$3$&NI$$CM$,$G$F$$$^$9(B.

$B5$$K$J$k$N$,$I$N$/$i$$%a%b%j$r>CHq$9$k$+$G$9(B. n 
$B0J2<$N$NAG?t$G9M$($k$H(B:

Generator: $BLs(B n/lon(n) * 4 byte
Eratos:       n/32 byte

$B$K$J$j$^$9(B. $B%*!<%@!<$O(BGenerator$B$NJ}$,NI$$$G$9(B. 
$B$?$@(B, $B:G=i$N$&$A$O(B
Eratos $B$NJ}$,6u4V8zN($ONI$$$G$9(B, 
Generator$B$NJ}$,%a%b%j$r;H$o$J$/$J$k(B n
$B$r5a$a$k$H(B

  n = 3.8*10**55

$B$H$J$j$^$9(B. $B$=$N;~$N;HMQ%P%$%H?t$O(B 10**54 
byte$B$0$i$$$K$J$j$^$9(B. $B$=$s$J(B
$B$K%a%b%j$J$$$N$G(B, $B8=<BE*$JHO0O$G$O(B 
Eratos$B$NJ}$,6u4V;HMQNL$O>/$J$$$H$$(B
$B$($^$9(B.

# $B8!;;5a$`(B(^^;

$B$H$$$&$3$H$G(B, Prime#each $B$N(B $B%G%U%)%k%H$N(B Generator 
$B$r(B
EratosthenesGenerator $B$K$7$^$7$g$&(B.

$B$"$H(B,

  Generator $B$r(B TrialDivisionGenerator
  PrimeSet $B$r(B TrialDivision

$B$K2~L>$7$^$7$g$&$+(B? $B$=$l$H(B, $B7G:\=gHV$r(B Eratosthenes* 
$B$r@h$K$7$^$7$g$&(B
$B$+(B?

>b) Prime.each$B$,>e3&$r$H$k$h$&$K$7$F$_$^$7$?!#$=$3$KE~C#$7$?$iNs5s$rBG(B
>$B$A@Z$j$^$9!#(B

$B$?$7$+$K$M(B. $B$"$C$?J}$,NI$$$+$b(B.

>c) Prime.each$B$NBh(B2$B0z?t$K(Bgenerator$B$r;XDj$G$-$k$h$&$K$7$F$_$^$7$?!#(B

>d) Prime.each$B$H(BPrime.each.each$B$,F1$8%*%V%8%'%/%H$G$"$k$?$a$KNs5s>uBV$r6&(B
>$BM-$7$F$7$^$$$^$9!#(Bgenerator$B$,(Bself$B$G$O$J$/(Bself.dup$B$rJV$9$h$&$K$7$^$7$?!#(B

$B$*!<(B. $B5$$,IU$-$^$;$s$G$7$?(B.

>e) Enumerator$B$K9g$o$;$F!"(BGenerator$B$K(Bwith_index$B$H(Bnext$B$H(Brewind$B$rB-$7$^(B
>$B$7$?!#(B

$BN;2r(B

>> * Prime::IncreaseSuperPrimeGenerator
>$B3N$+$K$3$NL>A0$K$O0cOB46$,$"$j$^$9$M!#(B
>
>PseudoPrimeGenerator$B$"$?$j$G$O$I$&$G$7$g$&$+!#(BGenerator23$B$_$?$$$K!V5?(B
>$B;w!W$N@:EY$,0-$/$F$b!"5U$K??$K(Bprime$B$G$"$C$F$b(BPseudo$B$N%5%V%;%C%H$K$O$J$k(B
>$B$H;W$$$^$9!#(B

$B$=$&$7$^$7$g$&(B.

$B2?%+=j$+JQ998D=j$,$"$j$^$7$?$,(B, $B$$$+$,$G$7$g$&(B?

$B$b$7(B, $BLdBj$J$$$h$&$G$"$l$P(B, $B$9$$$^$;$s$,(B, 
$B$=$l$rJQ99$7$F(Bcomit $B$7$F$$$?(B
$B$@$1$J$$$G$9(B?


__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

Yuguiです。


keiju ISHITSUKA さんは書きました:
> 何カ所か変更個所がありましたが, いかがでしょう? 
> 
> もし, 問題ないようであれば, すいませんが, それを変更してcomit していた
> だけないです?

ありがとうございます。コミットしようかと思いましたがテストを書いていたら
2点問題に気づきました。結果としてちょっと変更が必要になりそうですので、
恐れ入りますが再度確認をお願いします。

先にお送りしたprime.rbでは2点問題がありました。
1. Prime.eachが返すenumerator(実際にはgenerator)が、uboundを記憶しない。
   Prime.each(100){|p| }は停止するのに、Prime.each(100).each{|p| }は停止
しないという奇妙な結果になります。

2. Prime#nextがない。
  互換性にこだわって見せた割にうっかりPrime#nextの実装を書き忘れていました。
  また、先のバージョンを元に単純にPrime#nextを実装するとPrime#nextによっ
て進んだ内部ポインタとPrime#eachが同期しません。Prime#eachは先立つ
Prime#nextに関わらず2から列挙を開始してしまいます。
  一方、Prime::eachやPrime::instance.eachのほうは先立つPrimeのインスタン
スメソッド呼び出しには影響されずに2から列挙することを期待されると思います。


この2点の問題は解決できましたが、generatorのライフサイクルが少々変わりま
した。新しいprime.rbを添付します。これで差し支えないようでしたらPrimeを
削除したバージョンのmathn.rbと併せてコミットしようと思います。いかがで
しょうか?

$BK-J!$G$9!#(B

In [ruby-dev :36067]
> $B?7$7$$(Bprime.rb$B$rE:IU$7$^$9!#(B

[ruby-dev:30937] Re: Integer#prime_division $B$H(B Prime
$B$K=q$$$?$5$5$d$+$J:GE,2=$r<h$j9~$s$G$b$i$($?$i$H;W$$$^$9!#(B
divmod $B$H(B % $B$N7W;;%3%9%H$O$[$\F1$8$G$9$h$M!#(B

--- prime.rb.org
+++ prime.rb
@@ -87,8 +87,9 @@
   # +generator+:: optional. A pseudo-prime generator.
   def prime?(value, generator = Prime::Generator23.new)
     for num in generator
-      return true if value < num * num
-      return false if value % num == 0
+      q,r = divmod value num
+      return false if r == 0
+      return true if q <= num
     end
   end

@@ -135,7 +136,7 @@
       if count != 0
        pv.push [prime, count]
       end
-      break if prime * prime  >= value
+      break if value1 <= prime
     end
     if value > 1
       pv.push [value, 1]

---

$BK-J!$G$9!#(B

> +      q,r = divmod value num

  $B$9$$$^$;$s!#(B
q,r = value.divmod num

$B$G$9$M!#(BHaskell$BJJ$,!&!&!&(B orz
---

Yugui$B$G$9!#(B

TOYOFUKU Chikanobu $B$5$s$O=q$-$^$7$?(B:
> -      return true if value < num * num
> -      return false if value % num == 0
> +      q,r = divmod value num
> +      return false if r == 0
> +      return true if q <= num
>      end
>    end


$B$3$l$@$H(B2$B$,AG?t$K$J$i$J$$$G$9!#99$K(B
-      return false if r == 0
       return true if q <= num
+      return false if r == 0
$B$+$J!#(B

Yugui (Yuki Sonoda) $B$5$s$O=q$-$^$7$?(B:
> $B$3$l$@$H(B2$B$,AG?t$K$J$i$J$$$G$9!#99$K(B
> -      return false if r == 0
>        return true if q <= num
> +      return false if r == 0

$B$*$C$H!#(B
-      return false if r == 0
-      return true if q <= num
       return true if q < num
+      return false if r == 0

$B$G$7$?!#(B

$B$1$$$8$e!w$$$7$D$+$G$9(B.

In [ruby-dev :36067 ] the message: "[ruby-dev:36067] Re: Refactoring
of enumerating prime numbers ", on Sep/01 00:07(JST) "Yugui (Yuki
Sonoda)" writes:

>Yugui$B$G$9!#(B

$B$I$b$G$9(B.

>$B$"$j$,$H$&$4$6$$$^$9!#%3%_%C%H$7$h$&$+$H;W$$$^$7$?$,%F%9%H$r=q$$$F$$$?$i(B
>2$BE@LdBj$K5$$E$-$^$7$?!#7k2L$H$7$F$A$g$C$HJQ99$,I,MW$K$J$j$=$&$G$9$N$G!"(B
>$B62$lF~$j$^$9$,:FEY3NG'$r$*4j$$$7$^$9!#(B

$B$O$$(B.

>$B@h$K$*Aw$j$7$?(Bprime.rb$B$G$O(B2$BE@LdBj$,$"$j$^$7$?!#(B
>1. Prime.each$B$,JV$9(Benumerator($B<B:]$K$O(Bgenerator)$B$,!"(Bubound$B$r5-21$7$J$$!#(B
>   Prime.each(100){|p| }$B$ODd;_$9$k$N$K!"(BPrime.each(100).each{|p| }$B$ODd;_(B
>$B$7$J$$$H$$$&4qL/$J7k2L$K$J$j$^$9!#(B

$B$3$l$O(B, $B$^$:$$$G$9$M(B.

>2. Prime#next$B$,$J$$!#(B
>  $B8_49@-$K$3$@$o$C$F8+$;$?3d$K$&$C$+$j(BPrime#next$B$N<BAu$r=q$-K:$l$F$$$^$7$?!#(B
>  $B$^$?!"@h$N%P!<%8%g%s$r85$KC1=c$K(BPrime#next$B$r<BAu$9$k$H(BPrime#next$B$K$h$C(B
>$B$F?J$s$@FbIt%]%$%s%?$H(BPrime#each$B$,F14|$7$^$;$s!#(BPrime#each$B$O@hN)$D(B
>Prime#next$B$K4X$o$i$:(B2$B$+$iNs5s$r3+;O$7$F$7$^$$$^$9!#(B
>  $B0lJ}!"(BPrime::each$B$d(BPrime::instance.each$B$N$[$&$O@hN)$D(BPrime$B$N%$%s%9%?%s(B
>$B%9%a%=%C%I8F$S=P$7$K$O1F6A$5$l$:$K(B2$B$+$iNs5s$9$k$3$H$r4|BT$5$l$k$H;W$$(B
>$B$^$9!#(B

$B$&!<$s(B.  $B8@$o$l$F$$$k$3$H$OJ,$+$j$^$9$,(B, 
each$B$H$+%3!<%I$,Hs>o$K$o$+$j(B
$B$:$i$$$G$9$M$'(B(^^;;

$B$A$J$_$K3NG'$G$9$,(B, $B?7HG$NJ}$O(B, Prime.succ 
$B$OEvA3I,MW$J$$$o$1$G$9$M(B?
$B8E$$HG$G$O(B, Prime#each$B$O(Bunboound, 
generator$B$N;XDj$H$+$$$i$J$$$G$9$h$M(B?

$B$J$i(B, $B$3$s$J$N$O$$$+$,$G$9(B?
$B$3$l$J$i(B, 
$B@N$N%3%s%Q%A%S%j%F%#$,I,MW$J$/$J$l$P$9$0:o=|$G$-$^$9(B.

$B$h$1$l$P(B,

  OldCompatibility

$B$r(B Prime$B%/%i%9$N:G8e$K$b$C$F$$$C$F$$$?$@(B, 
$BK-J!$5$s$N$rH?1G$7$F%3%_%C%H(B
$B$7$F$$$?$@$1$l$P$H;W$$$^$9(B.


--- prime.rb  2008-09-03 11:01:29.000000000 +0900
+++ prime2.rb  2008-09-03 20:41:10.000000000 +0900
@@ -41,9 +41,6 @@
 class Prime
   include Enumerable

-  def initialize # :nodoc:
-    @generator = nil
-  end
   @the_instance = Prime.new

   # obsolete.
@@ -51,13 +48,22 @@
   # Use +Prime::instance+ or class methods of +Prime+.
   def initialize
     @generator = EratosthenesGenerator.new
+    extend OldCompatibility
     warn "Prime::new is obsolete. use Prime::instance or class methods 
of Prime."
   end

-  def succ
-    @generator.succ
+  module OldCompatibility
+    def succ
+      @generator.succ
+    end
+    alias next succ
+
+    def each(&block)
+      loop do
+  yield succ
+      end
+    end
   end
-  alias next succ

   class<<self
     extend Forwardable
@@ -71,16 +77,11 @@
   end

   # iterates the given block over all prime numbers.
-  def each(ubound = nil, generator = nil, &block)
-    generator ||= (@generator || EratosthenesGenerator.new)
-    orig_ubound = generator.upper_bound
+  def each(ubound = nil, generator = EratosthenesGenerator.new, &block)
     generator.upper_bound = ubound
     generator.each(&block)
-  ensure
-    generator.upper_bound = orig_ubound
   end

-
   # returns true if +value+ is prime, false for a composite.
   #
   # +value+:: an arbitrary integer.

__
---------------------------------------------------->> $B@PDM(B 
$B7=<y(B <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---

Yugui$B$G$9!#(B

keiju ISHITSUKA $B$5$s$O=q$-$^$7$?(B:
> 
>   OldCompatibility

$B$3$l$ONI$$$G$9$M!#(B 
$BK-J!$5$s$N$rJ;$;$F!"$9$Y$F%3%_%C%H$7$^$7$?!#(B