[Agda] Data.Rational

Sergei Meshveliani mechvel at botik.ru
Wed Mar 12 17:45:15 CET 2014


On Wed, 2014-03-12 at 14:20 +0100, Noam Zeilberger wrote:
> 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 https://lists.chalmers.se/pipermail/agda/2012/003988.html, as
> well as https://code.google.com/p/agda/issues/detail?id=426).
>

As far as  Nat  is represented in _unary system_, it is senseless to
consider efficiency of operations on large Nat or Integer values.

I have tried arithmetic in  Integer/(m)  ("modulo m")  in Agda  for  
m < 20.
The example applies about 100.000 times (partial) division in
Integer/(m).  Each such division applies the  extended GCD algorithm
extGCD  (extended Euclidean method).
I program  extGCD  for Integer (in Agda) by new. 

And all this loop is fast, somewhat comparable with an Haskell program
under GHC.

If  m  is bound by  9000 instead of 20,  then this will be different,
the unary system will not do, probably.

May be, when I go further with another examples, this call by name could
bite me. It is interesting to see.
The matter is that providing proofs takes a great effort, so that the
advance in programming methods is slow.

Regards,

------
Sergei



More information about the Agda mailing list