Calcul factoriel rapide.
Résolu
tony624
Messages postés
128
Date d'inscription
Statut
Membre
Dernière intervention
-
tony624 Messages postés 128 Date d'inscription Statut Membre Dernière intervention -
tony624 Messages postés 128 Date d'inscription Statut Membre Dernière intervention -
A voir également:
- Calcul factoriel rapide.
- Acces rapide - Guide
- Calcul moyenne excel - Guide
- Copie rapide - Télécharger - Gestion de fichiers
- Calcul km marche à pied gratuit - Télécharger - Sport
- Telechargement rapide - Télécharger - Téléchargement & Transfert
6 réponses
Première remarque : on ne sait pas dans quel langage tu codes !
Ensuite pour commencer, regardes mon post (ici) écrit il y a deux semaines.
Sinon une idée pourrait être de ne pas calculer (n+2)! = (n+2)*[(n+1)*[n!]]
Mais plutôt de calculer (n+2)! = [(n+2)*(n+1)]*n!
La différence est subtile mais on peut gagner pas mal de calculs comme ça, en effet n étant un "petit" nombre (un long suffit) alors (n+2)*(n+1) se calcule rapidement, ainsi au lieu de faire deux multiplications de grands nombres on ne fait plus qu'une multiplication de grand nombre et une multiplication de petit nombre.
Maintenant je vais manipuler un peu les maths pour gagner encore plus en remplaçant des opérations sur des grands nombres par des opérations moins coûteuses sur des petits nombres.
Limites de ma méthode :
Quand je dis des petits nombres, je parle de long en Java (ou long int en C), ce qui nous laisse la liberté de calculer n! avec n allant jusqu'à N=2^63, voire N=2^64 si on considère les types non signés...
Vu les calculs que j'ai fait au-dessus, je dois m'assurer que tous les résultats obtenus par mes multiplications de petits nombres soient inférieurs à cette limite N.
Donc : (n+4)*(n+3)*(n+2)*(n+1) < N
Du coup cette méthode nous limite à ne pas dépasser n=2^15.75 pour N=2^63 et n=2^16 pour N=2^64.
Au delà il faudra se limiter à ma première simplification (n+2)!=(n+1)*(n+2)
Et ce jusqu'à n=2^31.5 pour N=2^63 et jusqu'à n=2^32 pour N=2^64
Evidemment, on peut également implémenter une méthode intermédiaire :
(n+3)! = [(n+3)*(n+2)*(n+1)]*n!
Dans ce cas on a n=2^21 pour N=2^63 et n=2^21.33 pour N=2^64
La confiance n'exclut pas le contrôle
Ensuite pour commencer, regardes mon post (ici) écrit il y a deux semaines.
Sinon une idée pourrait être de ne pas calculer (n+2)! = (n+2)*[(n+1)*[n!]]
Mais plutôt de calculer (n+2)! = [(n+2)*(n+1)]*n!
La différence est subtile mais on peut gagner pas mal de calculs comme ça, en effet n étant un "petit" nombre (un long suffit) alors (n+2)*(n+1) se calcule rapidement, ainsi au lieu de faire deux multiplications de grands nombres on ne fait plus qu'une multiplication de grand nombre et une multiplication de petit nombre.
Maintenant je vais manipuler un peu les maths pour gagner encore plus en remplaçant des opérations sur des grands nombres par des opérations moins coûteuses sur des petits nombres.
(n+4)! = (n+4)*[(n+3)*[(n+2)*[(n+1)*[n!]]]] // 4 additions de petits nombres
// 4 multiplications de gds nombres
= [[(n+4)*(n+1)]*[(n+2)*(n+3)]]*n!
= [(n²+5n+4)*(n²+5n+6)]*n!
= [[n*(n+5)+4]*[n*(n+5)+6)]]*n!
m = n*(n+5) // 1 addition et 1 multiplication de petits nombres
(n+4)! = [(m+4)*(m+6)]*n! // 2 additions et une multiplication de petits nombres
// 1 seule multiplication de grands nombres
Limites de ma méthode :
Quand je dis des petits nombres, je parle de long en Java (ou long int en C), ce qui nous laisse la liberté de calculer n! avec n allant jusqu'à N=2^63, voire N=2^64 si on considère les types non signés...
Vu les calculs que j'ai fait au-dessus, je dois m'assurer que tous les résultats obtenus par mes multiplications de petits nombres soient inférieurs à cette limite N.
Donc : (n+4)*(n+3)*(n+2)*(n+1) < N
Du coup cette méthode nous limite à ne pas dépasser n=2^15.75 pour N=2^63 et n=2^16 pour N=2^64.
Au delà il faudra se limiter à ma première simplification (n+2)!=(n+1)*(n+2)
Et ce jusqu'à n=2^31.5 pour N=2^63 et jusqu'à n=2^32 pour N=2^64
Evidemment, on peut également implémenter une méthode intermédiaire :
(n+3)! = [(n+3)*(n+2)*(n+1)]*n!
Dans ce cas on a n=2^21 pour N=2^63 et n=2^21.33 pour N=2^64
La confiance n'exclut pas le contrôle
bonsoir,
un debut peut être
on doit pouvoir recupérer le nombre de 0 provenant de multiples de 10 dans n, par exemple si n = 100, il y a 11 zéros provenant des multiples de 10
on peut aller plus loin avec des 0 provenant des 5x2
bon courage
un debut peut être
on doit pouvoir recupérer le nombre de 0 provenant de multiples de 10 dans n, par exemple si n = 100, il y a 11 zéros provenant des multiples de 10
on peut aller plus loin avec des 0 provenant des 5x2
bon courage
Oui, c'est vrai que je gagnerais du temps si je n'avais pas les zéros à gérer.
Je vais chercher de ce coté mais je suis ouvert à d'autres propositions.
Merci.
Je vais chercher de ce coté mais je suis ouvert à d'autres propositions.
Merci.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Désolé KX, ta réponse n'apparaissait pas. Dommage parce qu'elle est très intéressante. Je viens de finir la gestion des zéros et je sais pas pourquoi le calcul est beaucoup plus long. Ce qui n'est pas logique. Mais bon de toute façon ta méthode à l'air très bien je vais y regarder de plus prés.
Je code en C++. Et j'utilise ma propre classe d'entier non signé.
J'étais déjà passé par ce post.
Merci.
Je code en C++. Et j'utilise ma propre classe d'entier non signé.
J'étais déjà passé par ce post.
Merci.
Je pense que ma réponse n'apparaissait pas car je n'ai pas arrêté de la modifier pour essayer d'être le plus précis et le plus complet possible. Mais ma réponse telle qu'elle est maintenant me convient et je ne devrais plus y toucher ;-)
Evidemment toute ma méthode repose sur l'alternance entre les calculs avec ta classe d'entier (plus lente mais dont les valeurs sont bien plus grandes) et les calculs standards (très rapides mais assez vite limités en amplitude) et sur quelques astuces de maths élémentaires...
Evidemment toute ma méthode repose sur l'alternance entre les calculs avec ta classe d'entier (plus lente mais dont les valeurs sont bien plus grandes) et les calculs standards (très rapides mais assez vite limités en amplitude) et sur quelques astuces de maths élémentaires...
Je ne sais pas comment tu as fait ta classe, mais il doit bien y avoir une méthode ou mieux un constructeur qui te créé un grand nombre à partir d'une valeur.
J'avoue que ça me paraît être un minimum pour une classe de grand nombre...
Remarque : si ta méthode n'existe pas tu peux toujours la créer, c'est très facile.
Je suppose que tu as tes deux valeurs "Zero" et "Un" (c'est généralement comme ça que l'on fait)
J'avoue que ça me paraît être un minimum pour une classe de grand nombre...
Remarque : si ta méthode n'existe pas tu peux toujours la créer, c'est très facile.
Je suppose que tu as tes deux valeurs "Zero" et "Un" (c'est généralement comme ça que l'on fait)
const Entier Deux = Un + Un;
Entier convertir(const unsigned long int n)
{
if (n<2)
return (n==0) ? Zero : Un;
else
return Deux*convertir(n/2) + (n%2==0) ? Zero : Un;
}
Entier e = convertir(12);
Tout dépend après de ton implémentation des grands nombres, il faut tout optimiser !
En général quand on parle de grand nombres on parle de grandes bases, dans ta liste utilises-tu tous les caractères (base 256) ou juste les 10 premiers ?
Pour le produit as-tu penser à utiliser un algoritme efficace (Karatsuba, ou Toom-Cook par exemple) ?
Et ta somme ? C'est moins important pour le calcul de la factorielle, mais il faut y penser...
Remarque : pour l'algo de 'Entier convertir(long)' on peut encore l'optimiser en utilisant une méthode 'Entier doubler(Entier)' optimisée plutôt que d'utiliser la multiplication générique par Deux.
En général quand on parle de grand nombres on parle de grandes bases, dans ta liste utilises-tu tous les caractères (base 256) ou juste les 10 premiers ?
Pour le produit as-tu penser à utiliser un algoritme efficace (Karatsuba, ou Toom-Cook par exemple) ?
Et ta somme ? C'est moins important pour le calcul de la factorielle, mais il faut y penser...
Remarque : pour l'algo de 'Entier convertir(long)' on peut encore l'optimiser en utilisant une méthode 'Entier doubler(Entier)' optimisée plutôt que d'utiliser la multiplication générique par Deux.
On peut utiliser un calcul récursif :
n! = n x (n-1)! (avec si n=0, n!=1)
n! = n x (n-1)! (avec si n=0, n!=1)
Le calcul récursif est mauvais pour de très grand nombres, la pile d'appel récursive n'est pas suffisamment grande pour se permettre d'aller trop loin !
En Java par exemple on ne peux guère dépasser n=25000 (voir mon post : ici)
En Java par exemple on ne peux guère dépasser n=25000 (voir mon post : ici)
