prime.rb in rubysl-prime-2.0.1

- old
+ new

@@ -69,24 +69,24 @@
 #
 # == Generators
 #
 # A "generator" provides an implementation of enumerating pseudo-prime
 # numbers and it remembers the position of enumeration and upper bound.
-# Furthermore, it is a external iterator of prime enumeration which is
-# compatible to an Enumerator.
+# Furthermore, it is an external iterator of prime enumeration which is
+# compatible with an Enumerator.
 #
 # +Prime+::+PseudoPrimeGenerator+ is the base class for generators.
 # There are few implementations of generator.
 #
 # [+Prime+::+EratosthenesGenerator+]
-#   Uses eratosthenes's sieve.
+#   Uses eratosthenes' sieve.
 # [+Prime+::+TrialDivisionGenerator+]
 #   Uses the trial division method.
 # [+Prime+::+Generator23+]
-#   Generates all positive integers which is not divided by 2 nor 3.
+#   Generates all positive integers which are not divisible by either 2 or 3.
 #   This sequence is very bad as a pseudo-prime sequence. But this
-#   is faster and uses much less memory than other generators. So,
+#   is faster and uses much less memory than the other generators. So,
 #   it is suitable for factorizing an integer which is not large but
 #   has many prime factors. e.g. for Prime#prime? .
 
 class Prime
   include Enumerable
@@ -131,17 +131,17 @@
   #
   # Calls +block+ once for each prime number, passing the prime as
   # a parameter.
   #
   # +ubound+::
-  #   Upper bound of prime numbers. The iterator stops after
+  #   Upper bound of prime numbers. The iterator stops after it
   #   yields all prime numbers p <= +ubound+.
   #
   # == Note
   #
-  # +Prime+.+new+ returns a object extended by +Prime+::+OldCompatibility+
-  # in order to compatibility to Ruby 1.8, and +Prime+#each is overwritten
+  # +Prime+.+new+ returns an object extended by +Prime+::+OldCompatibility+
+  # in order to be compatible with Ruby 1.8, and +Prime+#each is overwritten
   # by +Prime+::+OldCompatibility+#+each+.
   #
   # +Prime+.+new+ is now obsolete. Use +Prime+.+instance+.+each+ or simply
   # +Prime+.+each+.
   def each(ubound = nil, generator = EratosthenesGenerator.new, &block)
@@ -189,13 +189,13 @@
   #
   # == Parameters
   # +value+:: An arbitrary integer.
   # +generator+:: Optional. A pseudo-prime generator.
   #               +generator+.succ must return the next
-  #               pseudo-prime number in the ascendent
+  #               pseudo-prime number in the ascending
   #               order. It must generate all prime numbers,
-  #               but may generate non prime numbers.
+  #               but may also generate non prime numbers too.
   #
   # === Exceptions
   # +ZeroDivisionError+:: when +value+ is zero.
   #
   # == Example
@@ -207,11 +207,11 @@
   #
   #   [[p_1, e_1], [p_2, e_2], ...., [p_n, e_n]].
   #
   #   Prime.prime_division(12) #=> [[2,2], [3,1]]
   #
-  def prime_division(value, generator= Prime::Generator23.new)
+  def prime_division(value, generator = Prime::Generator23.new)
     raise ZeroDivisionError if value == 0
     if value < 0
       value = -value
       pv = [[-1, 1]]
     else
@@ -270,11 +270,11 @@
     # See +Enumerator+#rewind.
     def rewind
       raise NotImplementedError, "need to define `rewind'"
     end
 
-    # Iterates the given block for each prime numbers.
+    # Iterates the given block for each prime number.
     def each(&block)
       return self.dup unless block
       if @ubound
         last_value = nil
         loop do
@@ -304,16 +304,17 @@
   # An implementation of +PseudoPrimeGenerator+.
   #
   # Uses +EratosthenesSieve+.
   class EratosthenesGenerator < PseudoPrimeGenerator
     def initialize
-      @last_prime = nil
+      @last_prime_index = -1
       super
     end
 
     def succ
-      @last_prime = @last_prime ? EratosthenesSieve.instance.next_to(@last_prime) : 2
+      @last_prime_index += 1
+      EratosthenesSieve.instance.get_nth_prime(@last_prime_index)
     end
     def rewind
       initialize
     end
     alias next succ
@@ -334,15 +335,15 @@
       initialize
     end
     alias next succ
   end
 
-  # Generates all integer which are greater than 2 and
-  # are not divided by 2 nor 3.
+  # Generates all integers which are greater than 2 and
+  # are not divisible by either 2 or 3.
   #
   # This is a pseudo-prime generator, suitable on
