TP I20, semaine 2

Coefficients du binôme

Exemple de programme à réaliser :

long factorielle (int n) {
  int k;
  long f = 1;
  
  for (k = 2; k <= n; k++)
    f = f * k;
  return f;
}

long binome1 (int n, int p) {
  return factorielle (n) / factorielle (p) / factorielle (n-p);
}

/* Version incorrecte */

long binome2 (int n, int p) {
  int i;
  long c = 1;
  
  for (i = p; i > 0; i--)
    c = c * (n - p + i) / i;
  return c;
}

long binome3 (int n, int p) {
  int i;
  long c = 1;
  
  for (i = 1; i <= p; i++)
    c = c * (n - p + i) / i;
  return c;
}

long binome4 (int n, int p) {
  int i;
  long c = 1;
  
  for (i = 1; i <= p; i++)
    c = c * (n - i + 1) / i;
  return c;
}

void main () {
  int k, n;
  
  printf ("Entrer un entier : ");
  scanf ("%d", &n);
  for (k = 0; k <= n; k++)
    printf ("%12d %12d %12d %12d\n",
      binome1 (n, k),
      binome2 (n, k),
      binome3 (n, k),
      binome4 (n, k) );
}

Exécution sur Sparc :

Entrer un entier : 7
1 1 1 1
7 7 7 7
21 18 21 21
35 30 35 35
35 20 35 35
21 6 21 21
7 2 7 7
1 1 1 1
Entrer un entier : 13
1 1 1 1
4 13 13 13
24 72 78 78
88 264 286 286
221 660 715 715
399 990 1287 1287
532 1296 1716 1716
532 840 1716 1716
399 210 1287 1287
221 60 715 715
88 20 286 286
24 6 78 78
4 2 13 13
1 1 1 1

Commentaire

La fonction binome1 provoque un débordement, et donc fournit un résultat faux, dès que n! n'est plus représentable sur 32 bits, c'est-à-dire dès que n > 12, même si le coefficient du binôme est loin de ne plus être représentable sur 32 bits.

La fonction binome2 fournit presque toujours un résultat faux, à cause des divisions intermédiaires qui ne fournissent pas des quotients entiers.

Les fonctions binome3 et binome4 provoquent un débordement à partir de n=30.

Arithmétique circulaire

Exemple de programme à réaliser :

int puissance (int a, int n) {
  int i, p = 1;
  
  for (i = 0; i < n; i++)
    p = a * p;
  return p;
}

void main () {
  int i, n, p, q;
  
  n = puissance (2, 31);
    
  for (i = -8; i < 8; i++) {
    p = n + i;
    q = 2 * n + i;
    printf ("%12d %12u %8x %12d %12u %8x\n", p, p, p, q, q, q);
  }
}

Exécution sur Sparc :

214748364021474836407ffffff8 -84294967288fffffff8
214748364121474836417ffffff9 -74294967289fffffff9
214748364221474836427ffffffa -64294967290fffffffa
214748364321474836437ffffffb -54294967291fffffffb
214748364421474836447ffffffc -44294967292fffffffc
214748364521474836457ffffffd -34294967293fffffffd
214748364621474836467ffffffe -24294967294fffffffe
214748364721474836477fffffff -14294967295ffffffff
-2147483648214748364880000000 000
-2147483647214748364980000001 111
-2147483646214748365080000002 222
-2147483645214748365180000003 333
-2147483644214748365280000004 444
-2147483643214748365380000005 555
-2147483642214748365480000006 666
-2147483641214748365580000007 777

Commentaire

Sur Sparc, les entiers sont représentés sur 32 bits, donc les discontinuités apparaissent autour de 231 pour les entiers relatifs (colonne 1, débordement) et de 232 pour les entiers naturels (colonnes 5 et 6, perte de la retenue).