Granted, Maple doesn't need to compute a witness of GCD-ness along the way :)<div><br></div><div>I think James's new witness-carrying GCD takes about 5 seconds to normalize the GCD of 14303480934 and 44934319042, which seems pretty respectable. If you want to see the code, it's at <a href="https://github.com/xplat/potpourri/tree/master/Fast">https://github.com/xplat/potpourri/tree/master/Fast</a></div>
<div><br></div><div>Dan<br><br><div class="gmail_quote">On Wed, May 9, 2012 at 11:28 AM, Jacques Carette <span dir="ltr"><<a href="mailto:carette@mcmaster.ca" target="_blank">carette@mcmaster.ca</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>On 09/05/2012 11:06 AM, Noam Zeilberger wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
For<br>
example, computing the gcd (Data.Nat.Gcd) of 2012 and 1984 takes about<br>
three and a half minutes on my laptop.<br>
</blockquote>
<br></div>
I can't help you with how to make Agda faster, but I can at least show you what the bar ought to be. In Maple, on a 3 year old machine, computing gcd(3!!!^5, 2^26892+1) [which is 1446241] takes 0.015 seconds. 3!!!^5 (3 factorial factorial factorial to the 5th) is a 8732 decimal digits number, while 2^26892+1 is a 17125 digit number.<br>
<br>
To get into the 3 1/2 minutes ballpark, one has to go to millions of digits.<br>
<br>
<shameless plug> The CICM conference (<a href="http://www.informatik.uni-bremen.de/cicm2012/cicm.php" target="_blank">http://www.informatik.uni-<u></u>bremen.de/cicm2012/cicm.php</a>) in Bremen hosts a lot of people whose aim is to combine correctness [via theorem proving] and efficient computation [via computer algebra]. Programming Languages are, unfortunately, sorely under-represented. Please help us! </shameless plug><span><font color="#888888"><br>
<br>
Jacques<br>
</font></span><br>
PS: Mathematica and SAGE (via PARI) would be just as fast for these computations, I just happen to be most comfortable with Maple.<div><div><br>
______________________________<u></u>_________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se" target="_blank">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" target="_blank">https://lists.chalmers.se/<u></u>mailman/listinfo/agda</a><br>
</div></div></blockquote></div><br>
</div>