Eviter le débordement d’interger avec les fonctions de permutation (nPr, nCr) en C

J’essaie de faire certaines fonctions liées aux statistiques afin de pouvoir effectuer quelques procédures connexes (par exemple: calculs statistiques pour les probabilités, générer le sortingangle de Pascal pour une profondeur arbitraire, etc.).

J’ai rencontré un problème où je suis probablement confronté à un débordement. Par exemple, si je veux calculer nPr pour (n = 30, p = 1), je sais que je peux le réduire à:

30P1 = 30! / (30 - 1)! = 30! / (29)! = 30! / 29! = 30

Toutefois, lors du calcul à l’aide des fonctions ci-dessous, il semble que j’obtiendrai toujours des valeurs invalides en raison d’un dépassement d’entier. Existe-t-il des solutions de contournement qui n’exigent pas l’utilisation d’une bibliothèque pour prendre en charge des nombres arbitrairement grands? J’ai lu un peu dans d’autres articles sur les fonctions gamma, mais je n’ai pas pu trouver d’exemples concrets.

 int factorial(int n) { return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n; } int nCr(int n, int r) { return (nPr(n,r) / factorial(r)); //return factorial(n) / factorial(r) / factorial(nr)); } int nPr(int n, int r) { return (factorial(n) / factorial(nr)); }

Vous semblez être sur la bonne voie, alors voilà:

 #include  #include  int nCr(int n, int r) { if(r>n) { printf("FATAL ERROR"); return 0; } if(n==0 || r==0 || n==r) { return 1; } else { return (int)lround( ((double)n/(double)(nr)/(double)r) * exp(lgamma(n) - lgamma(nr) - lgamma(r))); } } int nPr(int n, int r) { if(r>n) {printf("FATAL ERROR"; return 0;} if(n==0 || r==0) { return 1; } else { if (n==r) { r = n - 1; } return (int)lround( ((double)n/(double)(nr)) * exp(lgamma(n) - lgamma(nr))); } }

Pour comstackr, faites: gcc -lm myFile.c && ./a.out

Notez que la précision de vos résultats est limitée par la profondeur de bits du type de données double . Vous devriez pouvoir obtenir de bons résultats avec cela, mais sachez-le: remplacer tous les int ci-dessus par long long unsigned ne garantit pas nécessairement des résultats précis pour des valeurs plus grandes de n,r . À un moment donné, vous aurez toujours besoin d’une bibliothèque mathématique pour gérer des valeurs arbitrairement grandes, mais cela devrait vous aider à éviter cela pour les valeurs plus petites.

Je pense que vous avez deux choix:

Utilisez une grande bibliothèque de nombres entiers. De cette façon, vous ne perdrez pas en précision (la virgule flottante peut fonctionner dans certains cas, mais est un substitut médiocre).
Restructurez vos fonctions afin qu’elles n’atteignent pas des valeurs intermédiaires élevées. Par exemple, factorial(x)/factorial(y) est le produit de tous les nombres de y+1 à x . Alors écrivez simplement une boucle et multipliez-vous. De cette façon, vous obtiendrez un débordement uniquement si le résultat final déborde.

Si vous n’avez pas à traiter avec les valeurs signées (et cela ne semble pas être le cas), vous pouvez essayer d’utiliser un type entier plus grand, par exemple unsigned long long . Si cela ne suffit pas, vous devrez utiliser une bibliothèque non standard prenant en charge des entiers longs arbitrairement. Notez que l’utilisation du type long long nécessite le support du compilateur C99 (si vous utilisez GCC, il peut être nécessaire de comstackr avec -std=c99 ).

Edit: vous pourrez peut-être insérer davantage dans un long double , qui est de 80 bits sur certains systèmes.

Je suis peut-être dense, mais il me semble que nous allons double et que la fonction gamma est excessive ici.

Existe-t-il des solutions de contournement qui n’exigent pas l’utilisation d’une bibliothèque pour prendre en charge des nombres arbitrairement grands?

Bien sûr il y a. Vous savez exactement à quoi vous avez à faire en tout temps: des produits de gammes d’entiers. Une plage d’entiers est un cas particulier d’une liste finie d’entiers. Je n’ai aucune idée de la manière idiomatique de représenter une liste en C, je vais donc m’en tenir au pseudocode C-ish:

 make_list(from, to) return a list containing from, from+1, ..., to concatenate_lists(list1, list2) return a list with all the elements from list1 and list2 calculate_list_product(list) return list[0] * list[1] * ... * list[last] calculate_list_quotient(numerator_list, denominator_list) /* be a bit clever here: form the product of the elements of numerator_list, but any time the running product is divisible by an element of denominator_list, divide the running product by that element and remove it from consideration */ n_P_r(n, r) /* nPr is n! / (nr)! which simplifies to n * n-1 * ... * r+1 so we can just: */ return calculate_list_product(make_list(r+1, n)) n_C_r(n, r) /* nCr is n! / (r! (nr)!) */ return calculate_list_quotient( make_list(1, n), concatenate_lists(make_list(1, r), make_list(1, nr)) )

Notez que nous ne calculons jamais réellement une factorielle!

Voici un moyen de calculer sans utiliser les fonctions gamma. Il repose sur le fait que n_C_r = (n / r) * ((n-1) C (r-1)) et que, pour toute valeur positive, n_C_0 = 1, nous pouvons donc l’utiliser pour écrire une fonction de récusation comme ci-dessous

 public long combination(long n, long r) { if(r==0) return 1; else { long num = n * combination(n - 1, r - 1); return num/r; } }