Sujet Précédent Sujet Suivant

Calcule de la factorielle pour de grands nombres

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 26 oct. 2014 à 16:45
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 26 sept. 2016 à 18:07
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/100781-calcule-de-la-factorielle-pour-de-grands-nombres
Firerazzer
26 sept. 2016 à 15:33
Tres intéressant cet article, mais j'ai tout de même une question, la méthode par dichotomie permet une optimisation impressionnante ! :o Mais quel est la raison logique de cette optimisation ? Pourquoi faire 30*56 est plus rapide que 120*6 ?
Merci beaucoup de répondre, c'est pour un projet de mathématique
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 127 > Firerazzer
26 sept. 2016 à 18:07
Bonjour,

L'explication est donnée dans cette partie là de l'article :

La taille en mémoire d'un BigInteger va grandir proportionnellement à la valeur qu'il représente. (...) Le temps nécessaire pour effectuer une opération sur deux BigInteger dépend de leurs valeurs respectives. Il est en effet évident que multiplier des nombres de plusieurs Mo est bien plus lent que multiplier des nombres de quelques Ko

Pour illustrer ce fait utilisons plutôt le calcul de k^n = k*k*k*k... n fois
La méthode naïve consiste à dire que k^n=k*k^(n-1) or ce produit va être déséquilibré en taille avec un petit nombre k et un nombre extrêmement grand k^(n-1).
Avec la dichotomie on dit plutôt que k^n=k^(n/2)*k^(n/2) donc les deux membres de l'opération sont de même taille et surtout beaucoup plus petit que le k^(n-1) précédent.

Remarque : ceci n'est vrai que pour les grands nombres qui sont stockés en mémoire avec des tailles dynamiques.
Avec des types primitifs (int, long...) où tout les nombres ont la même taille (4 ou 8 octets en général) ça ne change absolument rien.
irika
15 mars 2015 à 12:57
c est quoi comme resultat n factoriel exposant n factoriel le tout factoriel
si n est egal a 4 deja le resultat enorme je me demande quelle serait le resultat si n est egale a un million
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 127 > irika
15 mars 2015 à 13:45
"c est quoi comme resultat n factoriel exposant n factoriel le tout factoriel"
Clairement la valeur exacte est trop grande pour être calculée. Il faut donc réfléchir en ordre de grandeur, c'est donc plus un problème de maths que d'informatique.

Pour l'ordre de grandeur on a 
n! = O(n^n)
puisque la factorielle est le produit de n entiers entre 1 et n.
Donc 
(n! ^ n!)! = O(((n^n)^(n^n))^((n^n)^(n^n)))
sb53rm Messages postés 8 Date d'inscription lundi 3 mars 2014 Statut Membre Dernière intervention 25 janvier 2015
13 janv. 2015 à 16:27
merci bcp
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 656
29 oct. 2014 à 09:38
Juste une remarque, ceci relève je pense plus du tuto que de la source non?
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 127 > Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024
29 oct. 2014 à 10:48
Je ne suis pas expert dans les us et coutumes de CodeS-SourceS. Pour moi ce n'est ni un code, ni un tutoriel, c'est un snippet :-)

Des codes j'en ai quelques uns sur CS, des fiches pratiques aussi (sur CCM), là c'est un peu à cheval, je présente à la fois mes codes et ma démarche, mais je ne vois pas trop ce que ça ferait dans un tutoriel... apprendre à calculer la factorielle, tout le monde sait le faire, non ?
denisbertin Messages postés 245 Date d'inscription lundi 22 avril 2013 Statut Membre Dernière intervention 13 mai 2023 1
28 oct. 2014 à 21:32
Mais ma calculatrice Ti-57 de l'époque est combe en panne car j'ai voulu relier la touche Run/Stop (elle était programmable avec 50 pas de programmes) à la porte d'entrée de ma chambre de chambre et ainsi obtenir un compteur de présence et d'entrée de ma pièce.
denisbertin Messages postés 245 Date d'inscription lundi 22 avril 2013 Statut Membre Dernière intervention 13 mai 2023 1
28 oct. 2014 à 21:28
En effet sur une calculatrice Texas Instrument Ti-57, le temps de calcul de la factorielle de 69! était de façon perceptible de quelques secondes, idem pour les calculatrices Hewlett Packard HP-41 ainsi bien que Sharp et Casio de l'époque.
denisbertin Messages postés 245 Date d'inscription lundi 22 avril 2013 Statut Membre Dernière intervention 13 mai 2023 1
27 oct. 2014 à 03:55
Pour vérifier la puissance et la célérité de calcul des calculatrices de mes amis en classe d'étude nous nous amusions à comparer le temps d'exécution de la factorielle de 69! avec des calculatrices qui pouvez représenter un nombre au moins égale à 10^98. Ce simple calcul permet de comparer le temps de latence et la vitesse des calculatrices des années 1981 et suivantes.
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 127 > denisbertin Messages postés 245 Date d'inscription lundi 22 avril 2013 Statut Membre Dernière intervention 13 mai 2023
Modifié par KX le 27/10/2014 à 08:11
Dans la mesure où les calculatrices donnent une valeur approchée, je vais prendre la méthode factorielleIterative avec un type double : 69! se calcule chez moi en 70ns...
J'imagine qu'il y avait plus de latence à l'époque, aujourd'hui ce serait compliqué de comparer quoi que ce soit avec une valeur aussi petite ;-)
noctambule28 Messages postés 31791 Date d'inscription samedi 12 mai 2007 Statut Webmaster Dernière intervention 13 février 2022 5
27 oct. 2014 à 00:54
Un futur prix Nobel...merde pas en math ni en info. Ca doit être ringard Nobel.^^
jordane45 Messages postés 38145 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 25 avril 2024 344
Modifié par jordane45 le 26/10/2014 à 17:29
Extra

Discussions similaires

combinaison / factorielle
sacredead -
Chouchou182 -

1 réponse
génerateur de nombre aléatoire
cs_samnick -
rt15 -

8 réponses
factorielle inverse
sk_ -
sk_ -

2 réponses
COMMENT CALCULER LE VOLUME DE MORTIER POUR MONTER UN MUR EN PARPAINGS
STEPH1966 -
STEPH1966 -

5 réponses
Nombre de semaines dans l'année
cs_Macvel -
Macvel -

2 réponses
Rejoignez-nous