* string.c (rb_str_clear): avoid revealing NULL pointer.

  [ruby-dev:24766]

* string.c (str_gsub): add paranoid check. [ruby-dev:24827]

* string.c (str_mod_check): check frozen status as well.
  [ruby-dev:24801]

* lib/mathn.rb (Integer::gcd2): faster implementation by
  <erlercw@siu.edu>. [ruby-talk:120232]

* ext/gdbm/gdbm.c (fgdbm_store): StringValue() may alter string
  pointer.  [ruby-dev:24783]


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@7265 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 47 insertions, 38 deletions

diff --git a/lib/mathn.rb b/lib/mathn.rb
index aa2da885f3..ba8557cffc 100644
--- a/lib/mathn.rb
+++ b/lib/mathn.rb
@@ -17,24 +17,13 @@ require "matrix.rb"
 class Integer
 
   remove_method(:gcd2)
-  def gcd2(int)
-    a = self.abs
-    b = int.abs
-    a, b = b, a if a < b
-    
-    pd_a = a.prime_division
-    pd_b = b.prime_division
-    
-    gcd = 1
-    for pair in pd_a
-      as = pd_b.assoc(pair[0])
-      if as
-	gcd *= as[0] ** [as[1], pair[1]].min
-      end
-    end
-    return gcd
+  def gcd2(other)
+    min = self.abs
+    max = other.abs
+    min, max = max % min, min while min > 0
+    max
   end
-  
+
   def Integer.from_prime_division(pd)
     value = 1
     for prime, index in pd
@@ -68,34 +57,54 @@ end
   
 class Prime
   include Enumerable
+  # 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
+
+  class << self
+    # Return the prime cache.
+    def cache
+      return @@primes
+    end
+    alias primes cache
+    alias primes_so_far cache
+  end
+  
   def initialize
-    @seed = 1
-    @primes = []
-    @counts = []
+    @index = -1
+  end
+  
+  # Return primes given by this instance so far.
+  def primes
+    return @@primes[0, @index + 1]
   end
+  alias primes_so_far primes
   
   def succ
-    i = -1
-    size = @primes.size
-    while i < size
-      if i == -1
-	@seed += 1
-	i += 1
-      else
-	while @seed > @counts[i]
-	  @counts[i] += @primes[i]
-	end
-	if @seed != @counts[i]
-	  i += 1
-	else
-	  i = -1
-	end
+    @index += 1
+    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
-    @primes.push @seed
-    @counts.push @seed + @seed
-    return @seed
+    return @@primes[@index]
   end
   alias next succ