La fonction factorielle: Fact(N) = N!
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
8 juin 2014 à 09:55
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 - 13 juin 2014 à 19:25
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 - 13 juin 2014 à 19:25
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/100597-la-fonction-factorielle-fact-n-n
https://codes-sources.commentcamarche.net/source/100597-la-fonction-factorielle-fact-n-n
13 juin 2014 à 13:51
Je note que cet envoi a déjà suscité plusieurs méthodes pour calculer n! : une liste de valeurs pré-calculées, le calcul traditionnel avec les entiers internes ou bien avec les flotants internes de l'ordinateur, le calcul traditionnel avec la bibliothèque GMP, le calcul avec GMP et la dichotomie des opérandes, le calcul avec log10() et le calcul avec la multiplication comme manuellement (après correction du bug, si on veut aller jusqu'à n = 200 000 il suffit de faire nc = 486 676). Toutes ces diverses méthodes ont des propriétés différentes : résultat exact ou approximatif, limite maximum différente de l'entier pour lequel on veut son factoriel et divers temps de calcul. Merci à William Voirol pour avoir proposé ce sujet et merci aussi à tout visiteur qui souhaite proposer un nouveau complément amusant ou instructif. Ce sujet se révèle, en fait, très intéressant.
13 juin 2014 à 19:25
L'étape d'après c'est de passer au calcul partagé (avec MPI par exemple), c'est d'ailleurs très facile avec un algorithme par dichotomie.
On ordinateur récupère un message pour calculer le produit de p à n, il transmet à un de ses ordinateurs voisins la première moitié du calcul à effectuer, et un deuxième voisin la deuxième moitié. Une fois les réponses reçues de ses deux voisins, l'ordinateur fait le produit et envoie le résultat.
Ça coûte un peu plus cher en nombre de calculs (puisqu'il faut gérer le transfert de messages) mais comme le calcul est découpé sur plusieurs ordinateurs (ou plusieurs processeurs d'un même ordinateur) le temps de calcul sera réduit, et les ressources machines totalement utilisées : il vaut mieux utiliser 10 machines à 100% pendant 1 minute, que 1 machine à 10% pendant 100 minutes... sauf si vous n'êtes pas pressé bien sûr ;-)
12 juin 2014 à 08:24
Pour y remédier, il a demandé de l'aide à une grande école.
Les "spécialistes de l'optimisation" ont alors réussi à améliorer son code et diviser le temps d'exécution par deux !
A juste titre, ils ont été vivement félicités.
Par hasard, un autre collaborateur (non spécialiste) avait remarqué que le programme faisait de fréquents appels à la fonction factorielle et a proposé de les remplacer par un simple accès à un tableau contenant les valeurs pré calculées.
Et le temps de calcul a été divisé par 50 !
Ce collaborateur a été chaleureusement remercié par l'ingénieur, mais personne n'a osé le féliciter !
La solution est tellement banale, "connue" et "peu élégante" que ça ne vaut même pas la peine d'en parler !
Le "dédain" envers cette "solution" semble se poursuivre encore aujourd'hui: les articles ou codes qui la mentionnent ou l'utilisent sont très rares.
12 juin 2014 à 19:07
Possible, cependant il vaudrait mieux avoir un fichier ou une base de données pour faire cela, mettre ça en dur dans le code augmente inutilement le poids de l'exécutable, de plus cela va créer des variables supplémentaires qui vont devoir être intégralement chargées en mémoire alors qu'elles ne seront pas forcément toutes utilisées au cours du programme... il faut utiliser cela raisonnablement.
Modifié par William VOIROL le 12/06/2014 à 08:22
L'extension du calcul de la factorielle à des "types de nombres" plus étendus tels que a×10^b ou GMP, est très intéressante.
C'est principalement la manière de grouper différemment les multiplications qui a attiré mon attention, car elle permet de bien diminuer la "profondeur" des appels récursifs.
Petite question sur un "détail". A la place de:
ne vaut-il pas mieux écrire:
?
Il est vrai que sur internet, particulièrement dans le domaine dont il est question ici, c'est surtout la première méthode qui est utilisée !
Modifié par KX le 12/06/2014 à 19:07
if (p==n) return p; else { Integer a=(p+n)/2; return produit(p,a)*produit(a+1,n); }ou
Dans les deux cas cela fera la même chose, je pense même que le code compilé sera identique. C'est surtout au niveau de la lecture du code que ça change.
Dans le premier on met en avant la condition, on voit clairement qu'il ne peux y avoir que deux cas possibles. Dans le deuxième c'est moins évident, on a plus l'impression que l'on traite un cas particulier (p==n) puis le cas général... mais ça évite d'avoir un bloc d'accolades inutiles dans le else ce qui réduit le niveau d'indentation... ce n'est pas forcément plus mal.
la manière de grouper différemment les multiplications qui a attiré mon attention, car elle permet de bien diminuer la "profondeur" des appels récursifs
Cela permet surtout de diminuer la complexité des calculs, puisque les multiplications intermédiaires ont des opérandes moins grandes. Il n'y a qu'à voir nos tests pour 1000000! qui se calculent en quelques secondes ou plusieurs minutes selon la méthode utilisée.
11 juin 2014 à 14:32
Utilisation :
Il y a moyen d'améliorer l'appel, mais la structure globale y est.
11 juin 2014 à 19:24
J'ai envie de dire "beurk". La génération à la compilation de valeurs c'est vraiment moche... dans ce cas là, voire dans la quasi totalité des cas (ça peux avoir un intérêt pour générer des types de données, mais des valeurs... pas vraiment !)
Quand on parlait avec pgl10 de faire des factorielles de 1 million par exemple, on est sur des résultats à plusieurs millions de chiffres. Si je calcule le résultat des 1 million premières factorielles, cela représente 2674 milliards de chiffres au total !
Donc à moins de compiler un exécutable de plusieurs centaines de Go, ta méthode de génération à la compilation se réduit à une utilisation sur de petites valeurs, tellement petites que je préfère encore que tu les tapes à la main dans un gros switch ^^'
int factorielle(int n) { switch(n) { case 0: case 1: return 1; case 2: return 2; case 3: return 6; ... } }Si j'avais su qu'on en arriverait là...
10 juin 2014 à 12:15
On peut aussi dépasser facilement la limite des entiers internes sans utiliser une bibliothèque externe. Pour cela j'ai repris et modifié un programme qui calcule la factorielle de n en faisant la multiplication comme on la fait manuellement. J'ai seulement rangé dans un tableau le produit provisoire, jusqu'au résultat final, en base 100. A noter qu'il est très facile de dépasser la limite actuelle de 50 000 pour n, avec une modification très simple du source, mais le temps du calcul augmente quand n augmente.
// Calcul de la factorielle de n : n! #include<stdio.h> #define nc 106620 // Avec nc = 106 620 on peut aller jusqu'à n = 50 000 int main() { // pour mémoriser le nombre 123456 dans c[] // on aura : c[0]=56, c[1]=34, c[2]=12 et m=3 unsigned char c[nc]; int n,i,j,temp,m,x; for(;;) { printf("\nentrez n : "); scanf_s("%d", &n); if(n<1) return 0; c[0]=unsigned char(1); temp=0; m=1; for(i=1; i<=n; i++) { // on va multiplier le résultat provisoire // par i selon la méthode traditionnelle for(j=0; j<m; j++) { x=int(c[j])*i+temp; c[j]=unsigned char(x%100); temp=x/100; } while(temp>0) { c[m]=unsigned char(temp%100); temp=temp/100; m++; if(m>nc) { printf("n est trop grand"); goto next; } } } printf("n! = "); for(i=m-1; i>=0; i--) printf("%d", int(c[i])); next: printf("\n"); } }Modifié par pgl10 le 10/06/2014 à 15:55
for(i=m-1; i>=0; i--) printf("%d", int(c[i]));par les deux lignes suivantes :
printf("%d", int(c[m-1])); for(i=m-2; i>=0; i--) printf("%02d", int(c[i]));Avec cette modification j'espère bien que le résultat est correctement affiché.
En effet, sauf au début, quand un c[k] contient 7, par exemple, il faut afficher 07 et non pas 7 !
Merci de le modifier.
10 juin 2014 à 14:12
Tu pourrais utiliser le code sur l'approximation avec le logarithme (qui est très rapide) pour déterminer au plus juste la taille du tableau qui va contenir le résultat exact.
10 juin 2014 à 15:52
8 juin 2014 à 21:29
#include <stdio.h> #include <math.h> #include <ctime> void factorielle(int n) { double sum = 0; for (int i=n; i>=2; i--) sum += log10((double) i); double b = floor(sum); double a = pow(10,sum-b); printf("%.16f.10^%.0f\n",a,b); } int main() { clock_t t=clock(); factorielle(1000000000); printf("%d s\n",(clock()-t)/CLOCKS_PER_SEC); return 0; }Oui je sais, je triche, parce que c'est une valeur approchée, mais au moins elle est affichée, alors qu'avec la valeur exacte il y a tellement de chiffres que le plus long ce n'est pas le calcul mais l'affichage (que l'on fera bien sûr en hexadécimal pour s'éviter la conversion en base 10).
Modifié par pgl10 le 8/06/2014 à 20:41
Comme il est facile d'utiliser GMP en version de Paul Herman j'ai trouvé intéressant de confirmer le commentaire instructif de KX :
#include <iostream> #include <ctime> #include "Integer.h" Integer fact1(int n) { Integer x=1; if (n>1) for (int i=n; i>=2; --i) x*=i; return x; } Integer produit(Integer p, Integer n) { if (p==n) return p; else { Integer a=(p+n)/2; return produit(p,a)*produit(a+1,n); } } Integer fact2(int n) { return produit(2,n); } int main() { clock_t t=clock(); Integer x1=fact1(1000000); std::cout << (clock()-t)/CLOCKS_PER_SEC << " s" <<std::endl; t=clock(); Integer x2=fact2(1000000); std::cout << (clock()-t)/CLOCKS_PER_SEC << " s" <<std::endl; getchar(); return 0; }Sur mon ordinateur, j'ai obtenu 1215 s pour fact1 et 12 s pour fact2. Merci KX.
Mais calculer la factorielle de 1 000 000 est une opération que je n'imaginais pas jusqu'à maintenant !
8 juin 2014 à 17:51
Quelques remarques :
D'une part la limitation des entiers, elle est assez évidente puisque sur 32 bits on ne peut aller que jusqu'à 2^32 (idem avec 64) alors que la factorielle dépasse rapidement ces valeurs.
D'autre part la limitation des flottants, là encore il y a une limite en terme de valeurs la plus haute à atteindre, mais surtout une limite en terme de précision, du même ordre de grandeur que pour les entiers. C'est à dire qu'au delà de 2^32 pour les floats et 2^64 pour les double on n'aura plus la valeur exacte.
Si on ne s'intéresse pas à la valeur exacte alors il est plus intéressant de ne pas calculer directement l'exponentielle, mais d'en calculer le logarithme.
Ainsi au lieu d'avoir n! = 1*2*3*4*...*n, on aura log(n!) = log(1)+log(2)+log(3)+...+log(n)
Les valeurs étant radicalement plus petites on pourra atteindre des valeurs de n extrêmement grandes (bien au delà du milliard, à comparer au 170 actuel), il suffira alors d'afficher le résultat sous la forme "n! = a.10^b", avec a et b calculées à partir du log(n!) puisque b est la partie entière de log(n!)/log(10) et a=10^f où f est la partie fractionnaire de log(n!)/log(10).
Concernant la récursivité, elle ne change rien au résultat, quelque soit la méthode utilisée. Cependant pour de très grandes valeurs, elle peut faire planter le programme car la pile d'appel récursif est limitée en taille (quelques milliers maximum). Il faut donc toujours s'assurer que le nombre d'appels récursifs sera maîtrisé. Pour 170 ça allait, pour un milliard, ça n'ira pas du tout !
L'utilisation de GMP est une alternative intéressante mais elle emmène une complexité supplémentaire. En effet, sur les types primitifs du langage C, toutes les opérations se font en temps constants. Or avec une bibliothèque comme GMP, les opérations sont de plus en plus coûteuse pour de grands nombres. Le nombre de calculs nécessaire pour une multiplication sera "proportionnel" au nombre de chiffres du résultat (multiplier 2 et 2 nécessite le calcul du résultat sur 3 bits. Alors que 1024 et 1024 requiert le calcul du résultat sur 20 bits)
Ainsi l'utilisation "naïve" d'une boucle est inefficace, car la variable x représente la factorielle et est de plus en plus grande, ainsi le calcul de chaque produit va être de l'ordre de i!
On peut améliorer ceci en regroupant par dichotomie les nombres de même ordre de grandeur pour la multiplication.
Pour optimiser les calculs de 8! je ne ferais donc pas ((((((1*2)*3)*4)*5)*6)*7)*8 ce qui reviendrait à faire 1*2, 2*3, 6*4, 24*5, 120*6, 720*7 et 5040*8
Mais plutôt un calcul équivalent ((1*2)*(3*4))*((5*6)*(7*8)) qui reviendrait à faire 1*2, 3*4, 5*6, 7*8, 2*12, 30*56, 24*1680, ce n'est pas parfait, mais les opérandes pour chaque multiplications sont d'un ordre de grandeur plus proches (et globalement moins grands) ce qui diminuera le temps de calculs de la factorielle.
En pseudo code (car GMP utilises des fonctions différentes) ça donnerait ceci :
entier produit(entier p, entier n) { if (p==n) return p; else { entier a = (p+n)/2; return produit(p,a) * produit(a+1,n); } } entier factorielle(entier n) { return (n<2) ? 1 : produit(2,n); }Ici le code est récursif mais c'est de la dichotomie donc le nombre d'appels ne dépassera jamais log(n), il n'y a aucun problème même pour de très grandes valeurs de n. Par exemple, je calcule ainsi la factorielle de 1 000 000 en 10 secondes par dichotomie, contre 8 mn pour la boucle classique de 1 à n.
Remarque : une telle optimisation n'a aucun intérêt si on utilise les types entiers classiques, puisque chaque produit se fera en temps constants, peu importe la valeur des opérandes, c'est vraiment dans le cas des bibliothèques de grands nombres que cela devient utile.
Modifié par pgl10 le 8/06/2014 à 15:59
Pour utiliser une limite encore plus grande on peut faire une variante avec GMP en version de Paul Herman.
En voici un exemple très simple et très voisin du logiciel ici proposé :
#include <iostream> #include "Integer.h" Integer fact(int n) { Integer x=1; if (n>1) for (int i=n; i>=2; --i) x*=i; return x; } int main() { std::cout << fact(1000) << std::endl; getchar(); return 0; }Si on le souhaite, il y a la version 4.1.2 de GMP en version de Paul Herman avec la documentation, des exemples et les bibliothèques statique ou dynamique dans mon logiciel Fractran disponible dans mon site Internet : http://pgl10.chez.com/mathematiques.html