From: Kiswono Prayogo <kiswono@...>
Date: 2013-07-30T21:58:24+09:00
Subject: Re: Faster primality testing and factorization methods in Ruby

--047d7bd76ec4f9920604e2ba2945
Content-Type: text/plain; charset=UTF-8

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

--047d7bd76ec4f9920604e2ba2945
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

ah yeah, on 32-bit it&#39;s really-really slow.. (trying on my more powerfu=
l PC instead of my old laptop for now)<div><br></div><div>soo.. the conclus=
ion would be: Miller-Rabin is the fastest</div><div><br></div><div><a href=
=3D"http://pastie.org/8189939">http://pastie.org/8189939</a></div>
<div><br></div><div>ruby: 343s</div><div>jruby: 284s<br><div><br></div><div=
><br><br><div class=3D"gmail_quote">On Tue, Jul 30, 2013 at 12:05 PM, Matth=
ew Kerwin <span dir=3D"ltr">&lt;<a href=3D"mailto:lists@ruby-forum.com" tar=
get=3D"_blank">lists@ruby-forum.com</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">I get the following, on an Ubuntu 64-bit VM =
(edited to fit the page<br>
width):<br>
<br>
prime.rb:44: warning: assigned but unused variable - rescnt<br>
prime.rb:85: warning: assigned but unused variable - rescnt<br>
prime.rb:119: warning: assigned but unused variable - rescnt<br>
prime.rb:159: warning: assigned but unused variable - rescnt<br>
prime.rb:165: warning: assigned but unused variable - modk<br>
prime.rb:212: warning: shadowing outer local variable - p<br>
Rehearsal -------------------------------------------------<br>
<div class=3D"im">prime tests for P =3D 20000000000000003<br>
</div>Miller-Rabin =C2=A0 =C2=A00.000000 =C2=A0 0.000000 =C2=A0 0.000000 ( =
=C2=A00.000761)<br>
primzp7? =C2=A0 =C2=A0 =C2=A0 =C2=A02.290000 =C2=A0 0.000000 =C2=A0 2.29000=
0 ( =C2=A02.294709)<br>
primzp7a? =C2=A0 =C2=A0 =C2=A0 0.970000 =C2=A0 0.000000 =C2=A0 0.970000 ( =
=C2=A00.971033)<br>
primzp7b? =C2=A0 =C2=A0 =C2=A0 0.980000 =C2=A0 0.000000 =C2=A0 0.980000 ( =
=C2=A00.978331)<br>
primzp? 13 =C2=A0 =C2=A0 =C2=A01.900000 =C2=A0 0.010000 =C2=A0 1.910000 ( =
=C2=A01.905374)<br>
primzp? 17 =C2=A0 =C2=A0 =C2=A01.870000 =C2=A0 0.000000 =C2=A0 1.870000 ( =
=C2=A01.877343)<br>
primzpa? 13 =C2=A0 =C2=A0 3.200000 =C2=A0 0.050000 =C2=A0 3.250000 ( =C2=A0=
3.255519)<br>
primzpa? 17 =C2=A0 =C2=A0 3.100000 =C2=A0 0.040000 =C2=A0 3.140000 ( =C2=A0=
3.127512)<br>
factorzp 13 =C2=A0 =C2=A0 1.940000 =C2=A0 0.000000 =C2=A0 1.940000 ( =C2=A0=
1.949376)<br>
factorzp 17 =C2=A0 =C2=A0 1.870000 =C2=A0 0.000000 =C2=A0 1.870000 ( =C2=A0=
1.870068)<br>
prime? [ruby lib]<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 26.550000 =C2=A0 0.=
010000 =C2=A026.560000 ( 26.569130)<br>
prime_division [ruby lib]<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 29.570000 =C2=A0 0.=
000000 =C2=A029.570000 ( 29.585618)<br>
---------------------------------------- total: 74.350000sec<br>
<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 user =C2=A0 =C2=A0 =
system =C2=A0 =C2=A0 =C2=A0total =C2=A0 =C2=A0 =C2=A0 =C2=A0real<br>
<div class=3D"im">prime tests for P =3D 20000000000000003<br>
</div>Miller-Rabin =C2=A0 =C2=A00.000000 =C2=A0 0.000000 =C2=A0 0.000000 ( =
=C2=A00.000562)<br>
primzp7? =C2=A0 =C2=A0 =C2=A0 =C2=A02.320000 =C2=A0 0.000000 =C2=A0 2.32000=
0 ( =C2=A02.319329)<br>
primzp7a? =C2=A0 =C2=A0 =C2=A0 0.980000 =C2=A0 0.000000 =C2=A0 0.980000 ( =
=C2=A00.974572)<br>
primzp7b? =C2=A0 =C2=A0 =C2=A0 0.980000 =C2=A0 0.000000 =C2=A0 0.980000 ( =
=C2=A00.984110)<br>
primzp? 13 =C2=A0 =C2=A0 =C2=A01.920000 =C2=A0 0.000000 =C2=A0 1.920000 ( =
=C2=A01.923894)<br>
primzp? 17 =C2=A0 =C2=A0 =C2=A01.880000 =C2=A0 0.010000 =C2=A0 1.890000 ( =
=C2=A01.884494)<br>
primzpa? 13 =C2=A0 =C2=A0 3.080000 =C2=A0 0.030000 =C2=A0 3.110000 ( =C2=A0=
3.109670)<br>
primzpa? 17 =C2=A0 =C2=A0 3.010000 =C2=A0 0.020000 =C2=A0 3.030000 ( =C2=A0=
3.028406)<br>
factorzp 13 =C2=A0 =C2=A0 1.910000 =C2=A0 0.000000 =C2=A0 1.910000 ( =C2=A0=
1.917429)<br>
factorzp 17 =C2=A0 =C2=A0 1.880000 =C2=A0 0.000000 =C2=A0 1.880000 ( =C2=A0=
1.875251)<br>
prime? [ruby lib]<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 25.170000 =C2=A0 0.=
000000 =C2=A025.170000 ( 25.177364)<br>
prime_division [ruby lib]<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 28.270000 =C2=A0 0.=
020000 =C2=A028.290000 ( 28.298034)<br>
<br>
[Kiswono Prayogo, note the durations, especially in the core methods;<br>
10s is too short for calculating primality of large numbers. Have<br>
patience.]<br>
<br>
Note that all the warnings can be resolved by removing the unused<br>
definitions, and renaming that &#39;p&#39; variable in the block. =C2=A0The=
y&#39;re<br>
messy, but unimportant.<br>
<div class=3D"HOEnZb"><div class=3D"h5"><br>
--<br>
Posted via <a href=3D"http://www.ruby-forum.com/" target=3D"_blank">http://=
www.ruby-forum.com/</a>.<br>
<br>
</div></div></blockquote></div><br><br clear=3D"all"><div><br></div>-- <br>=
Regards,<br>Kiswono P<br>GB
</div></div>

--047d7bd76ec4f9920604e2ba2945--