<div dir="ltr">For what it's worth (which granted is not much given my limited experience), the performance issues I ran into really had more to do with Agda in general than with a specific strategy for rationals (hence my eventual approach of giving up and calling the FFI). šIn particular, Euclid's algorithm was taking an absurdly long time to run, apparently because of Agda's call-by-name evaluation strategy (see <a href="https://lists.chalmers.se/pipermail/agda/2012/003988.html">https://lists.chalmers.se/pipermail/agda/2012/003988.html</a>, as well as <a href="https://code.google.com/p/agda/issues/detail?id=426">https://code.google.com/p/agda/issues/detail?id=426</a>).<div>
<br></div><div>Noam</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Mar 12, 2014 at 2:04 PM, Sergei Meshveliani <span dir="ltr"><<a href="mailto:mechvel@botik.ru" target="_blank">mechvel@botik.ru</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="">On Wed, 2014-03-12 at 16:37 +0400, Sergei Meshveliani wrote:<br>
> On Tue, 2014-03-11 at 20:58 +0100, Andreas Abel wrote:<br>
><br>
> > I have no personal experience, but I listened to a talk by Anders<br>
> > M"ortberg who presented his joint work with Cyril Cohen. He said that<br>
> > if you want to be efficient you should *not* try to cancel the common<br>
> > primfactors in fractions each time. šThe cost of making things<br>
> > coprime repeatedly seems to be higher than computing with larger<br>
> > integers.<br>
><br>
> My experience is very different.<br>
><br>
</div>> [..]<br>
<br>
<br>
If one computes š m/n + m'/n' š for large random integers šm,n,m',n',<br>
than it is better to delay cancelling by šgcd.<br>
Because the average gcd for two large random integers occurs small.<br>
<br>
Due to this consideration, I had once (in about 1990) an illusion of<br>
that the (Delay) approach is good.<br>
<br>
But in most practical computation methods, the current šm šand šn šare<br>
not random, they are somehow accumulated from some root in a long loop.<br>
<br>
This is why (C) occurs more practicable than (Delay).<br>
I cannot prove this, I only provide practical examples and<br>
considerations in my previous letter.<br>
<br>
Just follow šD.Knuth: šin š m/n + m'/n'<br>
<br>
the first step is to find šgcd n n' ...<br>
<br>
Regards,<br>
<br>
------<br>
Sergei<br>
<div class=""><br>
<br>
> 1. GHC Rational<br>
> ---------------<br>
> As I recall, I tried this in earlier GHC versions (in 1990-ies)<br>
><br>
> š šsumF n = š1 + 1/2 + 1/3 + ... + 1/n, š with taking large šn<br>
><br>
</div>> [..]<br>
<div class=""><div class="h5"><br>
<br>
_______________________________________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" target="_blank">https://lists.chalmers.se/mailman/listinfo/agda</a><br>
</div></div></blockquote></div><br></div></div>