[Agda] is divMod slow?

Sergei Meshveliani mechvel at botik.ru
Mon Jun 19 21:24:14 CEST 2017


Dear Standard library developers,

I test  
       (suc n) mod (suc (suc n))
       where
       mod = Data.Nat.DivMod.mod

for  n = 123456789.

The result is correct (and trivial), but it takes   ** 6 seconds **   
on a 3 GHz machine.
It is written in  Data.Nat.DivMod that _mod_ is implemented via
Agda.Builtin.Nat.mod-helper.

Probably, this means that it relies on something like `mod' of Haskell
standard library implemented in GHC.
But `mod' of GHC computes this in less than 0.0001 sec
(somewhat one machine command for division of two macrodigits).   

Currently the Nat arithmetic in Agda Standard library is fast because it
is via built-ins. But divMod is also of important arithmetic. 
What about  divMod ?
For example, arithmetic of rational numbers rely on gcd for Nat, and gcd
relies on mod (divMod).

What is happening there?

Regards,

------
Sergei



More information about the Agda mailing list