Calcul factoriel rapide.
Résolu/Fermé
tony624
Messages postés
128
Date d'inscription
dimanche 27 avril 2008
Statut
Membre
Dernière intervention
14 septembre 2011
-
Modifié par tony624 le 6/03/2011 à 18:54
tony624 Messages postés 128 Date d'inscription dimanche 27 avril 2008 Statut Membre Dernière intervention 14 septembre 2011 - 7 mars 2011 à 21:11
tony624 Messages postés 128 Date d'inscription dimanche 27 avril 2008 Statut Membre Dernière intervention 14 septembre 2011 - 7 mars 2011 à 21:11
A voir également:
- Calcul factoriel rapide.
- Calcul moyenne excel - Guide
- Acces rapide - Guide
- Copie rapide - Télécharger - Gestion de fichiers
- Adresse mail rapide - Guide
- Telechargement rapide - Télécharger - Téléchargement & Transfert
6 réponses
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
Modifié par KX le 6/03/2011 à 23:57
Modifié par KX le 6/03/2011 à 23:57
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
ccm81
Messages postés
10904
Date d'inscription
lundi 18 octobre 2010
Statut
Membre
Dernière intervention
24 décembre 2024
2 428
Modifié par ccm81 le 6/03/2011 à 21:29
Modifié par ccm81 le 6/03/2011 à 21:29
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
tony624
Messages postés
128
Date d'inscription
dimanche 27 avril 2008
Statut
Membre
Dernière intervention
14 septembre 2011
6 mars 2011 à 20:24
6 mars 2011 à 20:24
Merci, mais j'ai déjà testé.
Pour information, j'ai mis 300s pour 6000!.
Pour information, j'ai mis 300s pour 6000!.
tony624
Messages postés
128
Date d'inscription
dimanche 27 avril 2008
Statut
Membre
Dernière intervention
14 septembre 2011
Modifié par tony624 le 6/03/2011 à 22:32
Modifié par tony624 le 6/03/2011 à 22:32
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
tony624
Messages postés
128
Date d'inscription
dimanche 27 avril 2008
Statut
Membre
Dernière intervention
14 septembre 2011
Modifié par tony624 le 6/03/2011 à 23:32
Modifié par tony624 le 6/03/2011 à 23:32
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.
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
6 mars 2011 à 23:50
6 mars 2011 à 23:50
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...
tony624
Messages postés
128
Date d'inscription
dimanche 27 avril 2008
Statut
Membre
Dernière intervention
14 septembre 2011
Modifié par tony624 le 6/03/2011 à 23:56
Modifié par tony624 le 6/03/2011 à 23:56
Je n'avais pas compris pour l'alternance. Ma classe ne peut pas interagir avec les types primitifs.
Du coup ça mets le même temps voir même un peu plus lent 327 au lieu de 300 pour 6000
Du coup ça mets le même temps voir même un peu plus lent 327 au lieu de 300 pour 6000
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
Modifié par KX le 7/03/2011 à 00:22
Modifié par KX le 7/03/2011 à 00:22
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);
tony624
Messages postés
128
Date d'inscription
dimanche 27 avril 2008
Statut
Membre
Dernière intervention
14 septembre 2011
Modifié par tony624 le 7/03/2011 à 01:24
Modifié par tony624 le 7/03/2011 à 01:24
Je viens de tester cette méthode et elle fonctionne mais je pense que je serai limité quand même.
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
Modifié par KX le 7/03/2011 à 07:37
Modifié par KX le 7/03/2011 à 07:37
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.
Patrice33740
Messages postés
8556
Date d'inscription
dimanche 13 juin 2010
Statut
Membre
Dernière intervention
2 mars 2023
1 779
6 mars 2011 à 19:09
6 mars 2011 à 19:09
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)
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
Modifié par KX le 6/03/2011 à 23:12
Modifié par KX le 6/03/2011 à 23:12
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)
