Décomposition minimale

Décomposition minimale - C++ - Programmation

Marsh Posté le 25-01-2006 à 23:21:06    

Hello,
 
   Je galere sur un truc qui à l'air con :(
 
   Mon but est de générer du code MIPS pour permettre de multiplier un nombre entier par une
valeur m avec un minimum de décalages, d'addition et de soustractions.
 
Je m'entraine d'abord à produire des strings lisibles pour l'instant ...
 
Exemples :  
i * 6 = i * 4 + i * 2 = i << 2 + i << 1    OK
i * 7 = i * 8 - i = i << 3 - i                  OK  
...
Donc il ne suffit pas de décomposer en base 2 car i * 15 est plus efficacement calculé par i * 16 - i  
   
 

Code :
  1. string itos(int i) // convert int to string
  2. {
  3.  stringstream s;
  4.  s << i;
  5.  return s.str();
  6. }
  8. int get_n( int x ){
  9.     if ( x == 1 )
  10.         return 0;
  11.     else if ( x == 2 )
  12.         return 1;
  13.     else
  14.         return 1 + get_n( x/2 );
  15. }   
  17. // Fonction qui decompose simplement la multiplication de 2 nombres
  18. // A virer !
  19. string decompose ( int m, const string& var, bool plus ) {
  20.      string s = "";   
  21.      if ( plus == true ) { s = s + " + "; plus = false; }   // Pour l'affichage du premier plus                   
  22.      if ( m == 0 ) { s = " 0 "; }
  23.      else if ( m == 1 ) { s = var; }   
  24.      else if ( (m % 2) == 0 ) {    // SI m est multiple de 2
  25.    
  26.           if ( (m & (m-1)) == 0 ){ // SI m est une puissance de 2
  27.                s = s + var + " << " + itos( get_n( m ) );         
  28.           } else {
  29.               s = s + decompose( m-2, var, plus );       
  30.               s = s + " + " + var + " << 1"; // la c'est provisoire
  31.           }
  32.          
  33.      } else { // SINON  ...
  34.          
  35.           if ( (m-1 & (m-2)) == 0 ){ // SI m-1 est une puissance de 2
  36.                s = s + var + " << " + itos( get_n( m - 1 ) );         
  37.                s = s + " + " + var;     
  38.           }/* else {          // SI  m+1 est puisance de 2
  39.                s = s + decompose( m+1, var, plus );
  40.                s = s + " - " + var;
  41.           } */else {
  42.                  // BOURRIN : avec une boucle on incremente et on regarde si ca peut se gerer ...
  43.                  int i = 1;
  44.                  while ( i <= m  && ((m+i)%2) == 0 ){
  45.                         if ( ((m+i) & (m+i-1)) == 0 ) // SI m est une puissance de 2
  46.                             s = s + var + " << " + itos( get_n( m+i ) );       
  47.                         else {
  48.                           s = s + decompose( m+i, var, plus );       
  49.                         }
  50.                         s = s + " - " + decompose( i, var, plus );       
  51.                         i++;
  52.                  }               
  53.           }
  54.            
  55.      }           
  56.      return s;   
  57. }
  59. int main (int argc, const char* argv []) {
  60.   int d = 24; 
  61.   cout << "i * " << d << " = " << decompose( d, "i", false ) << endl;
  62.   return 0;
  63. }


 
J'ai quelques cas de base qui marchent quand même.


i * 10 = i << 3 + i << 1
i * 17 = i << 4 + i
...
ET la ça mird
i * 24 = i << 4 + i << 1 + i << 1 + i << 1 + i << 1        
au lieu d'un simple
i * 24 = i << 4 + i << 3


 
Une idée quelqu'un ?
 
EDIT :
 
La c'est deja un peu mieu mais bon ca beug pour 25

Code :
  1. string decompose ( int m, const string& var, bool plus ) {
  3.     string s = "";   
  5.     if ( plus == true ) { s = s + " + "; plus = false; }   // Pour l'affichage du premier plus                   
  7.     if ( m == 0 )        { s = " 0 "; }
  8.     else if ( m == 1 )   { s = var;   }   
  9.     else if ( m == 2 )   { s = s + var + " << 1"; }
  10.     else if ( (m & (m-1)) == 0 ) { s = s + var + " << " + itos( get_n( m ) ); }
  11.     else {
  12.       // Le masque
  13.       int temp = m;
  14.       int mask = 1;
  15.      
  16.        while ( mask + 1 != temp && mask <= temp ) {
  17.              mask = mask << 1;
  18.        }
  19.        s = s + var + " << " + itos( get_n( mask ) );                       
  20.        if ( mask + 1 == temp )
  21.             s = s + " + " + var ;
  22.        else
  23.             s = s + " - " + decompose( mask-temp, var, plus );
  26.     }
  28.     return s;   
  29. }



Message édité par Chronoklazm le 26-01-2006 à 03:31:34

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 25-01-2006 à 23:21:06   

Reply

Marsh Posté le 29-01-2006 à 18:47:57    

Salut
 
Pour ta décomposition, n'aurais-tu pas intérêt à décomposer en utilisant les puissances de 2 les plus proches à chaque fois ?
style ce genre d'algo :

Code :
  1. entier n : nombre à décomposer
  2. entier pp : puissance de deux la plus proche
  3. entier signe : à l'initalisation, le signe est +, ensuite il change suivant que le nombre à décomposer est plus grand ou plus petit.
  5. [initialisation]
  6. debut
  7.   signe <- 1
  8.   faire
  9.     pp <- plus_proche(n)
  11.     memoriser(signe)
  12.     memoriser(pp)
  14.     si pp > n alors
  15.       n <- pp - n
  16.       signe <- -signe
  17.     sinon
  18.       n <- n - pp
  19.     fin si
  20.   tant que n <> 0
  21. fin
  23. fonction plus_proche(entier n) retour entier
  24. entier p1
  25. entier p2
  26. début
  27.   p1 <- 2
  28.   p2 <- 1
  29.   tant que p1 < n faire
  30.     p2 <- p1
  31.     p1 <- 2 * p1
  32.   fin tant que
  33.   si p1 - n < n - p2 alors
  34.     plus_proche <- p1
  35.   sinon
  36.     plus_proche <- p2
  37.   fin si
  38. fin


Il est évident qu'en C, on doit pouvoir optimiser la fonction plus_proche en lui faisant renvoyer le reste et le signe.
On doit pouvoir aussi trouver le plus proche en testant les bits à 1 contigus à partir des poids les plus forts.
style  
  pour 15 on prend 16  
  car 15 = 8 * 1 + 4 * 1 + 2 * 1 + 1 * 1
  les bits de 8 et 4 sont contigus et ont la valeur 1
 
alors que pour 11 on prend 8  
  car 11 = 8 * 1 + 4 * 0 + 2 * 1 + 1 * 1
  les bits de 8 et 4 sont contigus et n'ont pas la même valeur
 
 
 
 

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed