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és16733Date d'inscriptionsamedi 31 mai 2008StatutModérateurDernière intervention31 janvier 2024127
>
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.
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és16733Date d'inscriptionsamedi 31 mai 2008StatutModérateurDernière intervention31 janvier 2024127
>
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és8Date d'inscriptionlundi 3 mars 2014StatutMembreDernière intervention25 janvier 2015 13 janv. 2015 à 16:27
merci bcp
Whismeril
Messages postés18991Date d'inscriptionmardi 11 mars 2003StatutContributeurDernière intervention27 mars 2024654 29 oct. 2014 à 09:38
Juste une remarque, ceci relève je pense plus du tuto que de la source non?
KX
Messages postés16733Date d'inscriptionsamedi 31 mai 2008StatutModérateurDernière intervention31 janvier 2024127
>
Whismeril
Messages postés18991Date d'inscriptionmardi 11 mars 2003StatutContributeurDernière intervention27 mars 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és245Date d'inscriptionlundi 22 avril 2013StatutMembreDernière intervention13 mai 20231 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és245Date d'inscriptionlundi 22 avril 2013StatutMembreDernière intervention13 mai 20231 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és245Date d'inscriptionlundi 22 avril 2013StatutMembreDernière intervention13 mai 20231 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és16733Date d'inscriptionsamedi 31 mai 2008StatutModérateurDernière intervention31 janvier 2024127
>
denisbertin
Messages postés245Date d'inscriptionlundi 22 avril 2013StatutMembreDernière intervention13 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és31791Date d'inscriptionsamedi 12 mai 2007StatutWebmasterDernière intervention13 février 20225 27 oct. 2014 à 00:54
Un futur prix Nobel...merde pas en math ni en info. Ca doit être ringard Nobel.^^
26 sept. 2016 à 15:33
Merci beaucoup de répondre, c'est pour un projet de mathématique
26 sept. 2016 à 18:07
L'explication est donnée dans cette partie là de l'article :
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.
15 mars 2015 à 12:57
si n est egal a 4 deja le resultat enorme je me demande quelle serait le resultat si n est egale a un million
15 mars 2015 à 13:45
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 puisque la factorielle est le produit de n entiers entre 1 et n.
Donc
13 janv. 2015 à 16:27
29 oct. 2014 à 09:38
29 oct. 2014 à 10:48
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 ?
28 oct. 2014 à 21:32
28 oct. 2014 à 21:28
27 oct. 2014 à 03:55
Modifié par KX le 27/10/2014 à 08:11
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 ;-)
27 oct. 2014 à 00:54
Modifié par jordane45 le 26/10/2014 à 17:29