Faster primality testing and factorization methods in Ruby

Ruby
1

I have created various implementations of methods to replace prime? and
prime_division (from the standard lib file prime.rb) based on a class of
mathematical operators I’ve developed called prime generators (PG).Using
a special form of these PG I term Strictly Prime (SP) prime generators I
have created extremely simple and fast algorithms that can find all the
primes up to some number n, determine the primality of n, or
factorization.

Below are links to the paper which provides the mathematical basis for
the proposed methods with two tables of benchmark results comparing the
performance of the library methods prime? and prime_division with my
proposed methods. I provide test results on 32-bit and 64-bit Linux
systems using 5 reference primes of 17 to 19 digits.

My paper, ‘Improved Primality Testing and Factorization in Ruby’

The code rile ‘primeszp.rb’ is available in my github repository:

2

hmm… when i tried your code from your github link, this shows up:

$ ruby /tmp/primeszp.rb
/tmp/primeszp.rb:44: warning: assigned but unused variable - rescnt
/tmp/primeszp.rb:85: warning: assigned but unused variable - rescnt
/tmp/primeszp.rb:119: warning: assigned but unused variable - rescnt
/tmp/primeszp.rb:159: warning: assigned but unused variable - rescnt
/tmp/primeszp.rb:165: warning: assigned but unused variable - modk
/tmp/primeszp.rb:212: warning: shadowing outer local variable - p
Rehearsal

prime tests for P = 20000000000000003 0.000000 0.000000 0.000000 (
0.000011)
Miller-Rabin 0.000000 0.000000 0.000000 (
0.009361)
primzp7? ^C

$ jruby /tmp/primeszp.rb
Rehearsal

prime tests for P = 20000000000000003 0.020000 0.000000 0.020000 (
0.002000)
Miller-Rabin 0.490000 0.030000 0.520000 (
0.744000)
primzp7? ^C

—> hangs or too slow on both ruby 2.0 and jruby 1.7.4, so i ctrl+C it
after 10 seconds…

i’m using archlinux, amd c-60

3

I get the following, on an Ubuntu 64-bit VM (edited to fit the page
width):

prime.rb:44: warning: assigned but unused variable - rescnt
prime.rb:85: warning: assigned but unused variable - rescnt
prime.rb:119: warning: assigned but unused variable - rescnt
prime.rb:159: warning: assigned but unused variable - rescnt
prime.rb:165: warning: assigned but unused variable - modk
prime.rb:212: warning: shadowing outer local variable - p
Rehearsal -------------------------------------------------
prime tests for P = 20000000000000003
0.000000 0.000000 0.000000 ( 0.000011)
Miller-Rabin 0.000000 0.000000 0.000000 ( 0.000761)
primzp7? 2.290000 0.000000 2.290000 ( 2.294709)
primzp7a? 0.970000 0.000000 0.970000 ( 0.971033)
primzp7b? 0.980000 0.000000 0.980000 ( 0.978331)
primzp? 13 1.900000 0.010000 1.910000 ( 1.905374)
primzp? 17 1.870000 0.000000 1.870000 ( 1.877343)
primzpa? 13 3.200000 0.050000 3.250000 ( 3.255519)
primzpa? 17 3.100000 0.040000 3.140000 ( 3.127512)
factorzp 13 1.940000 0.000000 1.940000 ( 1.949376)
factorzp 17 1.870000 0.000000 1.870000 ( 1.870068)
prime? [ruby lib]
26.550000 0.010000 26.560000 ( 26.569130)
prime_division [ruby lib]
29.570000 0.000000 29.570000 ( 29.585618)
---------------------------------------- total: 74.350000sec

            user     system      total        real

prime tests for P = 20000000000000003
0.000000 0.000000 0.000000 ( 0.000011)
Miller-Rabin 0.000000 0.000000 0.000000 ( 0.000562)
primzp7? 2.320000 0.000000 2.320000 ( 2.319329)
primzp7a? 0.980000 0.000000 0.980000 ( 0.974572)
primzp7b? 0.980000 0.000000 0.980000 ( 0.984110)
primzp? 13 1.920000 0.000000 1.920000 ( 1.923894)
primzp? 17 1.880000 0.010000 1.890000 ( 1.884494)
primzpa? 13 3.080000 0.030000 3.110000 ( 3.109670)
primzpa? 17 3.010000 0.020000 3.030000 ( 3.028406)
factorzp 13 1.910000 0.000000 1.910000 ( 1.917429)
factorzp 17 1.880000 0.000000 1.880000 ( 1.875251)
prime? [ruby lib]
25.170000 0.000000 25.170000 ( 25.177364)
prime_division [ruby lib]
28.270000 0.020000 28.290000 ( 28.298034)

[Kiswono P., note the durations, especially in the core methods;
10s is too short for calculating primality of large numbers. Have
patience.]

