[Agda] built-in divMod

Sergei Meshveliani mechvel at botik.ru
Wed Mar 20 19:34:13 CET 2019


Dear standard library developers,

As I understand, 
(1) the certified Nat arithmetic is exponentially slow, due to unary 
    representation,
(2) due to this, it is added a non-certified built-in arithmetic for 
    Nat, including the predicates _≡ᵇ_; _<ᵇ_ returning a Boolean result.

But is there a fast built-in  divMod  for Nat ?

For I do not see, how (2) can help with fast GCD, and hence with a fast
_rational_ number arithmetic over Nat and Integer.

In scientific computation rational numbers are used as widely as
Integer, strongly needed. 

On the other hand, a fast divMod will allow us to program in Agda a fast
gcd   and fast rational arithmetic over Nat (Integer) 
(if I am not missing something, for this is difficult to make sure
without trying to write the code).

This (divMod a b b\=0)  can, say, return  (quot , rem) : Nat x Nat,
and the proofs for 
               T (a ≡ᵇ a * quot + rem),   T (rem <ᵇ b)  

can be postulated in the library.
As many non-certified things for Nat are already included, why do not
add built-in  divMod ?  I hope this will be the last one.
Probably it is somewhere in the  gmp  library (used in GHC ?).  

Am I missing something?

------
Sergei



More information about the Agda mailing list