Hi all,

I have been playing with my implementation or the Prime class since the

my

previous thread where Antonio C. provided the new and improved

Ruby

1.9 version of mathn.rb. Once I understood the new version, I found it

to

be very close to the base version of my implentation. I did find a

simple

way to make it significantly (over 8 times) faster. The Prime#succ

method

uses the following line to check a number, and add it to the list if it

is a

prime number.

@@primes.push @@next_to_check if @@primes[2…@@ulticheck_index].find

{|prime| @@next_to_check % prime == 0 }.nil?

I noticed that that creates a new sub array

@@primes[2…@@ulticheck_index]

every time. Simply extracting that out to another class variable array

that

gets one entry added to it every time ulticheck_index is incremented

dropped

the time to get 100,000 prime numbers from 377 seconds to 46.3 seconds.

I

have made a few other adjustments to implement a method of skipping more

non-prime numbers without having to test each case. The existing Ruby

1.9

version only checks 2 out of 6 numbers (1 and 5 for N modulo 6, step

size of

4 and 2). I have it setup to that it skips more numbers using higher

modulos (6 = 2*3 = first 2 primes; I use more primes to get the product

value).

As is, the code rebuilds the list of step sizes when the mathn.rb file

is

initially required. That introduces a startup penalty that becomes

noticable in the benchmarks when 5 primes are used. At 7 primes it

becomes

significant (4 seconds). Even with that overhead included, the 7 primes

case is faster at getting 100,000 primes than any of the others I have

tried

(I did not try 8 primes).

The step size calculation code could be moved to the initialize method,

to

delay that startup cost until the first prime is calculated. For lists

based on products of less than about 6 prime numbers, the calculation

can be

replaced by hard-coded lists. The product for 5 primes is 2310, and the

list of step sizes is 480 elements long. For 6 primes the product is

30030,

and the list of step sizes jumps to 5760 elements.

Perhaps someone will see a more efficient way of creating that step size

list. I did not spend too much time on it, once I found a fairly clean

‘Ruby’ way of building it. It does not seem to be worth it to make the

list

much bigger. The improvements I get by increasing it are fairly small.

Going from the initial adjustment that got to 46.3 seconds, to a version

that uses an array of 2 step values increased the time to 48.4 seconds.

Increasing the number of primes used in the product to 3,4,5,6,7 changed

the

time to 46.6, 44.8, 44.1, 43.0, 42,4 seconds. All times are in seconds

to

get 100,008 prime numbers on my 1Ghz Windows XP Pro with 512M. All

times

include the require line to load the Prime class (not the full mathn).

More

improvement is possible if the step array can be created more

efficiently.

That final 42.4 second value includes almost 4 seconds of overhead to

build

the array.

Here are the times to get the first 50 prime numbers :: mostly the time

for

the require, which includes the step size array initialization. version

2b

uses 2 primes to calculate the product, then calculates the step sizes.

3b,

4b, 5b, 6b, 7b each used one more prime number in the product.

Starting Prime number search benchmark script for mathn_1p9_2b

user system total

real

mathn_1p9_2b: 1 to 50 0.016000 0.000000 0.016000 (

0.016000)

mathn_1p9_3b: 1 to 50 0.000000 0.016000 0.016000 (

0.016000)

mathn_1p9_4b: 1 to 50 0.000000 0.016000 0.016000 (

0.015000)

mathn_1p9_5b: 1 to 50 0.016000 0.016000 0.032000 (

0.032000)

mathn_1p9_6b: 1 to 50 0.219000 0.015000 0.234000 (

0.234000)

mathn_1p9_7b: 1 to 50 3.906000 0.032000 3.938000 (

3.938000)

Here are the changes to the Prime class. This shows the version that

uses 7

prime numbers in the product, but all that needs to change for the other

cases, is to change the initial list of prime numbers. Everything else

is

calculated from that. I only made changes to the class variables and

the

succ method. Unchanged methods not included here.

# Modified Prime class from Ruby 1.9 mathn.rb -

# by H. Phil D. (PHrienDly Computer Consulting, Ltd.)

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.

@@primes = [2, 3, 5, 7, 11, 13, 17]

@@ulticheck_index = @@primes.size - 1

@@ulticheck_next_squared = @@primes[@@ulticheck_index] ** 2

@@root_primes = []

prd = @@primes.inject( 1 ) { |p, n| p * n } # product of first few

prime

numbers

prime_filter = [ * @@primes.last … prd + 1 ] # list of numbers modulo

prd

that

# could be prime numbers

@@primes.each { |p| prime_filter.delete_if { |n| n % p == 0 }} #remove

all

of

# numbers in the initial filter that are multiples of the prime

numbers that

# are factors of the calculated product.

accum = 1; @@skip_known = prime_filter.map { |n| ( accum, x = n, n -

accum ).last }

# create step sizes to skip values that are known to be

multiples of

the factors

# of the product of the first few prime numbers. This starts

from

prd * + 1

# The sum of the step sizes equals prd, so the steps can be used

continiously

# in a circular manner.

# The above steps to calculate @@skip_known can be replaced by

hard-code

initilization

# of the step values. Here are the values to use that match the first

few

products.

=begin

@@skip_known = [ 2 ] # one prime, product = 2

@@skip_known = [ 4, 2 ] # two primes, product = 6

@@skip_known = [ 6, 4, 2, 4, 2, 4, 6, 2 ] # three primes, product = 30

@@skip_known = [ 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,

6, 4,

6, 8,

4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2,

4,

2, 10, 2 ]

# # four primes, product = 210

=end

class << @@skip_known #provide method for getting next step size in

infinite circle.

@@skip_i = @@skip_known.size - 1

@@skip_n = [ * 1 … @@skip_i ] << 0

def next # sequence through the offsets needed to skip the known

prime

multiples

return self.at( @@skip_i = @@skip_n.at( @@skip_i )) #circular

indexing

end #def next

end #class << @@skip_known

@@next_to_check = 1 #+ @@skip_known.next will get to first possible

prime

after

# @@primes[@@ulticheck_index]

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.

@@next_to_check += @@skip_known.next

if @@next_to_check >= @@ulticheck_next_squared

@@ulticheck_index += 1

@@root_primes.push @@primes.at(@@ulticheck_index)

@@ulticheck_next_squared = @@primes.at(@@ulticheck_index + 1) **

2

end

@@primes.push @@next_to_check if @@root_primes.find {|prime|

@@next_to_check % prime == 0 }.nil?

end

return @@primes[@index]

end

alias next succ

end