Chronoklazm | 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 :
- string itos(int i) // convert int to string
- {
- stringstream s;
- s << i;
- return s.str();
- }
- int get_n( int x ){
- if ( x == 1 )
- return 0;
- else if ( x == 2 )
- return 1;
- else
- return 1 + get_n( x/2 );
- }
- // Fonction qui decompose simplement la multiplication de 2 nombres
- // A virer !
- string decompose ( int m, const string& var, bool plus ) {
- string s = "";
- if ( plus == true ) { s = s + " + "; plus = false; } // Pour l'affichage du premier plus
- if ( m == 0 ) { s = " 0 "; }
- else if ( m == 1 ) { s = var; }
- else if ( (m % 2) == 0 ) { // SI m est multiple de 2
-
- if ( (m & (m-1)) == 0 ){ // SI m est une puissance de 2
- s = s + var + " << " + itos( get_n( m ) );
- } else {
- s = s + decompose( m-2, var, plus );
- s = s + " + " + var + " << 1"; // la c'est provisoire
- }
-
- } else { // SINON ...
-
- if ( (m-1 & (m-2)) == 0 ){ // SI m-1 est une puissance de 2
- s = s + var + " << " + itos( get_n( m - 1 ) );
- s = s + " + " + var;
- }/* else { // SI m+1 est puisance de 2
- s = s + decompose( m+1, var, plus );
- s = s + " - " + var;
- } */else {
- // BOURRIN : avec une boucle on incremente et on regarde si ca peut se gerer ...
- int i = 1;
- while ( i <= m && ((m+i)%2) == 0 ){
- if ( ((m+i) & (m+i-1)) == 0 ) // SI m est une puissance de 2
- s = s + var + " << " + itos( get_n( m+i ) );
- else {
- s = s + decompose( m+i, var, plus );
- }
- s = s + " - " + decompose( i, var, plus );
- i++;
- }
- }
-
- }
- return s;
- }
- int main (int argc, const char* argv []) {
- int d = 24;
- cout << "i * " << d << " = " << decompose( d, "i", false ) << endl;
- return 0;
- }
|
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 :
- string decompose ( int m, const string& var, bool plus ) {
- string s = "";
- if ( plus == true ) { s = s + " + "; plus = false; } // Pour l'affichage du premier plus
- if ( m == 0 ) { s = " 0 "; }
- else if ( m == 1 ) { s = var; }
- else if ( m == 2 ) { s = s + var + " << 1"; }
- else if ( (m & (m-1)) == 0 ) { s = s + var + " << " + itos( get_n( m ) ); }
- else {
- // Le masque
- int temp = m;
- int mask = 1;
-
- while ( mask + 1 != temp && mask <= temp ) {
- mask = mask << 1;
- }
- s = s + var + " << " + itos( get_n( mask ) );
- if ( mask + 1 == temp )
- s = s + " + " + var ;
- else
- s = s + " - " + decompose( mask-temp, var, plus );
- }
- return s;
- }
|
Message édité par Chronoklazm le 26-01-2006 à 03:31:34
---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
|
