CALCUL DU FACTORIEL DES GRANDS NOMBRES EN TOUTE RAPIDITÉ
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 2023
-
17 avril 2007 à 16:10
neocracker
Messages postés35Date d'inscriptionvendredi 7 février 2003StatutMembreDernière intervention20 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.
neocracker
Messages postés35Date d'inscriptionvendredi 7 février 2003StatutMembreDernière intervention20 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és239Date d'inscriptionvendredi 20 octobre 2006StatutMembreDernière intervention20 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és12303Date d'inscriptionmardi 10 février 2004StatutMembreDernière intervention30 juillet 201244 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és173Date d'inscriptionjeudi 20 décembre 2001StatutMembreDernière intervention22 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és20Date d'inscriptionlundi 19 mars 2007StatutMembreDernière intervention26 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és380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 202311 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és21040Date d'inscriptionjeudi 23 janvier 2003StatutModérateurDernière intervention21 août 2019 18 avril 2007 à 00:33
Suffit d'un malloc() pour régler le prob de taille.
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 202311 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és20Date d'inscriptionlundi 19 mars 2007StatutMembreDernière intervention26 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
20 févr. 2009 à 04:44
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
23 avril 2007 à 11:48
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
19 avril 2007 à 02:46
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]); ?
18 avril 2007 à 19:43
18 avril 2007 à 15:23
et non juste l'affichage des factoriels entre 1 et 1000
18 avril 2007 à 09:58
18 avril 2007 à 00:33
17 avril 2007 à 20:20
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.
17 avril 2007 à 17:42
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