<div dir="ltr">For what it&#39;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&#39;s algorithm was taking an absurdly long time to run, apparently because of Agda&#39;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">&lt;<a href="mailto:mechvel@botik.ru" target="_blank">mechvel@botik.ru</a>&gt;</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>


&gt; On Tue, 2014-03-11 at 20:58 +0100, Andreas Abel wrote:<br>
&gt;<br>
&gt; &gt; I have no personal experience, but I listened to a talk by Anders<br>
&gt; &gt; M&quot;ortberg who presented his joint work with Cyril Cohen. He said that<br>
&gt; &gt; if you want to be efficient you should *not* try to cancel the common<br>
&gt; &gt; primfactors in fractions each time. šThe cost of making things<br>
&gt; &gt; coprime repeatedly seems to be higher than computing with larger<br>
&gt; &gt; integers.<br>
&gt;<br>
&gt; My experience is very different.<br>
&gt;<br>
</div>&gt; [..]<br>
<br>
<br>
If one computes š m/n + m&#39;/n&#39; š for large random integers šm,n,m&#39;,n&#39;,<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&#39;/n&#39;<br>
<br>
the first step is to find šgcd n n&#39; ...<br>
<br>
Regards,<br>
<br>
------<br>
Sergei<br>
<div class=""><br>
<br>
&gt; 1. GHC Rational<br>
&gt; ---------------<br>
&gt; As I recall, I tried this in earlier GHC versions (in 1990-ies)<br>
&gt;<br>
&gt; š šsumF n = š1 + 1/2 + 1/3 + ... + 1/n, š with taking large šn<br>
&gt;<br>
</div>&gt; [..]<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>