:: PlayerAdvance.org ::  

Précédent   :: PlayerAdvance.org :: > :: Développement Amateur :: > Autres > Tutoriels

Tutoriels Tutoriels dédiés au développement sur d'autres supports

Publicité

Réponse
 
Outils de la discussion Modes d'affichage
Vieux 18/09/2006, 23h10   #1
Bobby Sixkilla
Maître Chinpoko-extra-mon
 
Date d'inscription: 10/11/2005
Localisation: Palaiseau (Rive sud)
Messages: 6 466
Voir les codes amis Nintendo DS
Par défaut Optimisation du modulo

Optimisation du modulo

Auteur : Brunni

Voici une petite explication sur comment faire un modulo et une division à la main. Prenons le cas où on veut faire x%y. En gros, on voit qu'on peut faire ça très facilement, comme ceci:
Code:
while(x>=y)
   x-=y;
Bien sûr ça devient très lent si x est grand. Alors le principe n'est pas compliqué, c'est d'abord de vérifier si x n'est pas supérieur à 4*y, ou 16*y, de manière à éliminer rapidement les plus grosses valeurs...
Code:
while(x>=4*y)
   x-=4*y;
while(x>=y)
   x-=y;
Ce qui donne par optimisation (décalages binaires):
Code:
while (x >= y<<2)
   x-=y<<2;
while (x >= y)
   x-=y;
Et on peut continuer en insérant également au début:
Code:
while (x >= y<<4)
   x-=y<<4;
Afin d'accélérer le tout. Finalement, cela devient très simple: en partant de la valeur maximale souhaitée, on peut faire une vérification par échelons (puissances de 2). Cela donnerait, en reprenant le code plus haut, et en partant de 30, car on a 32 bits moins les deux premiers:
Code:
//Par étapes de 2
for (i=30;i>=0;i-=2)     {
   while (x >= y<<i)
       x -= y<<i;
}
Je le fais par étapes de deux, mais je pourrais y aller par trois, par un, ou même plus. Ici, puisqu'on extrait 2 bits à la fois, le nombre d'itérations maximum pour chaque test est de 3 (11) et comme 16 groupes de bits sont vérifiés (de 30 à 0 par étapes de 2), ça fait au maximum 64 opérations, et 16 au minimum. Si je prends un seul bit à la fois, ça donne une seule itération maximum, mais 32 tests à effectuer (64 opérations au max, 32 au min), finalement plus lent dans presque tous les cas. Et si je prends trois bits à la fois, ça donne 7 itérations maximum par test, et 10 tests à effectuer (soit 80 opérations au max, 10 au min). On voit donc que la solution de prendre 2 bits à la fois est le meilleur compromis.
Voilà donc la routine que j'ai écrite, mais elle n'est pas réellement plus rapide que la routine originale. J'ai bien la version boucle déroulée en ASM quelque part mais elle prend beaucoup trop de place, je préfère cette routine, plus lente mais qu'on peut mettre en IWRAM pour gagner déjà pas mal par rapport à la routine intégrée:
Code:
unsigned int IN_IWRAM modulo(s32 i, u32 x, u32 y)       {
   //x%y
   u32 j;
   while((y<<i)==0)
       i-=2;
   for (;i>=0;i-=2)      {
       j=y<<i;
       while(x>=j)     {
           x-=j;
       }
   }
   return x;
}

//Modulo 32 bits ou 16 bits
#define mod32(x,y) modulo(30,x,y)
#define mod16(x,y) modulo(14,x,y)
Il faut appeler mod32 ou mod16 suivant que les nombres seront maximum sur 16 ou 32 bits.
Après je me suis demandé comment faire une division, et finalement c'est exactement identique (ce qui explique pourquoi les routines de division ou de modulo font presque toujours les deux en même temps). Il suffit d'ajouter à une variable le nombre de fois qu'on a enlevé y à x. Par exemple si on fait x-=y<<2, soit x-=y*4, ça veut dire que x contenait 4 fois y, soit 1<<2 (=4) en fait. J'ajoute cela à z qui est le résultat de la division:
Code:
unsigned int IN_IWRAM division(s32 i, u32 x, u32 y)       {
   //x%y
   u32 j,z=0;
   while((y<<i)==0)
       i-=2;
   for (;i>=0;i-=2)      {
       j=y<<i;
       while(x>=j)     {
           x-=j;
           z+=1<<i;
       }
   }
   return z;
}

#define div32(x,y) division(30,x,y)
#define div16(x,y) division(14,x,y)
D'ailleurs même s'il n'est pas retourné, x contient x%y à la fin de cette fonction, et z=x/y.
Ce qu'on se rend compte après ça, c'est que la lenteur de la division et du modulo est variable, et dépend de la grandeur de x par rapport à y. Faire 12874834%5 sera très lent, mais 12874834%4894563 ou 27%5 déjà beaucoup moins. C'est un problème parce que si vos objets se déplacent selon un timer, le jeu aura tendance à ralentir au fur et à mesure que le temps passe (puisque la valeur du timer augmentera constamment).
Bobby Sixkilla est déconnecté   Réponse avec citation

