[Agda] divMod variant

Serge D. Mechveliani mechvel at botik.ru
Sun Sep 16 14:29:59 CEST 2012


People,
the archive  http://botik.ru/pub/local/Mechveliani/agdaNotes/ddivRem.zip
contains 
* the implementation  DDivRem.agda  for division with remainder for   
  unary coded natural numbers,
* the test module  Main.agd,
* notes  notes.agda  and questions on this program 

-- all this is for  Agda-2.3.0.1 + lib-0.6.  

Instead of
  data DivMod : Nat -> Nat -> Set where
    result : {divisor : Nat} (q : Nat) (r : Fin divisor) ->
             DivMod (toNat r + q * divisor) divisor
of Standard
divRem  has the result type

  record NatDivRem (dividend divisor : Nat) : Set where   
    field
      quot  : Nat   
      rem   : Nat
      proof : (rem < divisor) x (dividend == (quot * divisor + rem)) 

  natDivRem : (dividend : Nat)     -> (divisor : Nat) -> 
              False (divisor =? 0) -> NatDivRem dividend divisor

(For this letter I denote  \bn ->  Nat,  \equiv ->  ==,   \=? ->  =? ). 

It also builds the needed proofs.
In its internal loop, it processes the additional arguments for
* the counter for subtractions, in order to help the termination proof,
* the current proof for   m == (q * n' + r),  in order to provide an
  incremental proof, to save the cost.

I shall be grateful to you if you look into (a quite small code in) 
DDivRem.agda  and give notes.  
The mark  `debug'  in comments points at questionable places.

I tried  divRem m 5   for several values of  m  (see Main.agda).
I understand that
* probably,  Agda-2.3.0.1 + lib-0.6  does not at all aim at performance,
* unary coded naturals  is not an appropriate test for investigating  
  the performance points;
  I think, say, sorting a long character list fits better.

Still consider the following.
1. The time cost in  divRem  looks like  O(m^2).
2. The version "-skipProofs" has the same timing.
   Why does it look as  O(m^2) ?
   A short comment in  notes.agda  argues for that it must be  O(m).

Thanks,

------
Sergei


More information about the Agda mailing list