Salut tout le monde, j'ai en info un projet à faire en C sur la gestion d'entiers arbitrairement longs représentés par des listes chainées (chaque élément représentant un chiffre de l'entier en base 10000) et je dois coder diverses fonctions sur ces entiers, notamment la factorielle et la division.

Pour la factorielle, j'ai déjà une solution qui marche, il suffit de faire un algorithme qui récursif qui part de 1! = 1 et qui fait n! = (n-1)!*n. Mais pour des nombres supérieurs à 100, c'est long, très long. Est-ce qu'il existe un algorithme de calcul de factorielle plus optimisé ?

Et puis, j'ai aussi la division entière qui me pose problème : j'ai déjà implémenté un algorithme mais qui ne marche pas si le dividende est trop grand. J'ai entendu parler de l'algorithme de Knuth pour les divisions entières en base B, quelqu'un en saurait-il plus à ce sujet ?

Bon, l'algorithme de division de Knuth est finalement implémenté dans mon programme. Il ne reste plus que la factorielle qui me pose problème, j'ai rien trouvé sur google, quelqu'un aurait une idée ?

<?php

function factorielle($int) {
$resultat = 1;
for($u=2; $u<=$int; $u++) {
$resultat*=$u;
}
return $resultat;
}

echo factorielle(3), "\r\n";
echo factorielle(170), "\r\n"; // 170 c'est le max que j'ai pour php, il me sort à INF après ^^

deepblue>>Je crois que c'est du code C avec des listes chainées qu'il veut.

"Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, des pointeurs vers les éléments qui lui sont logiquement adjacents dans la liste."

Ce n'est pas ce que j'ai fais ?

Après, que ce soit en C ou en php, l'algo reste le même ^^

deepblue a raison, l'algorithme c'est le même dans un langage ou un autre donc vu que je connais PHP ça va j'arrive à comprendre l'idée sans problème.
Le seul problème, c'est que j'aimerais justement pouvoir calculer des factorielles comme 1000! (ou même 10000!) assez rapidement. Je me demande donc si il existe un algorithme optimisé pour le calcul de factorielle qui permette de faire le calcul de n! en moins de n opérations. Vu que j'ai rien trouvé sur google, c'est possible qu'un tel algorithme n'existe pas.

Désolé, je penseais qu'il fallait inclure le parcours du nombre avec les pointeurs.

Pour l'algo factorielle, je pense pas qu'il y ait plus rapide. A la limite si les factorielles que tu as à calculer sont toujours au dessus d'une certaines valeur, tu peux faire un cache qui possède déjà les 1ères factorielles, ça évitera de recalculer à chaque fois.

C'est normal que la factorielle soit longue à calculer. Pour des factorielles très grandes, on prend une approximation comme la formule de Stirling.

Sinon, n'oublie pas d'inclure de test de valeur négative qui doit renvoyer une erreur et non la valeur 1.

"Sinon, n'oublie pas d'inclure de test de valeur négative qui doit renvoyer une erreur et non la valeur 1"

T'inquiète pas, j'ai pensé à ça Sinon, t'as raison au dessus d'une certaine valeur je peux toujours mettre une approximation via la formule de Stirling, même si le calcul de la puissance n-ième dans la formule de Stirling risque de me poser quelques problèmes de rapidité.

il est possible que ton probleme ne vienne pas du calcul de la factoriel mais d'un manque de performance de tes operations arithmetique de base.

De plus, je ne sais pas comment tu fais ton implementation, mais lors du calcul d'une factoriel, tu peux reutiliser la variable temporaire au lieu de la realloue.

Finalement, c'est peut etre un peu overkill, mais tu peux faire du parallelisme. Dans le calcul d'une factorielle, toutes les operations sont independante. Si ton systeme a plusieurs processeur, tu peux decouper ce calcul.

"il est possible que ton probleme ne vienne pas du calcul de la factoriel mais d'un manque de performance de tes operations arithmetique de base. "

Pour les algorithmes de calcul de multiplication et de somme, j'utilise la méthode naïve (après avoir lamentablement tenté de mettre des trucs plus complexes) mais je pense pas que ce soit ça qui fasse ramer autant quand même ?
Je vais quand même essayer de chercher de ce coté là.

Il est naïf de croire qu'une méthode naïve est une méthode efficace.

Si ton programme fonctionne pour n! avec n < 100 mais rame de plus en plus après, c'est bien qu'il y a un problème d'optimisation. C'est peut-être du à la consommation de mémoire ou au temps de calcul, mais c'est très probablement l'algorithme utilisé qui est en cause.

Regarde (en faisant un petit graphique par exemple) le temps de calcul de n! en fonction de n (et montre le nous). Avec un algorithme naïf pour la multiplication qui est en log(n) (et encore), ta factorielle sera en n*log(n) (sauf si je dit n'importe quoi), mais si tu consomme plus de mémoire que tu as de RAM libre et que tu te mets à swapper, alors d'un seul coup, tes performances peuvent être divisées par 1000 peut-être. Es-tu sûr de désoualouer le plus tôt possible la mémoire dont tu n'as plus besoin ?

heu, quand tu dis que ta multiplication est naive, elle est naive comment ?

Ben elle croit tout ce qu'elle entend quoi

"Il est naïf de croire qu'une méthode naïve est une méthode efficace. "

Effectivement, j'espérais juste que ça puisse être suffisant pour aller au moins jusqu'à 10000!

"Si ton programme fonctionne pour n! avec n < 100 mais rame de plus en plus après, c'est bien qu'il y a un problème d'optimisation"

En fait, 100! est instantané, c'est à partir de 500! que ça commence à déjà prendre quelques secondes, et au dela c'est très long : 1000! en 1 minute par exemple.

"heu, quand tu dis que ta multiplication est naive, elle est naive comment ? "

Bah l'algorithme de base, celui qu'on utilise en primaire pour faire des multiplications.

tu veux dire que tu fais la multiplication de primaire mais en base 10000 ?