-  # checking primality of a integer by brute force
+  # checking primality of an integer by brute force
   # method.
   class Generator23<PseudoPrimeGenerator
     def initialize
       @prime = 1
       @step = nil
@@ -416,75 +417,55 @@
       end
       return @primes[index]
     end
   end
 
-  # Internal use. An implementation of eratosthenes's sieve
+  # Internal use. An implementation of eratosthenes' sieve
   class EratosthenesSieve
     include Singleton
 
-    BITS_PER_ENTRY = 16  # each entry is a set of 16-bits in a Fixnum
-    NUMS_PER_ENTRY = BITS_PER_ENTRY * 2 # twiced because even numbers are omitted
-    ENTRIES_PER_TABLE = 8
-    NUMS_PER_TABLE = NUMS_PER_ENTRY * ENTRIES_PER_TABLE
-    FILLED_ENTRY = (1 << NUMS_PER_ENTRY) - 1
-
-    def initialize # :nodoc:
-      # bitmap for odd prime numbers less than 256.
-      # For an arbitrary odd number n, @tables[i][j][k] is
-      # * 1 if n is prime,
-      # * 0 if n is composite,
-      # where i,j,k = indices(n)
-      @tables = [[0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196].freeze]
+    def initialize
+      @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]
+      # @max_checked must be an even number
+      @max_checked = @primes.last + 1
     end
 
-    # returns the least odd prime number which is greater than +n+.
-    def next_to(n)
-      n = (n-1).div(2)*2+3 # the next odd number to given n
-      table_index, integer_index, bit_index = indices(n)
-      loop do
-        extend_table until @tables.length > table_index
-        for j in integer_index...ENTRIES_PER_TABLE
-          if !@tables[table_index][j].zero?
-            for k in bit_index...BITS_PER_ENTRY
-              return NUMS_PER_TABLE*table_index + NUMS_PER_ENTRY*j + 2*k+1 if !@tables[table_index][j][k].zero?
-            end
-          end
-          bit_index = 0
-        end
-        table_index += 1; integer_index = 0
-      end
+    def get_nth_prime(n)
+      compute_primes while @primes.size <= n
+      @primes[n]
     end
 
     private
-    # for an odd number +n+, returns (i, j, k) such that @tables[i][j][k] represents primarity of the number
-    def indices(n)
-      #   binary digits of n: |0|1|2|3|4|5|6|7|8|9|10|11|....
-      #   indices:            |-|    k  |  j  |     i
-      # because of NUMS_PER_ENTRY, NUMS_PER_TABLE
+    def compute_primes
+      # max_segment_size must be an even number
+      max_segment_size = 1e6.to_i
+      max_cached_prime = @primes.last
+      # do not double count primes if #compute_primes is interrupted
+      # by Timeout.timeout
+      @max_checked = max_cached_prime + 1 if max_cached_prime > @max_checked
 
-      k = (n & 0b00011111) >> 1
-      j = (n & 0b11100000) >> 5
-      i = n >> 8
-      return i, j, k
-    end
+      segment_min = @max_checked
+      segment_max = [segment_min + max_segment_size, max_cached_prime * 2].min
+      root = Integer(Math.sqrt(segment_max).floor)
 
-    def extend_table
-      lbound = NUMS_PER_TABLE * @tables.length
-      ubound = lbound + NUMS_PER_TABLE
-      new_table = [FILLED_ENTRY] * ENTRIES_PER_TABLE # which represents primarity in lbound...ubound
-      (3..Integer(Math.sqrt(ubound))).step(2) do |p|
-        i, j, k = indices(p)
-        next if @tables[i][j][k].zero?
+      sieving_primes = @primes[1 .. -1].take_while { |prime| prime <= root }
+      offsets = Array.new(sieving_primes.size) do |i|
+        (-(segment_min + 1 + sieving_primes[i]) / 2) % sieving_primes[i]
+      end
 
-        start = (lbound.div(p)+1)*p  # least multiple of p which is >= lbound
-        start += p if start.even?
-        (start...ubound).step(2*p) do |n|
-          _, j, k = indices(n)
-          new_table[j] &= FILLED_ENTRY^(1<<k)
+      segment = ((segment_min + 1) .. segment_max).step(2).to_a
+      sieving_primes.each_with_index do |prime, index|
+        composite_index = offsets[index]
+        while composite_index < segment.size do
+          segment[composite_index] = nil
+          composite_index += prime
         end
       end
-      @tables << new_table.freeze
+
+      segment.each do |prime|
+        @primes.push prime unless prime.nil?
+      end
+      @max_checked = segment_max
     end
   end
 
   # Provides a +Prime+ object with compatibility to Ruby 1.8 when instantiated via +Prime+.+new+.
   module OldCompatibility