Discussion :

[SteelBox]

Bonjour à tous.
J'ai encore une question...et oui encore une, je sais
j'aimerais savoir comment faire l'opération modulo en assembleur ?
Merci

[Smortex]

C'est relativement simple : il suffit de soustraire au nombre dont on veut trouver le modulo le modulo lui même et ce tant que le premier nombre est strictement suppérieur au second...

Ca donne un truc genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
DoMod:
        Sub     Ax,Bx
        Cmp     Ax,Bx
        Jnl     DoMod

Bon dev'

[Invité]

C'est relativement simple : il suffit de soustraire au nombre dont on veut trouver le modulo le modulo lui même et ce tant que le premier nombre est strictement suppérieur au second...

Les x86 ont une intruction DIV/IDIV. Ta méthode prendrais environ 20000 boucles pour trouver 65535 mod 3 !

L'instruction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 DIV source  ; source = mem ou reg

divise [edx:eax] (ou [dx:ax] selon la taille de source) par la source.
Le quotient se retrouve dans eax
Le reste=modulo dans edx.

Pour les opérations sur des nombres signé, il y a IDIV (même fonctionnement)

Pour les jeux d'instructions x86
Recherche sur www.intel.com la doc suivante:
"IA-32 Intel® Architecture Software Developer’s Manual. Volume 2: Instruction Set Reference"

A+

[Smortex]

Les x86 ont une intruction DIV/IDIV.

C'est vrai... J'avais bêtement fait l'adaptation d'un prg qui tournais sur un microcontrôleur qui ne connaissant pas les divisions

Bon dev'

[Invité]

J'avais bêtement fait l'adaptation d'un prg qui tournais sur un microcontrôleur qui ne connaissant pas les divisions

Même dans ce cas, ton code est a déconseillé si ton microcontrôleur possède des instructions SHL/SHR.
Ta méthode a une complexité O(N*ln(N)), N représentant ici les données et non leur taille comme il est habituel en complexité. Donc ce n'est pas polynomial mais exponentiel en la taille des données (qui vaut ln(N)) .

Voici un algorithme de division "binaire" de complexité O(ln(N)^2) (donc polynomial en la taille des données).
(extrait du bouquin de R. Crandall et C. Pomerance "Prime Numbers: A Computationnal Perspective" Springer Verlag)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
Entrée:  x>=0 , N>=0 
Sortie:  q=x div N , r=x mod N
 
  si N=0 alors erreur division par 0;
 
  si x=N alors 
    q=1; r=0; exit;
  sinon si x<N alors
    q=0; r=x; exit;
  end; 
 
  Préliminaire: trouver l'unique entier b tel que  N*2^b <= x < N*2^(b+1): on peut le faire avec des shifts
 
  m := N*2^b   c := 0
  pour j=0 à b faire
     c := 2*c ;
     a := x-m;
     si (a>=0) alors
        c := c + 1;
        x := a ;
     fsi
     m = m/2
  fin for
 
  si a<0 alors a=a+N;  fsi
 
  q=c;  r=a;

Ce qui donne en C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
// q <- x div N , r <- x mod N  
// on renvoie 0 en cas de division par 0,  1 sinon
int  binary_divide (int x, int N, int *q, int *r) 
{ 
int m,b,tN ; 
 
   if (N==0) return 0; 
   if (x==N) { *q=1; *r=0; return 1; } 
   if (x<N)  { *q=0; *r=x; return 1; } 
 
   b=0; tN=N; 
   while (tN<x) { b++; tN<<=1;} 
   b--; 
 
   *q=0;  m= N << b; 
 
   for (int j=0;j<=b;j++) { 
     (*q) <<= 1 ; 
     *r = x-m; 
     if ((*r)>=0) { (*q)++; x=*r; } 
     m >>= 1 ; 
   } 
   if ((*r)<0) (*r) += N; 
 
   return 1; 
}

Il n'y a plus qu'a transcrire en ASM. La gestion des divisions signés ce fait de la même façon en gérant le signe indépendamment.

