<div dir="ltr"><span style="font-size:16px">Thank you, Matthias. The fix you propose is beyond my programming skills and my interest level. But you've given me insight into where the problem lies. I think the memory blowup problem may be the result of the "rho/1" procedure being coded in such a way that it isn't tail recursive. That problem, I can tackle.</span><div style="font-size:16px"><br></div><div style="font-size:16px">Best regards,</div><div style="font-size:16px">Robert Buckley</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 14, 2015 at 10:39 AM, Matthias Guedemann <span dir="ltr"><<a href="mailto:matthias@guedemann.org" target="_blank">matthias@guedemann.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Robert,<br>
<span class="im HOEnZb"><br>
> -disable-most-grades option. I am very disappointed with the slowness<br>
> of the procedures written for Mercury, and sometimes memory usage<br>
> begins to blow up (slowly, over time as the process runs. Some of<br>
> these run overnight). When I say I'm disappointed in the Mercury<br>
> performance, I mean that by comparison with similar procedures I run<br>
> written in Prolog, Erlang, Haskell, and Scheme, Mercury is much too<br>
> slow, often taking 10 times or more as much time to complete. The<br>
> Mercury runs I've made (not including those abandoned because of<br>
> memory blowup) do complete and get correct results, but take way too<br>
> much time to run.<br>
<br>
</span><span class="im HOEnZb">In my opinion, the principal reason for this is that the Mercury<br>
implementation for big integers is written in pure Mercury. In contrast,<br>
Haskell calls GMP via FFI. GMP is a highly optimized library written in<br>
C. For the other languages, it depends on the implementation, but very<br>
likely they also use GMP or a similar library directly. The downside of<br>
using GMP or another library is the added dependency, of course.<br>
<br>
</span><span class="im HOEnZb">> Does anyone have any suggestions for speedup, other than "Avoid using<br>
> Mercury for this purpose"? I'm attaching copies of the source code of<br>
> the procedures that run so slowly.<br>
<br>
</span><div class="HOEnZb"><div class="h5">A while ago, I implemented a faster multiplication algorithm for Mercury<br>
(parallel for asm_fast.par.gc.stseg), but IIRC Miller-Rabin requires<br>
primarily fast modulo and division. I am interested in optimizing these<br>
routines, too, but have not yet put any work into it. In my opinion,<br>
there is potential in optimizing the division and modulo algorithms and<br>
maybe also in optimizing the representation of big integers (currently<br>
lists of 14 bit digits), but to be honest, I think that reaching the<br>
speed of anything based directly on GMP is unrealistic.<br>
<br>
Best regards,<br>
Matthias<br>
</div></div></blockquote></div><br></div>