Publicité

Vieux 18/09/2006, 23h22   #2
Dr.Vince
Administrateur
 
Date d'inscription: 10/11/2005
Messages: 4 963
Voir les codes amis Nintendo DS Voir les codes amis Wii
Par défaut

cool, je vois que tu me donnes un coup de main
__________________
Projets Abandonnés: [Arcomage Advance] [Puzznic] [PA Card Games] [Blob Runner]
Projet en cours: [Ne plus abandonner de projet...]
Dr.Vince est déconnecté   Réponse avec citation
Vieux 18/09/2006, 23h35   #3
Bobby Sixkilla
Maître Chinpoko-extra-mon
 
Date d'inscription: 10/11/2005
Localisation: Palaiseau (Rive sud)
Messages: 6 466
Voir les codes amis Nintendo DS
Par défaut

On fait un concours?
Bobby Sixkilla est déconnecté   Réponse avec citation
Vieux 18/09/2006, 23h44   #4
Dr.Vince
Administrateur
 
Date d'inscription: 10/11/2005
Messages: 4 963
Voir les codes amis Nintendo DS Voir les codes amis Wii
Par défaut

allez.... demain au lieu de bosser, j'importe tous les tutos de l'ancien PA
__________________
Projets Abandonnés: [Arcomage Advance] [Puzznic] [PA Card Games] [Blob Runner]
Projet en cours: [Ne plus abandonner de projet...]
Dr.Vince est déconnecté   Réponse avec citation
Vieux 18/09/2006, 23h53   #5
Teka
Membre confirmé
 
Date d'inscription: 10/11/2005
Messages: 224
Par défaut

Sinon il existe une autre solution, c'est d'utiliser (quand c'est possible) les masques binaires mais pour cela il y a des contraintes mais les gains sont sans comparaisons !
Teka est déconnecté   Réponse avec citation
Vieux 18/09/2006, 23h57   #6
Dr.Vince
Administrateur
 
Date d'inscription: 10/11/2005
Messages: 4 963
Voir les codes amis Nintendo DS Voir les codes amis Wii
Par défaut

un ptit tuto Teka ??
__________________
Projets Abandonnés: [Arcomage Advance] [Puzznic] [PA Card Games] [Blob Runner]
Projet en cours: [Ne plus abandonner de projet...]
Dr.Vince est déconnecté   Réponse avec citation
Vieux 19/09/2006, 17h05   #7
thoduv
Membre confirmé
 
Date d'inscription: 10/11/2005
Localisation: ...
Messages: 1 464
Par défaut

Juste pour signaler que GCC optimise tout ca hein.
Il remplace les /2, /4, /8, etc, par les >>1 >>2, >>3 qui vont bien, pareil pour les multiplications, et pour les modulos, il remplace les %2, %,4, %8, par &1, &3, &7 etc... Donc on peut sans craine privilégier la lisibilité, le compilateur optimise tout comme il faut.
__________________
"S'il n'y a pas de solutions c'est qu'il n'y a pas de problème ..."
< mon devblog > ... < Lapinou Jumps ! - un jeu de plate-forme "vertical" avec un mignon petit lapin. >
thoduv est déconnecté   Réponse avec citation
Vieux 19/09/2006, 17h14   #8
Mollusk
Membre confirmé
 
Date d'inscription: 10/11/2005
Messages: 1 037
Par défaut

Pas de comparaison entre l'algo donné et le modulo normal pour voir la différence de vitesse ? :/
Mollusk est déconnecté   Réponse avec citation
Vieux 20/09/2006, 12h32   #9
Teka
Membre confirmé
 
Date d'inscription: 10/11/2005
Messages: 224
Par défaut

Citation:
Envoyé par Dr.Vince
un ptit tuto Teka ??
Urfff flemme je dois avouer


Citation:
Envoyé par Thoduv
Juste pour signaler que GCC optimise tout ca hein.
Il remplace les /2, /4, /8, etc, par les >>1 >>2, >>3 qui vont bien, pareil pour les multiplications, et pour les modulos, il remplace les %2, %,4, %8, par &1, &3, &7 etc... Donc on peut sans craine privilégier la lisibilité, le compilateur optimise tout comme il faut.
Oh ? gcc fait tout ça? ... super
Teka est déconnecté   Réponse avec citation
Réponse

Liens sociaux

Publicité



Utilisateurs regardant la discussion actuelle : 1 (0 membre(s) et 1 invité(s))
 
Outils de la discussion
Modes d'affichage

Règles de messages
Vous ne pouvez pas créer de nouvelles discussions
Vous ne pouvez pas envoyer des réponses
Vous ne pouvez pas envoyer des pièces jointes
Vous ne pouvez pas modifier vos messages

Les balises BB sont activées : oui
Les smileys sont activés : oui
La balise [IMG] est activée : oui
Le code HTML peut être employé : non
Navigation rapide


Fuseau horaire GMT +2. Il est actuellement 20h48.


Édité par : vBulletin® version 3.7.2
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Tous droits réservés.
Version française #16 par l'association vBulletin francophone
Design par Ass-Itch, DJP et Dr.Vince