From: Kiswono Prayogo Date: 2013-07-31T04:14:58+09:00 Subject: Re: Faster primality testing and factorization methods in Ruby --047d7bd76ec4af1bc704e2bf5673 Content-Type: text/plain; charset=UTF-8 $ 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. 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%E2%80%93Rabin_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 --047d7bd76ec4af1bc704e2bf5673 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
$ ruby --version
ruby 2.0.0p247 (2013-06-27 revision 41674) = [i686-linux]

$ jruby --version
jrub= y 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 in= formation utility, Version 4.1.0 Build 20120831
Copyright (C) 200= 5-2012 Intel Corporation. =C2=A0All rights reserved.

=3D=3D=3D=3D=3D =C2=A0Processor composition =C2=A0=3D=3D=3D=3D=3D
Processor name =C2=A0 =C2=A0: AMD Phenom(tm) 9850 Quad-Core Processor =C2= =A0
Packages(sockets) : 1
Cores =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 : 4
Processors(CPUs) =C2=A0: 4
Cor= es per package : 4
Threads per core =C2=A0: 1

$ uname -a
Linux 3.9.9-1-pae #1 SMP PREEMPT Mon Jul 8 17:38:58 EDT 2013 i686 GNU/Li= nux
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.. (tr= ying 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%E2%80%93Rabin_pri= mality_test
http://mathworld.wolfram.com/Rabin-MillerStrongPseud= oprimeTest.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-Prim= e-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 --047d7bd76ec4af1bc704e2bf5673--