Calcul de modulos

Publié le par JJ

Calculer un modulo

rappel mathématique:

Le modulo est une opération de base dans le calcul cryptographique et des mathématiques sur les entiers: un modulo a en effet des propriétés mathématiques intéressantes et très étudiées depuis très longtemps.

Congruance et modulo sont des concepts proches. Formelement la condruance est définie par: par y mod x = (y+a*x) mod x. Le modulo est quant à lui est le reste de la division entière: 0 < b < x, (a*x+b) mod x = b .

Comment calculer:

On peut donc préparer deux façon de calculer le modulo: la façon naïve et la façon sioux.

La façon naïve consiste à se rappeler que les congruances sont définies à une constante près. Si on ajoute / soustrait une constante alors on atteint un algorithme qui colle à la définition, qui est sans doute le plus simple à démontrer. Cette manoeuvre est cependant très couteuse en calculs dès que a (dans la formule (a*x+b) mod x) est grand.

La facon la plus sioux est d'utilisé la propriété "reste de la division". On verra que ce reste se calcule très simplement et rapidement.

Le langage C offre un opérateur tout fait. On verra comment il est calculé !

Un bout de code:

#include < stdio.h >
#include < stdlib.h >
#include < sys/time.h >
#include < string.h >
struct timeval tim;
double t1, t2;

/* pour demarer le décompte on ajoute à son code */
void chrono_start(){
gettimeofday(&tim, NULL);
t1=tim.tv_sec+(tim.tv_usec/1000000.0);
}

/* pour arreter le décompte un sime appel à stop suffit */
double chrono_stop(){
 gettimeofday(&tim, NULL);
 t2=tim.tv_sec+(tim.tv_usec/1000000.0);
 return t2 - t1;
}

 /** le modulo avec une soustraction */
int modulo_sou(int a, const int b){
 do{
 a = a-b;
 }while( a >= b );
 return a+b;
 }

 /** le modulo avec une addition */
 int modulo_som( const int a, int b){
 int tmp = b ;
 while( tmp < a ){
  tmp=tmp + b;
}
return a - tmp +b;
}

 /** le modulo avec une division */
int modulo_div(int a, int b){
 int tmp = a/b;
 return a - b*tmp;
}


/** le modulo avec l'operateur */
int modulo_ope(int a, int b){
 return a % b;
 }

/** */
double test_ope(int tab[], int round){
 double t;
 int a,i;
 chrono_start();
 for ( a = 0; a < 64; a++){
  for ( i = 1; i < round; i++){
  tab[i]=modulo_ope(i,7+a);
  }
 }
 t = chrono_stop();
 for ( i = 1; i < round; i++){a = tab[i];}
 return t/64;
 }

/** */
double test_div(int tab[], int round){
 double t;
 int a,i;
 chrono_start();
 for ( a = 0; a<64; a++){
 for ( i = 1; i < round; i++){
 tab[i]=modulo_div(i,7+a);
 }
 }
 t = chrono_stop();
 for ( i = 1; i < round; i++){a = tab[i];}
 return t/64;
 }
/** */
void affiche(int a){
 printf("résultat: %d.n",a);
}
/*
 printf("operateur ");
affiche(modulo_ope(177,200));
 printf("division ");
affiche(modulo_div(177,200));
 printf("somme ");
affiche(modulo_som(177,200));
 printf("soustration ");
affiche(modulo_sou(177,200));
*/

int main(void){
 const int MAX = 2090000;
 int tab[MAX+1];
 int round;
 printf("< table style="border: 1px solid gray;">n");
 printf("< tr >nt< td>nombre d'essais< / td >nt< td >operateur %%< / td >nt< td >perso< / td >n< / tr >n");
 round = 500; printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 5000;
 printf("< tr >nt< td > %d < / td >n",round)
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 50000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 50000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< /td >n", test_ope(tab,round));
 printf("t< td > %f< /td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 500000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n"); round = 1000000;
printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = 2000000;
 printf("< tr >nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n");
 round = MAX;
 printf("< tr>nt< td > %d < / td >n",round);
 printf("t< td > %f< / td >n", test_ope(tab,round));
 printf("t< td > %f< / td >n", test_div(tab,round));
 printf("< / tr >n"); printf("< / table >n");
 return 0;
}

On note que dans ce code la sortie est formatée en xhtml avec des espaces supplémentaires à cause de l'éditeur, pareil pour les \n qui sont mangés en 'n' ... bref.

Résultats

Ci dessous sans l'optimisation, l'exécution du code donne les résultats suivants. Les valeurs sont à comprendre relativement les unes aux autres et non pas de réelle valeurs intrisèques

J'ai décidé de ne pas montrer les résultats d'exécution des fonctions modulo_sou(int a, const int b) modulo_som( const int a, int b) car ses deux algo issues de la méthode naïve n'ont pas de résultats dans des temps raisonnables (complexité polynomiale de degré deux).

sans l'optimisation de code, les temps d'exécutions sont:

nombre d'essais operateur % perso
500 0.000016 0.000015
5000 0.000225 0.000331
50000 0.001766 0.001723
50000 0.001778 0.001721
500000 0.015320 0.016057
1000000 0.030472 0.031897
2000000 0.060813 0.063651
2090000 0.063432 0.066419

avec l'optimisation de code -O3, les temps d'exécutions sont

nombre d'essais operateur % perso
500 0.000011 0.000012
5000 0.000110 0.000124
50000 0.001305 0.001383
50000 0.001282 0.001378
500000 0.011527 0.012917
1000000 0.022844 0.025595
2000000 0.045422 0.050982
2090000 0.047352 0.053670

Attention! avec l'optimisation on rencontre un problème: le code inutile est supprimé. (le compilateur détecte les initialisations de variable qui ne sont pas réutilisée ). Ainsi pour lutter contre cette comportement on ajoute la ligne:

for ( i = 1; i < round; i++){a = tab[i];} 

Publié dans Divers

Commenter cet article

akim 27/03/2008 23:13

ca sert à rien ce code!