PS: J'ai testé le code C ci-dessus. Il est seulement entre 2 à 4 fois plus lent (selon les inputs il est même plus rapide quand x et N ont le même nombre de bits !) que l'utilisation du code asm suivant (on n'utilise pas une fonction C avec *q=x/N; *r=x%N; car le compilateur utilise deux divisions !!!)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int  normal_divide (int x, int N, int *q, int *r) 
{ 
 __asm{
       xor  eax , eax
       mov  ecx , N
       test ecx,ecx
       jz FIN
       xor  edx , edx  
       mov  eax , x        
       div  ecx
       mov  ecx , q
       mov [ecx] , eax
       mov  ecx , r
       mov [ecx] , edx
       mov eax , 1
 FIN:
}
}

Avec VC6 comme compilo et un Athlon comme proc.

A+

[Invité]

Pour ceux que ça interesse (malgré la présence de div sur x86) voilà le code asm de binary_divide pour x86:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
__declspec(naked) int asm_binary_divide ( int x, int N, int *q, int *r) 
{ 
  __asm {
              push ebp
              mov  ebp , esp
              push ebx 
              push esi
              push edi  
 
              xor  eax , eax        // valeur de retour 0 par défaut
 
              mov  ebx , x          
              mov  edx , N
              test edx , edx       // N=0 <- ERREUR
              jz   FIN_DIV 
 
              cmp  ebx , edx
              jnz  XdifferentN 
 
              mov  eax , 1          // x=N -> q=1 r=0
              mov  ecx , q
              mov  [ecx] , eax
              mov  ecx , r
              mov  dword ptr [ecx] , 0   
              jmp  FIN_DIV
 
XdifferentN:  ja XsuperieurN
                                    // x<N  -> q=0 r=x
              mov ecx , q
              mov [ecx] , eax
              mov eax , 1
              mov ecx , r
              mov [ecx] , ebx
              jmp FIN_DIV
                                   // eax <-> tN , ecx <->b 
XsuperieurN:  xor  ecx , ecx
              mov  eax , edx
              cmp  eax , ebx       // tN >= x ?
              jae  FIN_LOOP_B      // -> FIN_LOOP_B
ALIGN 8  
              LOOP_B:  shl eax , 1
                       inc ecx
                       cmp eax , ebx       // tN < x ?
                       jb  LOOP_B        
 
  FIN_LOOP_B: dec  ecx              // b--
              xor  edi , edi      // edi <- *q=0                                      
              mov  eax , edx            
              shl  eax , cl         // eax=m = N<<b
ALIGN 8                
              LOOP_J: shr edi , 1   //  *q <<= 1
                      mov esi , ebx 
                      sub esi , eax // *r = x-m
                      js  NEXT_J
                      inc edi       // *q++  
                      mov ebx , esi // x=*r
              NEXT_J: shr eax , 1   // m >>= 1
                      dec ecx
                      jns LOOP_J  
 
              mov   ecx , q
              mov  [ecx] , esi
              cmp  edi , 0
              jns  NO_ADJUST
 
              add  edi , edx        // *r += N
   NO_ADJUST: mov  ecx , r
              mov [ecx] , edi
              mov  eax , 1          // return 1;
 
    FIN_DIV:  pop  edi
              pop  esi 
              pop  ebx
              mov  esp , ebp
              pop  ebp    
              ret 
  }
}

Ce code doit être largement perfectible (peut-être en déroulant LOOP_J et aussi en supprimant LOOP_B grâce à un usage astucieux de l'instruction BSF).

[Blustuff]

juste une pitite question, les divisons > 64 bits sont faites en binaires avec ta methode AMILIN ?

[Invité]

Il n'y a pas de restriction à l'algo que j'ai donné. J'ai donné une implémentation ASM pour des divisions 32 par 32. Avec les instructions MMX, il est facile de le modifier pour faire une division 64 par 64. Au delà, l'implémentation se complique...
Toutefois, sur x86, on utilise toujours des algos basé sur l'instruction div.
Pour plus de précision sur les divisions en multi-précision (ie > taille du mot machine ici 32 bits) voir le livre
D.E. Knuth "The Art Of Computer Programming, Volume 2: Seminumerical Algorithms" chez Addisson Wesley (disponible dans toute bonne BU qui se respecte).
A+

[Vincent PETIT]

Salut AMILIN, pour que je soit bien sur. Est ce que ton algorithme réprensente même chose que sur ce site ?
http://www.ift.ulaval.ca/~marchand/ift17583/Support/Arithm.html
Je parle de la 3eme animations "division faite par un ordinateur".

Personnellement j'ai compris l'algorithme dans ce sens ! mais j'aimerai ton avis.

Merci, avance.
Vincent

[Invité]

C'est exactement ça.
Toutefois, la première figure expliquant une division binaire "à la main" me semble plus claire pour le fonctionnement de l'algo.

Quand on fait c=2*c on décale le quotient à gauche comme dans l'animation.
On cherche ensuite si le bit à rajouter (à droite donc) vaut 0 ou 1 en testant si la soustraction à donnée un résultat positif: c étant de la forme xxxxx0 après le shift, faire c=c+1 c'est mettre le bit faible de c à 1.
En décale ensuite m (le diviseur N "shifté" de b) vers la droite.

Naturellement, ne travaillant pas bit à bit, on n'est obligé d'adapter, notamment avec le décalage préliminaire de N qui donne m: on travaille sur 32 bits plutôt que juste sur les bits les plus hauts.

On peut aussi le programmer en manipulant vraiment les nombres bit à bit mais c'est plus hardu à implémenter et sûrement plus lent. Le bit à bit est le privilège des implémentations hardware.

A+

[Vincent PETIT]

Je te remerci beaucoup AMILIN, maintenant ton algorithme m'est encore plus claire et le seul doute que j'avais n'est plus.