From: "erlercw@..." <erlercw@...>
Date: 2004-11-14T09:51:49+09:00
Subject: mathn.rb is unacceptably slow (proposed replacements)

In mathn.rb (ruby 1.8.1), Integer#gcd2 and the Prime class are 
unacceptably slow.

(The Integer#gcd2 replacement below is also faster than both Integer#gcd and 
Integer#gcd2 in rational.rb, at least on this machine, and might be a nice 
replacement for Integer#gcd there.)

Try the following test with the standard mathn and then with the method and class 
replacements below it :

require 'mathn'
puts "Finding the GCDs of 10,000 pairs starting at #{Time.now}...."
10000.times { rand(10000).gcd2(rand(10000)) }
puts "Finished with that, now finding the first 10,000 primes at #{Time.now}...."
primes = Prime.new
10000.times { primes.succ }
puts "Finished with that at #{Time.now}...."

Here are replacements for Integer#gcd2 and the Prime class which are effectively 
identical (with Prime.cache and Prime#primes_so_far added), but are thousands of 
times faster for any kind of heavy use :



# Use a Euclidean GCD algorithm
def gcd2(other)
  min, max = [self.abs, other.abs].sort
  min, max = max % min, min while min > 0
  max
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
    @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
    @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
    return @@primes[@index]
  end
  alias next succ

  def each
    loop do
      yield succ
    end
  end
end



There are other methods from number theory which are a lot faster than mine, but 
these are an easy and quick change with a large speed benefit.  Plus, I don't know 
how to do those ;)