[前][次][番号順一覧][スレッド一覧]

ruby-changes:46694

From: marcandre <ko1@a...>
Date: Sat, 20 May 2017 09:37:02 +0900 (JST)
Subject: [ruby-changes:46694] marcandRe: r58809 (trunk): lib/prime: Fix primality of some large integers [#13492].

marcandre	2017-05-20 09:36:55 +0900 (Sat, 20 May 2017)

  New Revision: 58809

  https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=58809

  Log:
    lib/prime: Fix primality of some large integers [#13492].
    
    * lib/prime.rb: Use accurate sqrt to insure all factors are tested.
      Patch by Marcus Stollsteimer.
    
    * test/test_prime.rb: Adapt test for timeout

  Modified files:
    trunk/lib/prime.rb
    trunk/test/test_prime.rb
Index: test/test_prime.rb
===================================================================
--- test/test_prime.rb	(revision 58808)
+++ test/test_prime.rb	(revision 58809)
@@ -174,20 +174,21 @@ class TestPrime < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/test_prime.rb#L174
   def test_eratosthenes_works_fine_after_timeout
     sieve = Prime::EratosthenesSieve.instance
     sieve.send(:initialize)
+    # simulates that Timeout.timeout interrupts Prime::EratosthenesSieve#compute_primes
+    class << Integer
+      alias_method :org_sqrt, :sqrt
+    end
     begin
-      # simulates that Timeout.timeout interrupts Prime::EratosthenesSieve#compute_primes
-      def sieve.Integer(n)
-        n = super(n)
+      def Integer.sqrt(n)
         sleep 10 if /compute_primes/ =~ caller.first
-        return n
+        org_sqrt(n)
       end
-
       assert_raise(Timeout::Error) do
         Timeout.timeout(0.5) { Prime.each(7*37){} }
       end
     ensure
-      class << sieve
-        remove_method :Integer
+      class << Integer
+        alias_method :sqrt, :org_sqrt
       end
     end
 
Index: lib/prime.rb
===================================================================
--- lib/prime.rb	(revision 58808)
+++ lib/prime.rb	(revision 58809)
@@ -35,7 +35,7 @@ class Integer https://github.com/ruby/ruby/blob/trunk/lib/prime.rb#L35
     return self >= 2 if self <= 3
     return true if self == 5
     return false unless 30.gcd(self) == 1
-    (7..Math.sqrt(self).to_i).step(30) do |p|
+    (7..Integer.sqrt(self)).step(30) do |p|
       return false if
         self%(p)    == 0 || self%(p+4)  == 0 || self%(p+6)  == 0 || self%(p+10) == 0 ||
         self%(p+12) == 0 || self%(p+16) == 0 || self%(p+22) == 0 || self%(p+24) == 0
@@ -445,7 +445,7 @@ class Prime https://github.com/ruby/ruby/blob/trunk/lib/prime.rb#L445
 
       segment_min = @max_checked
       segment_max = [segment_min + max_segment_size, max_cached_prime * 2].min
-      root = Integer(Math.sqrt(segment_max).floor)
+      root = Integer.sqrt(segment_max)
 
       segment = ((segment_min + 1) .. segment_max).step(2).to_a
 

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/

[前][次][番号順一覧][スレッド一覧]