CALCUL DU FACTORIEL DES GRANDS NOMBRES EN TOUTE RAPIDITÉ

pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 - 17 avril 2007 à 16:10
neocracker Messages postés 35 Date d'inscription vendredi 7 février 2003 Statut Membre Dernière intervention 20 février 2009 - 20 févr. 2009 à 04:44
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/42308-calcul-du-factoriel-des-grands-nombres-en-toute-rapidite

neocracker Messages postés 35 Date d'inscription vendredi 7 février 2003 Statut Membre Dernière intervention 20 février 2009
20 févr. 2009 à 04:44
Slt,

Il faut travailler sur un tableau unsigned long où chaque élément du tableau est un chiffre en base 2^64, ensuite il faut appliquer le bon vieux algo de primaire sur ces chiffres. C'est, d'après moi, la méthode avec le meilleur rapport simplicité/vitesse/espace mémoire.

Les changements de base me semble inutile car pour l'ordinateur une addition se fait sur 32 ou 64 bits.

Cordialement

VDB Tristan
LeFauve42 Messages postés 239 Date d'inscription vendredi 20 octobre 2006 Statut Membre Dernière intervention 20 avril 2009
23 avril 2007 à 11:48
Salut,

Je suis d'accord avec coucou747. Tu peux gagner beaucoup de temps en mettant plusieurs chiffres ensemble.

Un bon compromis est de mettre 4 chiffres dans un int 32bits (ou compter en "base 10000"). Comme on peut en stocker jusqu'a 8, ca permet de multiplier deux "chiffres" sans debordement.

Eric
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 44
19 avril 2007 à 02:46
ce qui est interessant c'est de bosser sur une base superieure pour diminuer le nombre d'operations et le nombre de retenues, mais apres, on ne peut plus faire int a ... if a > MAXINT... gerer retenue... on doit faire differement :)

c'est marrant ces libs, avec du Cpp, on peut ajouter des templates, de la surcharge d'operateurs, de l'algebre...
sinon, pourquoi
# printf("%d!\n",k);
# puts(f[k]);

et pas
printf("%d!\n %s\n", k, f[k]); ?
Cyberboy2054 Messages postés 173 Date d'inscription jeudi 20 décembre 2001 Statut Membre Dernière intervention 22 août 2008
18 avril 2007 à 19:43
Je suis impression par l'efficacité de ton programme, alors que la source fait à peine 50 lignes !
elkasimi2007 Messages postés 20 Date d'inscription lundi 19 mars 2007 Statut Membre Dernière intervention 26 mai 2011
18 avril 2007 à 15:23
salut,je précise que mon code sert pour une réponse aléatoire des nombres entre 1 et 1000
et non juste l'affichage des factoriels entre 1 et 1000
pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 11
18 avril 2007 à 09:58
Pour clarifier mon commentaire précédant, je précise que grâce à la routine multiply() ici présente de ELKASIMI2007 j'ai calculé facilement 20000! avec la variante sans le tableau f comme je l'ai indiqué. Par contre, malloc ou pas, je n'ai pas osé utiliser un tableau ayant la taille de 1 560 000 000 octets, cela fait quand même beaucoup. Enfin, 20000! qui se calcule en une minute environ et qui s'écrit avec 77338 chiffres doit être facile à dépasser. Mais si on utilise f il faut augmenter sa taille environ au carré du rapport d'augmentation du nombre dont on cherche le factoriel. En résumé, bravo pour cette incursion inhabituelle dans les très grands nombres.
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
18 avril 2007 à 00:33
Suffit d'un malloc() pour régler le prob de taille.
pgl10 Messages postés 382 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 1 mai 2024 11
17 avril 2007 à 20:20
Effectivement tout dépend de ce que l'on veut faire. Avec la variante qui n'a pas besoin du tableau f on peut, si nécessaire, imprimer chaque factoriel successif dans la boucle : for ... multiply(i);
De plus avec cette variante on peut calculer !20000 il suffit de mettre : #define MAX 78000 Cela ne pose aucun problème.
Mais avec le tableau f cela fait : 1 560 000 000 octets.
elkasimi2007 Messages postés 20 Date d'inscription lundi 19 mars 2007 Statut Membre Dernière intervention 26 mai 2011
17 avril 2007 à 17:42
salut pour le code proposé le temps d'execution pour la liste omplète des nombres
1 ... 1000 est de 24 secondes alors que c'est seulement 264 ms pour l'autre ;)
ta proposition sert principalement a optimiser la memoire du programme mais mon objectif est le calcul rapide des solutions.
a bientot
Rejoignez-nous