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) ); }
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
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.
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); } }
2147483640 2147483640 7ffffff8 -8 4294967288 fffffff8 2147483641 2147483641 7ffffff9 -7 4294967289 fffffff9 2147483642 2147483642 7ffffffa -6 4294967290 fffffffa 2147483643 2147483643 7ffffffb -5 4294967291 fffffffb 2147483644 2147483644 7ffffffc -4 4294967292 fffffffc 2147483645 2147483645 7ffffffd -3 4294967293 fffffffd 2147483646 2147483646 7ffffffe -2 4294967294 fffffffe 2147483647 2147483647 7fffffff -1 4294967295 ffffffff -2147483648 2147483648 80000000 0 0 0 -2147483647 2147483649 80000001 1 1 1 -2147483646 2147483650 80000002 2 2 2 -2147483645 2147483651 80000003 3 3 3 -2147483644 2147483652 80000004 4 4 4 -2147483643 2147483653 80000005 5 5 5 -2147483642 2147483654 80000006 6 6 6 -2147483641 2147483655 80000007 7 7 7
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).