Optimisation du calcul de n! pour de très grands nombres
Résolu/Fermé
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
-
Modifié par kasom le 13/01/2013 à 09:20
Utilisateur anonyme - 14 janv. 2013 à 14:45
Utilisateur anonyme - 14 janv. 2013 à 14:45
A voir également:
- Optimisation du calcul de n! pour de très grands nombres
- Optimisation pc - Guide
- Calcul moyenne excel - Guide
- Formule de calcul excel - Guide
- Logiciel calcul plancher bois gratuit - Télécharger - Architecture & Déco
- Optimisation découpe panneau gratuit - Télécharger - Outils professionnels
1 réponse
Utilisateur anonyme
12 janv. 2013 à 19:34
12 janv. 2013 à 19:34
Bonjour
Je n'ai pas la solution, mais une approche quand même.
À partir de la formule de Stirling, il est facile de déterminer le nombre de chiffres de a! et de b!. Le nombre de chiffres de k! est la moyenne arithmétique de ces deux nombres, facile à calculer.
Maintenant il faut 'remonter' la formule du nombre de chiffres pour arriver à k et là, j'avoue que je n'ai rien de très efficace à proposer. Une table de valeurs précalculées peut-être, ou la méthode de Newton, mais ça reste lourd.
Je n'ai pas la solution, mais une approche quand même.
À partir de la formule de Stirling, il est facile de déterminer le nombre de chiffres de a! et de b!. Le nombre de chiffres de k! est la moyenne arithmétique de ces deux nombres, facile à calculer.
Maintenant il faut 'remonter' la formule du nombre de chiffres pour arriver à k et là, j'avoue que je n'ai rien de très efficace à proposer. Une table de valeurs précalculées peut-être, ou la méthode de Newton, mais ça reste lourd.
12 janv. 2013 à 19:55
En fait pour l'instant je suis parti sur un calcul de logarithmes, ce qui est plus rapide et moins coûteux que des calculs de factoriels, puisque l'on manipule toujours des doubles (le temps de calcul est donc constant quelque soit les valeurs manipulées)
J'ai donc un tableau des ln(n!) ce qui se calcule tout simplement en faisant tab[n]=ln(n)+tab[n-1]
Puis j'ai b!/k! ≈ k!/a! ==> k!² ≈ a! * b! ==> 2*ln(k!) ≈ ln(a!)+ln(b!) ==> ln(k!) ≈ [ln(a!)+ln(b!)]/2
En faisant une recherche par dichotomie sur mon tableau de log(n!) j'obtiens immédiatement un intervalle [n,n+1] dans lequel se trouve k. En pratique, k vaudrait soit n, soit n+1 vu qu'il est entier mais pour ma courbe j'ai laissé une valeur décimale pour que ce soit plus lisse.
Mais à la limite le problème n'est pas là., car une fois dessinée ma courbe semble très régulière, il doit donc y avoir une équation "simple" derrière, et sous réserve qu'il n'y ait que quelques paramètres à régler, j'ai bon espoir de pouvoir les déterminer. Le problème c'est que je ne sais pas quelle tête peut bien avoir l'équation de cette surface en forme de "plan incurvé"...
Modifié par le père. le 12/01/2013 à 23:19
en log décimaux ou naturels, c'est la même chose. Et en log décimaux, log(x) c'est bien le nombre de chiffres de x (pas exactement, mais pour les grands nombres ça ne change pas grand chose). Le nombre de chiffres de k! est bien la moyenne arithmétique de ceux de a! et b!, nous parlons bien de la même chose.
L'intérêt de la formule de Stirling est de permettre le calcul direct (et non pas de manière itérative) de ln(a!) uniquement avec des doubles aussi, sans avoir besoin de tout stocker dans un tableau qui risque d'être énorme si tu veux calculer 1000000!
a et b étant donnés, le calcul de log(k!) est donc immédiat avec des doubles. Le problème est de remonter à k, on connaît très bien la tête de la courbe (toujours plus simple qu'une surface) mais ça ne veut pas dire que ce soit facile.
13 janv. 2013 à 00:04
Voici l'algo pour retrouver k à partir de a et b
k(0)=(a * ( ln(a) -1) + b * ( ln(b) -1))/2
k(i+1) = (k(i)+k(0))/ln(k(i)
Très facile à tester avec un tableur, pour vérifier la convergence (que je ne sais pas prouver). On vérifie aussi sa validité sur des petits nombres, ce qui est étonnant compte-tenu des approximations.
13 janv. 2013 à 00:07
Oups. Effectivement ^^
"sans avoir besoin de tout stocker dans un tableau qui risque d'être énorme"
Evidemment, l'intérêt de mon tableau était uniquement pour déterminer quelques valeurs de k pour tracer la courbe et en déduire une loi générale...
"L'intérêt de la formule de Stirling est de permettre le calcul direct (...) de ln(a!)"
La formule de Stirling donne une approximation de la factorielle (une équivalence à l'infini), pas la valeur exacte. Moi je m'intéresse à la valeur exacte de la factorielle.
Mais je viens de regarder cette équivalence de Sterling, et la seule chose que je peux en tirer (au moins pour ce soir) c'est que dans le cas simple : n! = k!² (la première itération de ma dichotomie), on n'a pas k=n/2 à l'infini (c'est ce que j'utilisais jusqu'à présent en pensant que c'était judicieux).
Si n~2k j'applique la formule de Sterling sur k et 2k, et en simplifiant je trouve (e/4k)^k ~ √2 ce qui est bien évidemment faux car (e/4k)^k → 0
Je vais regarder également l'algo que tu viens de me donner. Bonne soirée.
13 janv. 2013 à 00:46
J'ai bien conscience que c'est le but ultime, mais pour l'évaluation de k, une approximation peut faire l'affaire. Sauf bien sûr si tu tiens à choisir le k exactement optimal.
je trouve (e/4k)^k ≈ √2
Je ne vois pas comment tu arrives à ce résultat à partir de la formule de Stirling appliquée à k et 2k... Je n'arrive pas à faire disparaître k! ni (2k)!