Calcule de la factorielle pour de grands nombres

Signaler
Messages postés
16331
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
8 mai 2021
-
Messages postés
16331
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
8 mai 2021
-
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

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
Messages postés
16331
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
8 mai 2021
118 > Firerazzer
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
Messages postés
16331
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
8 mai 2021
118 > irika
"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)))
Afficher les 13 commentaires