Note that all the warnings can be resolved by removing the unused
definitions, and renaming that ‘p’ variable in the block. They’re
messy, but unimportant.

4

ah yeah, on 32-bit it’s really-really slow… (trying on my more powerful
PC
instead of my old laptop for now)

soo… the conclusion would be: Miller-Rabin is the fastest

http://pastie.org/8189939

ruby: 343s
jruby: 284s

5

$ ruby --version
ruby 2.0.0p247 (2013-06-27 revision 41674) [i686-linux]

$ jruby --version
jruby 1.7.4 (2.0.0) 2013-05-16 2390d3b on OpenJDK Server VM 1.7.0_40-b31
+indy [linux-i386]

$ cpuinfo -g
Intel® Processor information utility, Version 4.1.0 Build 20120831
Copyright © 2005-2012 Intel Corporation. All rights reserved.

===== Processor composition =====
Processor name : AMD Phenom™ 9850 Quad-Core Processor
Packages(sockets) : 1
Cores : 4
Processors(CPUs) : 4
Cores per package : 4
Threads per core : 1

$ uname -a
Linux 3.9.9-1-pae #1 SMP PREEMPT Mon Jul 8 17:38:58 EDT 2013 i686
GNU/Linux

6

Kiswono P. wrote in post #1117124:

ah yeah, on 32-bit it’s really-really slow… (trying on my more powerful
PC
instead of my old laptop for now)

soo… the conclusion would be: Miller-Rabin is the fastest

http://pastie.org/8189939

ruby: 343s
jruby: 284s

First, thanks to all who have run my code on their systems.

It would be really helpful if you would site your system specs for
comparison purposes. Please provide this minimal system spec info:

Ruby version: ruby-2.0.0-p247, jruby-1.7.4, etc
CPU spec: Intel I5, 4 core, 2.4 GHz, etc.
OS: Linux Mint 14 64-bit, etc

It would be nice to see the performance across a range of hardware
(Intel, AMD, Power PC, etc) and OSs (Linux, OS X, Windows, etc)

Also Miller-Rabin is a probabilistic primality test, which I provided
for comparison. This means it can/will give incorrect answers to some
odd composites (especially odds > 10^16). See more at Miller-Rabin liks:

All my algorithms are deterministic (answers are 100% true or false).

They also lend themselves to parallel implementations.

My primality test algorithms came out of work I originally began on
creating and understanding prime generators and using them to create
prime sieves (finding all primes up to some number N). See my Sieve of
Zakiya, which is faster/more efficient than the Sieve of Eratosthenes,
et al.

7

I changed the Miller-Rabin in the gist to a shorter/faster/adjustable
version which I modified a little. Here’s the new code in the gist.

class Integer

Miller-Rabin prime test in Ruby

From: Miller–Rabin primality test - Wikipedia

Ruby Rosetta Code:

I modified the Rosetta Code, as shown below

require ‘openssl’

def primemr?(k=20) # increase k for more reliability
n = self.abs
return true if n == 2 or n == 3
return false if n % 6 != 1 && n % 6 != 5 or n == 1

 d = n - 1
 s = 0
 (d >>= 1; s += 1) while d & 1 == 0  # while d even
 k.times do
   a = 2 + rand(n-4)
   x = OpenSSL::BN::new(a.to_s).mod_exp(d,n)   #x = (a**d) % n
   next if x == 1 or x == n-1
   (s-1).times do
     x = x.mod_exp(2,n)                        #x = (x**2) % n
     return false if x == 1
     break if x == n-1
   end
   return false if x != n-1
 end
 true  # probably

end
end

8

Here is a much faster, and more standard, method for doing primality
testing and factorization in Ruby.

[Un/L]inux comes with the standard cli command “factor”.

$ factor 30409113
30409113: 3 7 1448053 # here the number is composite

$ factor 6000000000000001
6000000000000001: 6000000000000001 # here the number is a prime

This can be used to create MUCH FASTER and more portable code that will
work exactly the same with all versions of Ruby run under *nix systems.

Here’s the code:

class Integer
def factors
factors = factor #{self.abs}.split(’ ')[1…-1].map {|i| i.to_i}
h = Hash.new(0); factors.each {|f| h[f] +=1}; h.to_a.sort
end

def primality?
return true if factor #{self.abs}.split(’ ')[1…-1].size == 1
return false
end
end

2.0.0p247 :054 > 30409113.factors
=> [[3, 1], [7, 1], [1448053, 1]]

2.0.0p247 :055 > 6000000000000001.primality?
=> true

I used these names to not conflict with the other methods in my code
base.

Now Ruby can do REALLY BIG NUMBERS with consistent fast performance.

Since Ruby uses other system calls and dependencies anyway, I don’t see
where this should be a problem (technically or politically), especially
for the enormous performance gains. This should even work for Windoze
builds, as they use *nix emulators.

Jabari Zakiya