mod

mod.c

/* mod

Profil
###### 

mod: entier_nat x entier_nat -> entier_nat

Exemples
###### 

mod(10,4) = 2  // le reste de la division entiere de 10 par 4 (10=2*4+2)
mod(10,0) = Erreur

10 = 2*4 + 2 => 2 = 10-4*2

mod(10,4) = mod(10-4, 4) 
          = mod(6, 4)
          = mod(6-4, 4)
          = mod(2, 4)
          = 2 car 2 < 4

Axiomes
###### 

mod(n, zero()) = Erreur
mod(n, succ(m)) = si_alors_sinon_finsi( n < succ(m), n, mod(n-succ(m), succ(m)) )

Algorithme recursif
###### 

fonction mod(a: entier_nat, b: entier_nat): entier_nat
debut
 | si est_nul(b)          
 | -------------          
 |                         | alors Erreur_Entier_Naturel        
 | finsi                  
 | si plus_petit_que(a, b)
 |                         | alors retourner a                  
 |                         | sinon retourner mod(moins(a, b), b)
 | finsi                  
fin

Algorithme iteratif
###### 

fonction mod(a: entier_nat, b: entier_nat): entier_nat
debut
 | si est_nul(b)                        
 | -------------                        
 |                                       | alors Erreur_Entier_Naturel
 | finsi                                
 | tantque non plus_petit_que(a,b) faire
 |                                       | a := moins(a, b)           
 | fintantque                           
 | retourner a                          
fin

*/

#include `<stdio.h>`

#include "entier_nat.h"
#include "plus_petit_que.h"

#include "moins.h"

ENTIER_NAT mod_recursif(ENTIER_NAT a, ENTIER_NAT b)
{
   if (est_nul(b))
   {
      Erreur_Entier_Nat();
   }
   if (plus_petit_que_recursif(a, b))
   {
     return a;
   }
   else
   {
     return mod_recursif(moins_recursif(a,b), b);
   }
}

ENTIER_NAT mod_iteratif(ENTIER_NAT a, ENTIER_NAT b)
{
   if (est_nul(b))
   {
      Erreur_Entier_Nat();
   }
   while (! plus_petit_que_iteratif(a, b))
   {
      a = moins_iteratif(a, b);
   }
   return a;
}

void test_recursif(ENTIER_NAT a, ENTIER_NAT b)
{
    printf("recursif: mod(%d, %d) = %d\n", a, b, mod_recursif(a, b));
}
void test_iteratif(ENTIER_NAT a, ENTIER_NAT b)
{
    printf("iteratif: mod(%d, %d) = %d\n", a, b, mod_iteratif(a, b));
}

int main()
{
   test_recursif(10,4);
   test_iteratif(10,4);
   test_recursif(101,14);
   test_iteratif(101,14);
}