Faster primality testing and factorization methods in Ruby

ruby-talk
#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:

Attachments:
http://www.ruby-forum.com/attachment/8542/Improved_Primality_Testing_and_Factorization_in_Ruby.pdf
http://www.ruby-forum.com/attachment/8543/primeszp.rb

···

--
Posted via http://www.ruby-forum.com/.

#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

On Thu, Jun 27, 2013 at 10:48 AM, Jabari Z. <lists@ruby-forum.com> wrote:

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'

http://www.scribd.com/doc/150217723/Improved-Primality-Testing-and-Factorization-in-Ruby

The code rile 'primeszp.rb' is available in my github repository:
https://gist.github.com/jzakiya/455f2357cdb08f4ee1c4

Attachments:

http://www.ruby-forum.com/attachment/8542/Improved_Primality_Testing_and_Factorization_in_Ruby.pdf
http://www.ruby-forum.com/attachment/8543/primeszp.rb

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

···

--
Posted via http://www.ruby-forum.com/.

#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

···

On Tue, Jul 30, 2013 at 12:05 PM, Matthew Kerwin <lists@ruby-forum.com>wrote:

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

--
Posted via http://www.ruby-forum.com/.

--
Regards,
Kiswono P
GB

#5

Kiswono Prayogo 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:


http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

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.


···

--
Posted via http://www.ruby-forum.com/.

#6

$ 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(R) Processor information utility, Version 4.1.0 Build 20120831
Copyright (C) 2005-2012 Intel Corporation. All rights reserved.

===== Processor composition =====
Processor name : AMD Phenom(tm) 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

···

On Tue, Jul 30, 2013 at 9:58 PM, Jabari Z. <lists@ruby-forum.com> wrote:

Kiswono Prayogo 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:

https://en.wikipedia.org/wiki/Miller–Rabin_primality_test
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

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.

http://www.scribd.com/doc/73384039/Ultimate-Prime-Sieve-Sieve-Of-Zakiya
http://www.scribd.com/doc/73385696/The-Sieve-of-Zakiya

--
Posted via http://www.ruby-forum.com/.

--
Regards,
Kiswono P
GB

#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: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
   # Ruby Rosetta Code:
http://rosettacode.org/wiki/Miller-Rabin_primality_test
   # 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

--
Posted via http://www.ruby-forum.com/.

#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

···

--
Posted via http://www.ruby-forum.com/.