# Faster Prime class then Ruby 1.9

**URL:** <https://www.ruby-forum.com/t/faster-prime-class-then-ruby-1-9/225899>\
**Category:** Ruby\
**Created:** [February 3, 2006, 8:21am UTC](https://www.ruby-forum.com/t/faster-prime-class-then-ruby-1-9/225899 "2006-02-03T08:21:57Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![phildobbin](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/p/b782af/32.png) [@phildobbin](https://www.ruby-forum.com/u/phildobbin)\
**Post date:** [February 3, 2006, 8:21am UTC](https://www.ruby-forum.com/t/faster-prime-class-then-ruby-1-9/225899/1 "2006-02-03T08:21:57Z")

</div>

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