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クラスに
ä»˜åŠ ã™ã‚‹ã®ãŒè‡ªç„¶ã ã¨æ€ã„ã¾ã™ã€‚

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

e$B$1$$$8$e!w$$$7$D$+$G$9e(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:

Yuguie$B$G$9!#e(B

mathn.rbe$B$K<}O?$5$l$F$$$ke(BPrimee$B%/%i%9$N;H$$>!<j$,$$$^$$$ANI$/$J$$$N$G2~A1e(B
e$B$rDs0F$7$^$9!#D>$7$?$$$N$Oe([email protected]$G$9!#e(B

  1. mathn.rbe$B$KF~$C$F$$$ke(B
  2. e$B%$%s%9%?%s%[email protected]@.$9$kI,MW$,$"$ke(B
  3. e$B$=$b$=$bFH<+$N%/%i%9$,I,MW$+e(B?

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

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

== mathn.rbe$B$KF~$C$F$$$ke(B
[email protected]?t$KJD$8$?7W;;$G$bI,MW$K$J$k$b$N$J$N$G!“e(Bmathn.rbe$B$,$b$?$i$9e(B
int / int => rational
e$B$O4r$7$/$J$$$3$H$,$”$j$^$9!#e(B

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

[email protected](B, e$B$=$b$=$be(B, Prime e$B$Oe(B e$B85!9e(B,
e$BAG0x?tJ,2r$N$?$a$Ke(B mathn.rb e$B$KF~$C$F$$e(B
e$B$k$b$N$Ge(B, mathn.rb
e$B$KF1:-$5$l$F$$$k$+$i$3$=I8=E:IU$K$J$l$?$b$N$Ge(B, e$B$=e(B e$B$lC1FH$GI8=E:IU$K$J$l$?$+$I$&$+e(B? e$B$?$V$se(B,
e$B$J$l$J$+$C$?$G$7$g$&e(B.

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

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

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

== e$B%$%s%9%?%s%[email protected]@.$9$ke(B
e$BAG?tNs5s5!G=$O8=:_$O<!$N$h$&$K$7$F;H$&I,MW$,$"$j$^$9!#e(B
Prime.new.each do |prime|

do something

end
e$BMW$9$k$K!"e(BPrimee$B%*%V%8%’%/%H$OAG?tNs5s$KBP$9$k30It%$%F%l!<%?$G$9!#e(B
e$B$3$l$O>/$74qL/$K;W$($^$9!#e(B

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

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

do something

end

e$B$=$l$Oe(B, e$B%$%s%?!<%U%’!<%9>e$NLdBj$Ge(B,
[email protected]$+$i$=$$$&$b$N$,$"$C$F$b$h$$e(B
e$B5$$,$7$^$9$,e(B.

for prime in Prime

end

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

== e$B$=$b$=$bFH<+$N%/%i%9$,I,MW$+e(B
e$B$3$&$J$k$H!"e(BPrimee$B$H$$$&FH<+$N%/%i%9$,I,MW$+$I$&$+$,5?Ld$K$J$C$F$-$^$9!#e(B
Integer.each_prime do |prime|

do something

end

e$B$G$h$$$N$G$O$J$$$G$7$g$&$+!#e(BPrimee$B$H$$$&JL8D$N%/%i%9$,MQ0U$5$l$F$$$?$N$Oe(B
e$B30It%$%F%l!<%?$rDs6!$9$k$?$a$K%$%s%9%?%s%[email protected]@.$9$kI,MW$,$"[email protected]$H;We(B
e$B$o$l$^$9!#e(BEnumeratore$B$,AH$9~$$K$J$C$?:#!"AG?tNs5s5!G=$Oe(BIntegere$B%/%i%9$Ke(B
e$BIU2C$9$k$N$,<[email protected]$H;W$$$^$9!#e(B

Integer.each_prime do |prime|

e$B$,%$%s%?!<%U%’%$%9>eM_$7$$$C$F$N$rH]Dj$9$k$D$b$j$O$J$$$G$9e(B.
[email protected]*$K9Ne(B
e$BDj$9$kMh$b$J$$$G$9$,e(B.

e$B<!$Ke(B, e$B5!G=E*B&LL$+$ie(B.

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

e$B<!$Ke(B, e$B<BAuE*B&LL$+$ie(B, Yuguie$B$5$s$N<BAu$O$G$Oe(B,
Integere$B$N%/%i%9JQ?t$H$7$Fe(B

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

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

e$B:#$Oe(BEnumerable::Enumeratore$B$,$"$k$N$G$9$+$i!“30It%$%F%l!<%?@8@[email protected]$1e(B
e$B$K4qL/$J?6$kIq$$$r$5$;$kI,MW$O$”$j$^$;$s!#$^$?!"e(BRubye$B%i%$%V%i%j$H$7$F$OFbe(B
e$BIt%$%F%l!<%?$r$^$:Ds6!$9$k$N$,$h$j<+A3$G$O$J$$$G$7$g$&$+!#e(B

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

e$B8=9T$Ne(BPrimee$B$+$iFbIt%$%F%l!<%?$r<B8=$9$kJ}K!$He(BYuguie$B$5$s$NFbIt%$%F%l!<%?e(B
e$B$+$ie(BEnumertore$B$rMxMQ$9$kJ}K!$H$I$A$i$,<+A3$+$H$$$($Pe(B,
e$B30It%$%F%l!<%?$re(B
e$B<B8=$9$k$?$a$Ke(BFibere$B$rMQ$$$F$$$kJ}$,$h$C$]$IIT<[email protected]$H;W$$$^$9e(B.
e$B5mEa$Ce(B
e$B$F46$8$,$7$^$9e(B. e$B$5$i$Ke(B,
e$B>e5-$G=R$Y$?$h$&$K5!G=E*$KNt$k$b$N$KCV$-49$($ke(B
e$BM}M3$O$J$$$H9M$($^$9e(B.

e$B;[email protected]$H$7$F$Oe(B:

e$B$G$9e(B.

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

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ã¯ã©ã†ã—ã¦ã‚‚æ¬²ã—ã„ã¨ã„ã†ã»ã©ã§ã¯ã‚ã‚Šã¾ã›ã‚“ãŒã€ç´ æ•°
    列挙機能があって整数クラスがあるならば、整数クラスに列挙機能が付いていた
    方が自然であると感じます。

e$B$1$$$8$e!w$$$7$D$+$G$9e(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:

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

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

e$B$^$:e(B, e$B:G=i$Ke(B, e$B:#2s$N0F$O$J$+$J$+$9$P$i$7$$$H;W$$$^$9e(B.
e$B:#$N<[email protected](B
e$BM}$5$l$F$$$k5$$,$7$^$9e(B. [email protected]$7e(B, e$B$$$/$D$+%3%a%s%H$,e(B:

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

e$BJ,$1$k$N$O;d$b;[email protected]$7$^$9$,e(B, e$BL>A0$,$G$9$M$'e(B.

lib/prime.rb

e$B$G$$$$$s$8$c$J$$$+$J$!e(B. [email protected]$l$+$i$bH?BP$,$J$1$l$P$G$9$,e(B(^^;;

== e$B%$%s%9%?%s%[email protected]@.$9$ke(B

e$BAG?t$NA4BN$N%$%s%9%?%s%9$,J#?tB8:[email protected]$k$N$O$*$+$7$$$G$9!#e(B

e$B$`!<e(B.

[email protected]?t$NA4BN$KBP1~$9$k$b$N$,e(BIntegere$B$G$"$k$h$&$K!“AG?t$NA4BN$KBP1~$9$k$Ne(B
e$B$Oe(BPrimee$B$G$”$k$[$&$,<[email protected]$H46$8$^$7$?!#e(B

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

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

e$BAG?tA4BN$H$$$&$b$N$Ne(BRubye$BI=8=$,J#?tB8:[email protected]$k$h$&$K$J$C$F$$$k$N$O!"$d$O$je(B
e$B30It%$%F%l!<%?$H$7$F$N5!G=$r4|BT$5$l$F$$$?$,$?$a$G$O$J$$$G$7$g$&$+!#e(B

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

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

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

e$B$=$&$9$l$Pe(B, e$BM#[email protected]$bJ]$?$l$D$De(B,
e$B$A$c$s$H%$%s%9%?%s%9$G<B8=$G$-$^$9e(B.

e$B$G$"$l$P!"$3$&$$$&$N$O$I$&$G$7$g$&$+!#e(B

  1. Prime::Generator e$B$H$$$&AG?tNs5s$N30It%$%F%l!<%?%/%i%9$r:[email protected](B
    1.1. [email protected]$N$?$a!"$^$?FbIt%$%F%l!<%?$NDs6!<T$H$7$Fe(BPrimee$B%/%i%9$r29B8e(B
  2. Prime.each e$B$Oe(B Prime::Generator e$B%*%V%8%’%/%H$r8F$S=P$7$FNs5se(B
  3. (optional) Integer.each_primee$B$Oe(BPrime.eache$B$KE>Awe(B

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

e$B$"$H$Oe(B, e$B>e=R$Ne(B Singleton e$B$N0F$bF~$l$Fe(B,
[email protected]$1$k$H$&$l$7$$$J$He(B.

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

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

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

on Aug/16 14:11(JST) “Yugui (Yuki S.)” writes:

mathn.rbe$B$K<}O?$5$l$F$$$ke(BPrimee$B%/%i%9$N;H$$>!<j$,$$$^$$$ANI$/$J$$$N$G2~A1e(B
e$B$rDs0F$7$^$9!#D>$7$?$$$N$Oe([email protected]$G$9!#e(B

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

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

[email protected]$G$9!#e(B

At Tue, 19 Aug 2008 12:43:04 +0900,
keiju ISHITSUKA wrote in [ruby-dev:35875]:

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

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

e$B$=$&$9$l$Pe(B, e$BM#[email protected]$bJ]$?$l$D$De(B, e$B$A$c$s$H%$%s%9%?%s%9$G<B8=$G$-$^$9e(B.

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

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

[email protected]$1$G$$$$$h$&$J5$$b$7$J$/$O$J$$$G$9!#e(B

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

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

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

[email protected]$G$9!#e(B

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

e$B;d$b$=$&$J$N$+$J$!e(B? e$B$H;W$$$D$D$be(B, e$B$G$Oe(B,
e$B85$N%/%i%9$NL>A0$O$I$&[email protected](B?
e$B$H;W$C$?$j$b$7$F$^$9e(B.

[email protected]$1$G$$$$$h$&$J5$$b$7$J$/$O$J$$$G$9!#e(B

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

e$B$3$l$C$Fe(B, Yugui e$B$5$s$NBh#20Fe(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

e$B$H6a$$$G$9$,e(B, include Enumerable e$B$,F~$C$F$$$^$;$se(B. Enuerable
e$B$G$"$kI,e(B
e$BMW$O$J$/e(B each [email protected]$1$"$l$P$h$$$C$F$3$H$G$9e(B?

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

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

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

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

e$B2?$+%a%$%k$,$?$^$C$F$7$^$C$Fe(B…
e$B7h$7$FK:$l$F$$$k$o$1$G$O$"$j$^$;$s$N$Ge(B, > e$BBT$C$F$$$kJ}e(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:

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

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

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

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

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

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

e$B$G$be(B, [email protected]$C$F$$$k5$$,$7$^$9$Me(B.
e$BNc$($Pe(B, e$BAG?t$+$I$&e(B
e$B$+H=Dj$9$k%a%=%C%I$b$3$A$i$NJ}K!$r;H$C$?J}$,[email protected]$C$F$$$^$9$7e(B…

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

[email protected]$G$9!#e(B

At Wed, 20 Aug 2008 11:52:55 +0900,
[email protected]=<ye(B wrote in [ruby-dev:35882]:

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

e$B;d$b$=$&$J$N$+$J$!e(B? e$B$H;W$$$D$D$be(B, e$B$G$Oe(B, e$B85$N%/%i%9$NL>A0$O$I$&[email protected](B?
e$B$H;W$C$?$j$b$7$F$^$9e(B.

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

[email protected]$1$G$$$$$h$&$J5$$b$7$J$/$O$J$$$G$9!#e(B

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

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

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

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

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

e$B$=$3$OLdBj$G$9$M!#e(BPrime#succe$B$N%k!<%W$re(Bsynchronizee$B$5$;$l$P$$$$$Ge(B
e$B$7$g$&$+!#e(B

e$B$R$H$^$:!"e(BPrimee$B4X78$rJL%U%!%$%[email protected]$jJ,$1$k$H$3$m$^$G$d$C$F$7$^$Ce(B
e$B$F$O$I$&$G$7$g$&$+!#e(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

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

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

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

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

yuguie$B$5$s$N$H$O0U?^[email protected]$H;W$$$^$9$,e(B…

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

[email protected]$G$9!#e(B

e$B;d$b$=$&$J$N$+$J$!e(B? e$B$H;W$$$D$D$be(B, e$B$G$Oe(B, e$B85$N%/%i%9$NL>A0$O$I$&[email protected](B?
e$B$H;W$C$?$j$b$7$F$^$9e(B.

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

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

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

Generatore$B$,0l<oN`[email protected]$($k$H;W$&$N$G$9$,e(B,
e$BK-J!$5$s$N%a%$%k$N$he(B
e$B$&$Ke(B,e$BC1D4A}2C$G>/$J$/$H$b$9$Y$F$NAG?t$,4^$^$l$k?tNs$rMQ$$$kJ}$,NI$$>le(B
e$B9g$b$"$k$N$Ge(B, Generator e$B$Oe(B
e$BJL$K$"$C$?J}$,$h$$5$$,$7$F$$$^$9e(B.

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

e$B;d$,[email protected]$$$?$+$C$?$3$H$H$A$g$C$H$:$l$F$k$+$be(B.
e$B>$7$/$OE:IU$N%3!<%I$r8+$Fe(B
[email protected]$-$?$$$N$G$9$,e(B, @@class_var
e$B$,B?MQ$5$l$F$$$k$N$,5$$K$/$o$J$$$N$Ge(B,
e$B$=$l$r$J$/$7$?$+$C$?$N$G$9e(B.

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

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

e$B?70Fe(B:

  • Primee$B%/%i%9$Oe(B singleton.

  • Primee$B%/%i%9%a%=%C%I$O%$%s%9%?%s%9%a%=%C%I$K%G%l%2!<%H$9$ke(B.

  • Prime::Generator
    e$BAG?tNs$Ne(Bgenerator

  • Prime::Generator23
    e$BK-J!$5$s$Ne(Bgenerator.
    e$BL>A0$NM3Mhe(B: 2e$B$He(B3e$B$NG?t0J30$N?tCM$J$N$Ge(B.

  • Prime::IncreaseSuperPrimeGenerator
    e$B>e5-e(B2e$B$D$Ne(Bgeneratore$B$NCj>]%9!<%Q!<%/%i%9e(B
    e$BL>A0$O$$$^$$$A$J$s$G$9$,e(B, e$B>:=g$Ge(B,
    e$BAG?t=89g$N%9!<%Q!<%;%C%H$K$J$ke(B
    generator e$B$H$$$&$3$H$m$+$i$H$C$F$$$^$9e(B.
    e$B$h$$L>A0Jg=8Cfe(B

  • Prime::PrimeSet
    [email protected]@.$NK\BNe(B
    singletone$B$K$9$k$3$H$K$h$C$Fe(B, e$B%/%i%9JQ?t$r$J$/$7$F$$$^$9e(B

  • Integer e$B$KDI2C$5$l$k%a%=%C%Ie(B
    e$B<BAu$Oe(B, Primee$B$NJ}$K0\F0e(B

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

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

e$B$40U8+Jg=8Cfe(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

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

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のサブセットにはなる
と思います。

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と併せてコミットしようと思います。いかがで
しょうか?

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

In [ruby-dev :36067]

e$B?7$7$$e(Bprime.rbe$B$rE:IU$7$^$9!#e(B

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

e$B$1$$$8$e!w$$$7$D$+$G$9e(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:

Yuguie$B$G$9!#e(B

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

e$B;d$,Aw$C$?%3!<%I$b4{B8$Ne(BPrime.newe$B$7$F$$$k%3!<%I$KG[N8$7$F$O$$$^$9$,!"e(B
[email protected]$r$h$j3N<B$KDs6!$9$k$H$$$&0UL#$G$Oe(BPrimee$B$,%/%i%9$GM-$jB3$1$?$[$&$,e(B
e$BNI$$$+$b$7$l$^$;$s!#e(B

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

[email protected]!"$=$N0UL#[email protected]$5$s$N!"e(BPrimee$B$r40A4$K%7%s%0%k%H%s%Q%?!<%s$K$7$F$7e(B
e$B$^$&$N$Oe(BPrime.newe$B$G$-$J$$$N$G:$$k$H;W$$$^$9!#e(B

e$B$^$"e(B, [email protected]$+$iNI$$$+$H;W$C$Fe(B(^^;;

  1. e$B5?;[email protected]@.$9$ke(BGeneratore$B$b$[$7$$e(B
    => Prime::Generator, Prime::Generator23, Prime::EratosthenesGenerator

e$B$O$$e(B.

Prime::e$B$NDj?t%9%3!<%W$rDs6!$9$k$?$a$K$be(BPrimee$B$O!";d$,=q$$$?$h$&$Je(B
singletone$B$J%
%V%8%’%/%H$h$j$O!"@PDM$5$s$N$h$&$Je(Bsingletone$B%Q%?!<%s$N$[$&$,e(B
e$BNI$5$=$&$K;W$($^$9!#e(B

e$B$G$9$Me(B.

[email protected]$7!"[email protected]$N$?$a$Ke(BPrime.newe$B$b5vMF$9$k$h$&$K$7$F$_$^$7$?!#$3$N%P!<e(B
e$B%8%g%s$Ne(Bprime.rbe$B$rE:IU$7$^$9!#e(B

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

e$B$3$NB>!"e(B
a) e$B%(%i%H%9%F%M%9$N$U$k$$$Ge(BGeneratore$B$r=q$$$F$_$?$i$H$F$bB.$/$J$C$?$N$G!“e(B
Prime::EratosthenesGeneratore$B$r2C$($F$”$j$^$9!#e(B

 user     system      total        real

trial division
17.060000 22.580000 39.640000 ( 39.556764)
eratosthenes
2.270000 0.010000 2.280000 ( 2.277945)

e$B$*!<e(B.

(2**19-1)**2 e$B$NAG0x?tJ,2r$G$be(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)

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

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

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

e$B$K$J$j$^$9e(B. e$B%*!<%@!<$Oe(BGeneratore$B$NJ}$,NI$$$G$9e(B.
[email protected](B, e$B:G=i$N$&$A$Oe(B
Eratos e$B$NJ}$,6u4V8zN($ONI$$$G$9e(B,
Generatore$B$NJ}$,%a%b%j$r;H$o$J$/$J$ke(B n
e$B$r5a$a$k$He(B

n = 3.8*10**55

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

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

e$B$H$$$&$3$H$Ge(B, Prime#each e$B$Ne(B e$B%G%U%)%k%H$Ne(B Generator
e$B$re(B
EratosthenesGenerator e$B$K$7$^$7$g$&e(B.

e$B$"$He(B,

Generator e$B$re(B TrialDivisionGenerator
PrimeSet e$B$re(B TrialDivision

e$B$K2~L>$7$^$7$g$&$+e(B? e$B$=$l$He(B, e$B7G:=gHV$re(B Eratosthenes*
[email protected]$K$7$^$7$g$&e(B
e$B$+e(B?

b) Prime.eache$B$,>e3&$r$H$k$h$&$K$7$F$_$^$7$?!#$=$3$KE~C#$7$?$iNs5s$rBGe(B
[email protected]$j$^$9!#e(B

e$B$?$7$+$K$Me(B. e$B$"$C$?J}$,NI$$$+$be(B.

c) Prime.eache$B$NBhe(B2e$B0z?t$Ke(Bgeneratore$B$r;XDj$G$-$k$h$&$K$7$F$_$^$7$?!#e(B

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

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

e) Enumeratore$B$K9g$o$;$F!"e(BGeneratore$B$Ke(Bwith_indexe$B$He(Bnexte$B$He(Brewinde$B$rB-$7$^e(B
e$B$7$?!#e(B

e$BN;2re(B

  • Prime::IncreaseSuperPrimeGenerator
    e$B3N$+$K$3$NL>A0$K$O0cOB46$,$"$j$^$9$M!#e(B

PseudoPrimeGeneratore$B$"$?$j$G$O$I$&$G$7$g$&$+!#e(BGenerator23e$B$_$?$$$K!V5?e(B
e$B;[email protected]:EY$,0-$/$F$b!“5U$K??$Ke(Bprimee$B$G$”$C$F$be(BPseudoe$B$N%5%V%;%C%H$K$O$J$ke(B
e$B$H;W$$$^$9!#e(B

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

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

e$B$b$7e(B, e$BLdBj$J$$$h$&$G$"$l$Pe(B, e$B$9$$$^$;$s$,e(B,
e$B$=$l$rJQ99$7$Fe(Bcomit e$B$7$F$$$?e(B
[email protected]$1$J$$$G$9e(B?

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

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

  •  q,r = divmod value num
    

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

e$B$G$9$M!#e(BHaskelle$BJJ$,!&!&!&e(B orz

Yuguie$B$G$9!#e(B

TOYOFUKU Chikanobu e$B$5$s$O=q$-$^$7$?e(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

[email protected]$He(B2e$B$,AG?t$K$J$i$J$$$G$9!#99$Ke(B

  •  return false if r == 0
     return true if q <= num
    
  •  return false if r == 0
    

e$B$+$J!#e(B

Yugui (Yuki S.) e$B$5$s$O=q$-$^$7$?e(B:

[email protected]$He(B2e$B$,AG?t$K$J$i$J$$$G$9!#99$Ke(B

  •  return false if r == 0
     return true if q <= num
    
  •  return false if r == 0
    

e$B$*$C$H!#e(B

  •  return false if r == 0
    
  •  return true if q <= num
     return true if q < num
    
  •  return false if r == 0
    

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

Yuguie$B$G$9!#e(B

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

OldCompatibility

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

e$B$1$$$8$e!w$$$7$D$+$G$9e(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:

Yuguie$B$G$9!#e(B

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

e$B$"$j$,$H$&$4$6$$$^$9!#%3%_%C%H$7$h$&$+$H;W$$$^$7$?$,%F%9%H$r=q$$$F$$$?$ie(B
[email protected]$K5$$E$-$^$7$?!#7k2L$H$7$F$A$g$C$HJQ99$,I,MW$K$J$j$=$&$G$9$N$G!"e(B
e$B62$lF~$j$^$9$,:FEY3NG’$r$*4j$$$7$^$9!#e(B

e$B$O$$e(B.

[email protected]$K$*Aw$j$7$?e(Bprime.rbe$B$G$Oe([email protected]$,$"$j$^$7$?!#e(B

  1. Prime.eache$B$,JV$9e(Benumerator(e$B<B:]$K$Oe(Bgenerator)e$B$,!"e(Bubounde$B$r5-21$7$J$$!#e(B
    Prime.each(100){|p| }e$B$ODd;_$9$k$N$K!"e(BPrime.each(100).each{|p| }e$B$ODd;_e(B
    e$B$7$J$$$H$$$&4qL/$J7k2L$K$J$j$^$9!#e(B

e$B$3$l$Oe(B, e$B$^$:$$$G$9$Me(B.

  1. Prime#nexte$B$,$J$$!#e(B
    [email protected][email protected]$o$C$F8+$;$?3d$K$&$C$+$je(BPrime#nexte$B$N<BAu$r=q$-K:$l$F$$$^$7$?!#e(B
    e$B$^$?!"@h$N%P!<%8%g%s$r85$KC1=c$Ke(BPrime#nexte$B$r<BAu$9$k$He(BPrime#nexte$B$K$h$Ce(B
    [email protected]%]%$%s%?$He(BPrime#eache$B$,F14|$7$^$;$s!#e(BPrime#[email protected])$De(B
    Prime#nexte$B$K4X$o$i$:e(B2e$B$+$iNs5s$r3+;O$7$F$7$^$$$^$9!#e(B
    e$B0lJ}!"e(BPrime::eache$B$de(BPrime::instance.eache$B$N$[$&[email protected])$De(BPrimee$B$N%$%s%9%?%se(B
    e$B%9%a%=%C%I8F$S=P$7$K$O1F6A$5$l$:$Ke(B2e$B$+$iNs5s$9$k$3$H$r4|BT$5$l$k$H;W$$e(B
    e$B$^$9!#e(B

e$B$&!<$se(B. [email protected]$o$l$F$$$k$3$H$OJ,$+$j$^$9$,e(B,
eache$B$H$+%3!<%I$,Hs>o$K$o$+$je(B
e$B$:$i$$$G$9$M$'e(B(^^;;

e$B$A$J$_$K3NG’$G$9$,e(B, e$B?7HG$NJ}$Oe(B, Prime.succ
e$B$OEvA3I,MW$J$$$o$1$G$9$Me(B?
e$B8E$$HG$G$Oe(B, Prime#eache$B$Oe(Bunboound,
generatore$B$N;XDj$H$+$$$i$J$$$G$9$h$Me(B?

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

e$B$h$1$l$Pe(B,

OldCompatibility

e$B$re(B Primee$B%/%i%9$N:[email protected](B,
e$BK-J!$5$s$N$rH?1G$7$F%3%_%C%He(B
[email protected]$1$l$P$H;W$$$^$9e(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.

__
---------------------------------------------------->> [email protected](B
e$B7=<ye(B <<—
---------------------------------->> e-mail: [email protected] <<—

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs