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:
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'
[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.
[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.
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.
$ 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:
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.
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
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.