<div dir="ltr">The divMod implementation of the standard library is indeed horribly slow. If you need fast certified divMod (and gcd) you can check out the implementation in the agda-prelude library [1].<div><br></div><div>/ Ulf</div><div><br></div><div>[1] <a href="https://github.com/UlfNorell/agda-prelude/tree/master/src/Numeric/Nat">https://github.com/UlfNorell/agda-prelude/tree/master/src/Numeric/Nat</a></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 19, 2017 at 9:24 PM, Sergei Meshveliani <span dir="ltr"><<a href="mailto:mechvel@botik.ru" target="_blank">mechvel@botik.ru</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Dear Standard library developers,<br>
<br>
I test<br>
(suc n) mod (suc (suc n))<br>
where<br>
mod = Data.Nat.DivMod.mod<br>
<br>
for n = 123456789.<br>
<br>
The result is correct (and trivial), but it takes ** 6 seconds **<br>
on a 3 GHz machine.<br>
It is written in Data.Nat.DivMod that _mod_ is implemented via<br>
Agda.Builtin.Nat.mod-helper.<br>
<br>
Probably, this means that it relies on something like `mod' of Haskell<br>
standard library implemented in GHC.<br>
But `mod' of GHC computes this in less than 0.0001 sec<br>
(somewhat one machine command for division of two macrodigits).<br>
<br>
Currently the Nat arithmetic in Agda Standard library is fast because it<br>
is via built-ins. But divMod is also of important arithmetic.<br>
What about divMod ?<br>
For example, arithmetic of rational numbers rely on gcd for Nat, and gcd<br>
relies on mod (divMod).<br>
<br>
What is happening there?<br>
<br>
Regards,<br>
<br>
------<br>
Sergei<br>
<br>
______________________________<wbr>_________________<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" rel="noreferrer" target="_blank">https://lists.chalmers.se/<wbr>mailman/listinfo/agda</a><br>
</blockquote></div><br></div>