Il y a quelques temps j'ai trouvé une formule pour les factorielles (et il ne me semble pas l'avoir vu ailleurs). Du coup je me dis que je pourrais un peu l'expliquer ici, peut-être que ça vous intéressera. :3
La formule en question est celle-ci :
Pour arriver à ça il faut d'abord suivre un méthode analogue à celle de Gauss pour calculer la somme d'une suite arithmétique. Mais au lieu d'additionner dans les deux sens, il faut multiplier. Et comme je ne suis pas très clair ici, je préfère mettre un exemple :
D'où :
On peut ainsi organiser les résultats ( (n!)² ) sous forme de triangle :
(d'ailleurs ce triangle correspond à ça)
Il faut donc maintenant trouver une formule pour exprimer la produit des termes de la nième ligne du triangle (c'est à tâtons que j'ai fini par trouvé ce qu'il fallait... ^^), on se retrouve donc avec
Bien sûr, elle peut être vérifiée avec une petite récurrence :
Soit P(n) la propriété définie pour tout entier naturel n non nul, par
Initialisation :
Pour n = 1, on a
Or 1! = 1
Ainsi P(1) est vraie.
Hérédité :
On suppose que P(n) est vraie pour un entier naturel n non nul.
Et on démontre que P(n+1) est vraie, cest-à-dire
D'après l'hypothèse de récurrence :
Donc! = \sqrt{\prod_{k=0}^{n-1}(n-k)(k+1)} \times (n+1))
! = \sqrt{\prod_{k=0}^{n-1}(n-k)} \times \sqrt{n+1} \times \sqrt{\prod_{k=0}^{n-1}(k+1)} \times \sqrt{n+1})
Ainsi P(n+1) est vraie.
Conclusion :
Alors, bien sûr, cette formule n'est pas très utile si on souhaite trouver les factorielles à la main, mais il me semble qu'elle permet d'avoir un algorithme un peu moins gourmand en temps pour les calculer (je ne m'y connais pas plus que ça en complexité temporelle).
Bref, voilà ce que ça donne en C++ avec GMP (pour gérer les grands nombres) : http://akrotrili.tk/Stuff/factorial.txt
Avec ça j'ai pu calculer 255209! en moins de 10s. Mais pas plus, parce qu'il me semble que je manque de mémoire.
Voilà, ce sera tout. \o
