Mathn.rb is unacceptably slow (proposed replacements)

ruby-talk
1

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 :wink:

2

# 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

Now that I think of it,

# Use a Euclidean GCD algorithm
def gcd2(other)
  min = self.abs
  max = other.abs
  min, max = max % min, min while min > 0
  max
end

will be even faster. The sort isn't really needed, min = max %
min will ensure that min is the true minimum in one step.

3

Hi,

···

In message "Re: mathn.rb is unacceptably slow (proposed replacements)" on Sun, 14 Nov 2004 09:51:49 +0900, "erlercw@siu.edu" <erlercw@siu.edu> writes:

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 :

I like this. I will merge this.

              matz.

4

Thank you both for the proposal and the merge. Prime especially is so
slow that for any kind of real life use I have to code some sieve of
erathostenes.

A good way to check ruby math speed is the euler project at
mathchallenge. There are some math problems that must be resolved with
a program that takes less than 60 seconds. Anyone can program in his
favourite language, and obviously I chose ruby. Most ppl can try the
brute force approach most of the times, while I can't when primes are
involved and have to think about clever solutions. Being a lazy guy I
really needed the faster Primes, thank again :smiley:

···

On Sun, 14 Nov 2004 18:49:40 +0900, Yukihiro Matsumoto <matz@ruby-lang.org> wrote:

>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 :
I like this. I will merge this.

5

Date: 15-Nov-2004 16:50:53 -0600
From: "Giovanni Intini" <intinig@gmail.com>

...

Thank you both for the proposal and the merge. Prime especially is so
slow that for any kind of real life use I have to code some sieve of
erathostenes.

...

A good way to check ruby math speed is the euler project at
mathchallenge. There are some math problems that must be resolved with
a program that takes less than 60 seconds. Anyone can program in his
favourite language, and obviously I chose ruby. Most ppl can try the
brute force approach most of the times, while I can't when primes are
involved and have to think about clever solutions. Being a lazy guy I
really needed the faster Primes, thank again :smiley:

Strangely enough, the reason I submitted it was that I was also trying to do the Euler
Project challenges. I'm glad that it helped :).

6

Strangely enough, the reason I submitted it was that I was also trying to do the Euler
Project challenges. I'm glad that it helped :).

Well it still hasn't helped because I had to solve those problems
before you came up with the cool code, but I am happy nonetheless :slight_smile: