mathn.rb is unacceptably slow (proposed replacements)

[erlercw]

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

 

[erlercw]

# 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.

 

[Yukihiro Matsumoto]

Hi,

In message "Re: mathn.rb is unacceptably slow (proposed replacements)"

|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.

 

[Giovanni Intini]

|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.

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

 

[erlercw]

Date: 15-Nov-2004 16:50:53 -0600
From: "Giovanni Intini" <[email protected]> ...
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

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 .

 

[Giovanni Intini]

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