[Agda] practical integer/rational arithmetic?
wren ng thornton
wren at freegeek.org
Wed May 9 23:30:37 CEST 2012
On 5/9/12 11:55 AM, Nils Anders Danielsson wrote:
> On 2012-05-09 17:28, Jacques Carette wrote:
>> 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.
>
> In GHCi, on an older machine:
>
> Prelude> let fac n = product [1..n] in gcd (fac (fac (fac 3)) ^ 5)
> (2^26892 + 1)
> 1774001
> (0.10 secs, 39859272 bytes)
FWIW, with numbers this large it's worth using a sophisticated
implementation of factorial. Using the one in exact-combinatorics[1] I
get less than half that time in ghci:
Prelude> :m +Math.Combinatorics.Exact.Factorial
Prelude Math.Combinatorics.Exact.Factorial>
gcd (factorial (factorial (factorial 3))^5) (2^26892 + 1)
Loading package exact-combinatorics-0.2.0 ... linking ... done.
1774001
(0.04 secs, 41337232 bytes)
GHC = 6.12.1 (32-bit because of OSX)
OS = OSX 10.5.8
ARCH = 2.8 GHz Intel Core 2 Duo
[1] http://hackage.haskell.org/package/exact-combinatorics
--
Live well,
~wren
More information about the Agda
mailing list