<div dir="ltr">A small addition: There is also an intermediate implementation of the original three modules. The intermediate uses memoized integers, the standard integer library, and a rewriting of all the main predicates in functional form so that they look very much like the _mpm files, provided above. The intermediate exhibits some speedup over the original. The _mpm files run, on average, about 13.5 times faster than the intermediate. The improvement is never less than 10 times and, depending upon the size of the number being factored, and the number and size of the factors, can run faster than 13.5 times.<div><br></div><div>Here are some examples in which the composite to be factored is a product of two adjacent primes. The first line shows the composite. The second line shows one of the two prime factors, the time required for the intermediate integer version to find that factor, the time for the mp_int version to find the same factor, and a ratio of the two times.</div><div><br></div><div><div><font face="monospace, monospace">% 15241578784264594783019</font></div><div><font face="monospace, monospace">% 123456789133 in 27.8 Sec/2.70 Sec/10.3</font></div><div><br></div><div><div><font face="monospace, monospace">% 15241578780677434318061334559</font></div><div><font face="monospace, monospace">% 123456789123487 in 2428.1/170.5 Sec/14.2</font></div></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace"><div>% 152415787806737799971032802318399</div><div>% 12345678912345721 in 8415.8 Sec/512.0 Sec/16.4</div></font></div><div><br></div><div>As you can see, there is a considerable performance improvement.</div><div><br></div><div>Robert Buckley</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, May 16, 2015 at 8:54 AM, Delmas Buckley <span dir="ltr"><<a href="mailto:rbuckley@ieee.org" target="_blank">rbuckley@ieee.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>On April 14 I wrote complaining that Mercury 14.01.1 is too slow when factoring large composite numbers into their prime factors. Several suggestions for improvement were made by users and these were incorporated into my Mercury programs resulting in some slight improvement. And then Matthias Guedemann got involved and, over a period of about 25 days, he created a faster bignum library that he calls mp_int. Using mp_int in place of the standard Mercury integer library has increased the speed of factoring by better than an order of magnitude. For comparison purposes I have attached the new modules corresponding to those attached to my original post. Also attached is the mp_int module and a module, mp, in which numerous integers, large and small are defined and memoized.<br><br></div>Best regards,<br></div>Robert Buckley<br></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 14, 2015 at 9:38 AM, Delmas Buckley <span dir="ltr"><<a href="mailto:rbuckley@ieee.org" target="_blank">rbuckley@ieee.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hello -- I learned enough Mercury to translate a Miller-Rabin primality test and construct a process using that test to implement a prime factorization of large composite numbers (large being < 65 decimal digits). I run this in Mercury 14.01.1 under Ubuntu 64-bit running on an Apple Mac Pro using the Yosemite OS and VMWare's Fusion. When I installed Mercury into Ubuntu I used the --disable-most-grades option. <u>I am very disappointed with the slowness</u> of the procedures written for Mercury, and sometimes memory usage begins to blow up (slowly, over time as the process runs. Some of these run overnight). When I say I'm disappointed in the Mercury performance, I mean that by comparison with similar procedures I run written in Prolog, Erlang, Haskell, and Scheme, Mercury is much too slow, often taking 10 times or more as much time to complete. The Mercury runs I've made (not including those abandoned because of memory blowup) do complete and get correct results, but take way too much time to run.<div><br></div><div>Does anyone have any suggestions for speedup, other than "Avoid using Mercury for this purpose"? I'm attaching copies of the source code of the procedures that run so slowly.</div><div><br></div><div>Best regards,</div><div>Robert Buckley</div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>