Calculateur 32bits ... problème de débordement !!!

boguista Messages postés 1 Date d'inscription mardi 20 décembre 2005 Statut Membre Dernière intervention 6 février 2009 - 6 févr. 2009 à 14:24
gaspos Messages postés 17 Date d'inscription jeudi 9 décembre 2004 Statut Membre Dernière intervention 20 février 2009 - 6 févr. 2009 à 18:36
j'ai à coder le calcul suivant :

S= c. [(a.b + (a+b).2^15 + 2^30)/2^32] sachant que a, b et c sont sur 16 bits

Avez vous un algorithme précis qui puisse retourner une valeur exacte de sortie S sur 16 bits sans aucune perte de l'information !

Bon de ma part j'ai realisé ce code mais un test sur un émalateur 32bits me donne des résultats non conforme à ceux que j'ai calculé moi même

Voici un en algorithmmique une vue de ce code, j'attends vos remarques et merci .

{
if ( (a + b) * 32768) > (UINT32_MAX - (a * b) - 2^30))
   {
      u32LocalProduct1 = ((a * b) / 65536) + ((( a+ b)* 32768) / 65536) + 16384;
   }
   else
   {
      u32LocalProduct1 = (( a* b) + ((a + b) * 32768)+ 1073741824)/ 65536;
   }

   if (c== 0)
   {
      S = 0;
   }
   else
   {
      if (u32LocalProduct1 > (UINT32_MAX / c))
      {
         u32LocalProduct2 = (u32LocalProduct1 / 65536) * c;
         S = MIN(u32LocalProduct2,65535);
      }
      else
      {        
         u32LocalProduct2 = ((u32LocalProduct1 * c) + 32768)/ 65536;
        S = MIN(u32LocalProduct2,65535);
      }
}

1 réponse

gaspos Messages postés 17 Date d'inscription jeudi 9 décembre 2004 Statut Membre Dernière intervention 20 février 2009
6 févr. 2009 à 18:36
En fait, ce qu'il te faut, c'est un calcul sur 64 bits...
Je suppose que tu n'as pas accès aux entiers sur 64 bits sinon tu n'aurais pas posté ce message !

Du coup, voici une petite solution toute propre : implémenter les calculs 64 bits dont tu as besoin :

typedef struct
    {
    unsigned long hi,lo ;
    } uint64 ;





void add ( uint64 a , uint64 b , uint64 * r )
    {
    r->lo = a.lo + b.lo ;
    r->hi = a.hi + b.hi ;
    if ((r->lo < a.lo) || (r->lo < b.lo))
        r->hi++ ; // ajout de la retenue s'il y a lieu
    }



void shift_right ( uint64 * a , int nbbit )
    {
    a->lo = (a->lo >> nbbit) | (a->hi << (32-nbbit)) ;
    a->hi >>= nbbit ;
    }



void shift_left ( uint64 * a , int nbbit )
    {
    a->hi = (a->hi << nbbit) | (a->lo >> (32-nbbit)) ;
    a->lo <<= nbbit ;
    }



// c. [(a.b + (a+b).2^15 + 2^30)/2^32]
unsigned long compute ( unsigned short a , unsigned short b , unsigned short c )
    {
    uint64 aa = { 0,a+b } ;
    uint64 bb = { 0,a*b } ; // pas de débordement si a et b sur 16 bits
    uint64 dd = { 0,1<<30 } ;



    uint64 r1,r2,r3 ;



    shift_left( &aa,15 ) ;  // aa = (a+b).2^15
    add( aa,bb,&r1 ) ;      // r1 = a.b + (a+b).2^15    add( dd,r1,&r2 ) ;      // r2 r1 + 2^30 a.b + (a+b).2^15 + 2^30
                            // r2.hi = r2/2^32
    return( c * r2.hi )  ;
    }




et voila !

Hadrien
0