CALCUL DE LA FACTORIELLE D'UN NOMBRE AVEC TOUS SES CHIFFRES (AUCUNE LIMITE !)
cs_Jack
Messages postés
14006
Date d'inscription
samedi 29 décembre 2001
Statut
Modérateur
Dernière intervention
28 août 2015
-
5 août 2005 à 17:01
cs_orelec Messages postés 7 Date d'inscription dimanche 4 juin 2006 Statut Membre Dernière intervention 15 octobre 2006 - 15 oct. 2006 à 23:40
cs_orelec Messages postés 7 Date d'inscription dimanche 4 juin 2006 Statut Membre Dernière intervention 15 octobre 2006 - 15 oct. 2006 à 23:40
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/33064-calcul-de-la-factorielle-d-un-nombre-avec-tous-ses-chiffres-aucune-limite
https://codes-sources.commentcamarche.net/source/33064-calcul-de-la-factorielle-d-un-nombre-avec-tous-ses-chiffres-aucune-limite
15 oct. 2006 à 23:40
Dernires remarques concernant le calcul scientique, il faut lire :
À noter que les plate-formes Solaris ont une précision (pour le même type de variables) ayant le double de décimales par rapport aux PC.
15 oct. 2006 à 23:33
J'apporte cette précision car mon commentaire n'en laisse rien paraître. Mais la façon et les résultats obtenus sous Java sont proportionnellement similaires à ceux obtenus sous d'autres langages. Pourquoi Microsoft a sorti la plate-forme .NET si Java est aussi lent que certains le prétendent ?
Quant aux tableaux de chaînes ils ne sont intéressants que si l'on y met des valeurs distinctes pour un calcul. Exemple :
sommeCumulée(String[] arguments)
Une somme de plusieurs éléments sera implémentée en utilisant ce code Java schématique :
String somme(String[] listeArguments){
x = liste.length; // nombre d'éléments en entrée
y = sommeCumulée(liste); // résultats initiaux
résultat y[x]; // résultat dernier de la liste
}
C'est du naïf mais on ne réécrit pas de code existant. Mais avec de multiples fichiers cela devient ingérable à cause de la quantité de RAM nécessaire 2 Go pour le fichier + XP et ce avant de faire un calcul avec ce fichier... On voit donc que les valeurs que j'ai données sont purement théoriques. En fait il faudrait s'en tenir à une valeur moyenne abordable pour toutes les machines, le Go semble être la meilleure.
Remarques sur la factorielle
Je viens de passer pas mal de temps à accélerer mon noyau naïf mais j'ai eu droit à de belles surprises mais l'opération n'est pas terminée
1- L'algorithme classique va de X vers 0. J'ai obtenu le temps suivant pour 1500 : 89 secondes avec int[]. En montant de 1 vers x : 34 secondes ! soit -60%. En conclusion plus on augmente progressivement la taille du résultat plus le calcul est rapide.
2- Le passage du type int[] à long[] permet seulement de passer de 34 à 21 secondes soit -40% (= 75% au total). Plus on utilise une grande valeur entière moins la performance progresse.
3- L'algorithme en lui-même est trop lent. Exemple :
1! = 1 // classique
2! = 1*2 // classique
3! = 1*2*3 // classique
4! 1*2*3*4 1*2^3*3 // modifié
5! 1*2*3*4*5 1*2^3*3*5 // modifié
6! 1*2*3*4*5*6 1*2^4*3^2*5 // modifié
Le secret s'appelle la factorisation, l'on se contente de simplifier les multiples de 2 le gain est d'un peu de 50% à cause du calcul de la puissance de 2. Et plus il y a de multiples plus il faut prévoir leurs interactions...
Je n'ai pas essayé mais cela doit en valoir le coup mais j'ai d'autres projets en tête.
À US_30 : au quotidien à cause du temps de calcul et pour être franc j'ai un Athlon XP 2600 en 32 bitsà 2 GHz. Trouve moi une application 64 bits de calcul si tu en trouves parce que même en dehors de ce domaine c'est Apple contre PC...
Les erreurs d'arrondis viennent du fait que les nombres réels contiennent beaucoup de nombres infinis (quand ils ne sont pas transcendants). Il faut donc éviter les approximations et faire du calcul exact comme les Texas (89 et 92 entre autres), ce qui est loin d'être une promenade de santé.
À VIOLENT_KEN : mon programme est comme le tiens : mon premier projet informatique. Et comme tu l'auras compris c'est pour le quotidien. Et au vu des résultats le tien est plus rapide mais j'utilise mon noyau de calcul à base de String et de long[] et la multiplication n'est pas optimisée.
Si tu n'as pas compris la remarque sur le cast, c'est parce que tu ne sais pas ce qu'est un cast, ou en français, une conversion de type. J'espère que mes explications te seront utiles et sont basées sur mon code en Java. Exemple (calcul de 10^x, x positif):
static String pow10(String x, String y){
int z = Integer.parseInt(y); // conversion de String vers entier
int j = (int) Math.floor(y / 10);
String result = x;
if (j != <0)
for (int i = 0; i < j i++)
result = result.concat("0000000000");
j = z - result.length();
result = result.concat(ZEROS[j]);
return result;
}
Zeros[] est une chaîne Static située en dehors de la méthode mais dans sa classe. Static permet de l'utiliser dans les méthodes de la classe. Elle comporte 10 chaînes, la première est vide, à la suivante on a "0", puis à chaque fois on ajoute un zéro, la dernière en a neuf.
Bien que ce soit du Java le code est clair sauf :
int j = (int) Math.floor(y / 10);
Parce que les tableaux sont basés sur des nombres entiers il nous en faut un. Sans le cast Java plante au débogage parce que Math.floor retourne un double. Remarques les deux int en entrée !
En fait tous les langages de programmation le font. Je te donnerai la règle plus tard. Pour passer de double à int on réalise un cast qui est dit "explicite". Ce type de cast est réalisé par le développeur, mais pas ce cast dit "implicite" qui lui se fait automatiquement comme pour Math.floor.
La règle des casts implicites est la suivante :
flottant flottant = flottant (le plus grand en entrée)
entier flottant = flottant
entier entier = entier (le plus grand en entrée)
Le plus grand en entrée veut dire que s'il y a un 16 et un 32 bits en entrée la sortie doit être en 32 bits. À noter que l'on peut aussi faire un cast dit de "réduction". C'est-à-dire que l'on réduit le nombre de bits du type primitif.
J'espère que ce n'est plus incompris pour toi.
Dernière remarque concernant le calcul scientifique :
Le premier langage de programmation (le Fortran apparu en 1954) est encore très utilisé dans les labo à cause de sa facilité d'apprentissage et il n'a pas 16 décimales en précision mais accélère les simulations numériques. À noter les plate-formes sont ont une précision (pour le même type de variables) ayant le double de décimales par rapport aux PC.
15 oct. 2006 à 19:36
Donc on doit se rabattre (même si c'est relativement moche) sur la création de n fichiers de 2Go chacun contenant tous une partie du nombre calculé.
@+
15 oct. 2006 à 19:32
String dynamique ou non n'y changera rien.
15 oct. 2006 à 19:06
"Dim N, R(100000), M, MAX, K, RET, S, B, A, C2, C1, E4, E5, B2, L, L1, C, bouc1, bouc2, bouc3, bouc4, CX, CY As Double "
est inadmissible ;)
J'aurais bien updaté cette source si j'avais eu le temps...
@+
15 oct. 2006 à 19:03
Ce qui implique plusieurs choses :
-mon excès d'orgueil dans le titre et la description du code
-un code très très peu optimisé (il n'y a qu'à voir les déclarations catastrophiques que je fais)
-le manque de commentaires pertinents
-un code fort peu clair (Goto à bannir...etc.)
Donc cette source est pas très bonne, "programmaticalement" parlant.
Mais bon, je réponds au premier "nouveau" commentaire :
"À vrai dire, la taille maximale d'un fichier sous XP est de 2 Go (2^31 exactement, soit 2 147 483 648 octets)."
> Faux. A la rigueur sous FAT32, mais on peut monter bien au dela sur une partition NTFS.
Cela dit, le type string est en effet limité à 2^31 octets, et c'est bien là qu'il existe une limitation, mais on peut envisager de créer un tableau dynamique de strings pour éviter cette limite. Sans doute étais-ce le propos ?
"Plus la factorielle est grande plus il faut de temps de calcul et de ressources. Votre algorithme (bien qu'il y a deux programmes différents mais un seul modèle mathématique) n'est pas des plus rapides"
> Certes non, mais ce n'est pas son but : il n'y a qu'à voir la structure bancale - sans parler de l'algorithme mathématique - qu'il a ==> performances minables.
"mais il a le mérite d'être un peu au-dessus des algorithmes dits naïfs"
> Son seul but est de donner une précision importante.
"Il faut savoir qu'en calcul scientifique (notamment en modélisation) en utilise au maximum 32 décimales voire 64 (on en connaît 4 milliards pour pi). Le seul intérêt dans le cas présent est de vouloir faire des calculs précis en combinatoire, du genre n! / (n - k)! et autres. Encore faut-il écrire la division..."
> Le seul intérêt est de calculer une factorielle avec ses chiffres exacts. Pourquoi ? Pour la prouesse mathématique.
Si l'on se contente de 32 décimales, alors autant utiliser une approximation de la fonction Gamma.
"Sans parler des fonctions associées (soustraction, multiplication et addition)."
> Il existe une source sur vbfrance.com (opération sur les grands nombres, il me semble) pour réaliser ceci ;)
"Quoiqu'il en soit cela est intéressant dans le cadre de ce code mais scientifiquement peu utilisable au qoutidien..."
> Certes, mais ce n'est pas le but. Personnellement, je réalise mes calculs scientifiques avec Matalb, ou Maple pour le formel. Pas avec VB6. Et encore moins avec une précision de cette taille.
Remarquons que la majeure partie des sources présentes sur vbfrance ne servent pas au quotidien.
"Dernier détail : lorsque que l'on travaille avec des entiers en entrée il est recommandé d'utiliser le même type primitif en sortie (Int* ou Decimal) à cause du cast implicite"
> Je n'ai pas compris cette remarque ;)
Concernant la remarque de US_30
"Ensuite, faire un calcul avec les grands nombres, permet d'obtenir une meilleur précision, et cela devient vite nécessaire lorsqu'on calcule avec beaucoup de nombre (comme avec le calcul matriciel). Les erreurs d'arrondies deviennent dans ce cas non négligeables... et la seule parade, c'est de calculer avec plus de chiffre..."
> Tout à fait. Travailler en double précision n'est pas suffisant pour certains calculs, d'où une nécessité de travailler avec un maximum de chiffres exacts.
Mais je suis évidemment d'accord sur le fait que cette source, dans l'utilisation qui peut en être faite, n'a que peu d'intérêt.
Pour conclure sur les performances de cette source : je pense que l'on peut raisonnablement diviser par 2 le temps de calcul en reprogrammant légèrement le programme (au niveau du typage de données et des structures itératives).
Merci pour ces commentaires constructifs, @+
15 oct. 2006 à 17:58
Je réagi !
"Quoiqu'il en soit cela est intéressant dans le cadre de ce code mais scientifiquement peu utilisable au qoutidien..."
Ceci n'est pas vrai. Certes, il faut posséder plus de calcul pour en faire vraiment quelque chose, mais... C'est long de programmer tout cela, donc c'est déjà un début qui a le mérite d'exister, pouvant inspirer.
Ensuite, faire un calcul avec les grands nombres, permet d'obtenir une meilleur précision, et cela devient vite nécessaire lorsqu'on calcule avec beaucoup de nombre (comme avec le calcul matriciel). Les erreurs d'arrondies deviennent dans ce cas non négligeables... et la seule parade, c'est de calculer avec plus de chiffre...
Amicalement,
Us.
15 oct. 2006 à 01:20
À vrai dire, la taille maximale d'un fichier sous XP est de 2 Go (2^31 exactement, soit 2 147 483 648 octets). En Java et tout ce qui est codé Unicode on obtient le quart de cette capacité à cause du codage sur 4 octets, il faut alors stocker sous format ASCII.
En entrée de type chaîne (données respectivement pour Java et .NET et le type primitif associé):
- 32 677 vers short et Int16;
- 2 147 483 647 vers int et Int32;
- 9 223 372 036 854 775 807 vers long et Int64;
- 79 228 162 514 264 337 593 543 950 335 vers Decimal (pas d'équivalent Java).
Le type int ou Int32 suffit amplement mais en réalité il est rare d'utiliser de si grandes valeurs.
Considérations générales :
Plus la factorielle est grande plus il faut de temps de calcul et de ressources. Votre algorithme (bien qu'il y a deux programmes différents mais un seul modèle mathématique) n'est pas des plus rapides mais il a le mérite d'être un peu au-dessus des algorithmes dits naïfs. Toutefois il faut faire un distingo :
- donner un exemple de programme simple pour dépasser les capacités de calcul avec des variables de type primitifs;
- écrire un programme rapide en dépassant ces mêmes capacités.
Il faut savoir qu'en calcul scientifique (notamment en modélisation) en utilise au maximum 32 décimales voire 64 (on en connaît 4 milliards pour pi). Le seul intérêt dans le cas présent est de vouloir faire des calculs précis en combinatoire, du genre n! / (n - k)! et autres. Encore faut-il écrire la division...
Sans parler des fonctions associées (soustraction, multiplication et addition).
Quoiqu'il en soit cela est intéressant dans le cadre de ce code mais scientifiquement peu utilisable au qoutidien...
Dernier détail : lorsque que l'on travaille avec des entiers en entrée il est recommandé d'utiliser le même type primitif en sortie (Int* ou Decimal) à cause du cast implicite
13 mai 2006 à 17:38
Code très intéressant.Il m'aidera pour mes sources à venir
Je viens de le tester
10/10
A plus
JP
7 août 2005 à 10:05
ET bien, regarde mon algo , c'est parfaitement le même schéma en plus court... Donc, il me semble que tu avais codé exactement la même chose que moi (dans la base 9), mais avec des longueurs en plus... Bon, j'espère que je ne vais pas te décourager en disant cela, car l'idée était bonne. La preuve, je l'ai codé ! Aller je te mets un 10/10 d'encouragement... en espérant te revoir dans d'autres bonne idée d'algorithme...
Bonne programmation,
Us.
7 août 2005 à 09:30
MAX = Int((Int((0.92 + (N + 0.5) * Log(N) - N) / Log(10)) + 1) / 9) + 1
Connaître d'avance la valeur MAX, permet de supprimer toutes les références de celui-ci dans la boucle. Gain de temps assuré ! Mais le mieux, c'est de noter comme dans algo, de cette façon :
'Nombre d'indice dans la base
Expo = 9
MAX = Int((0.92 + (N + 0.5) * Log(N) - N) / Log(10)) + 1 'nb chiffre de N!
MAX = Int(MAX / Expo) + 1
Car de cette façon, on peut changer la base de calcul, pour tester s'il est préférable d'utiliser des déclarations de type Long ou Double.
Voilà, c'était une p'tit plus...
A+
Us.
6 août 2005 à 09:58
Merci à us_30 pour toutes ses remarques constructives, j'en prend compte et je m'efforce de vous commenter l'algorithme mathématique.
Bientôt la nouvelle mise à jour !
6 août 2005 à 09:48
J'ai la seconde repris ton code (enfin un peu). Je n'ai pas touché à la structure des boucles, car j'ai du mal à bien cerner le principe de calcul. Néanmoins, je rajoute aux remarques de cette nuit ceci :
- La boucle :
For L1 = 1 To L
ef = ef & "0"
Next L1
peut être remplacé par l'équivalent et plus rapide :
ef = ef & String(L, "0")
- CX et CY ne rentrent dans aucun calcul, et peut être supprimés.
- Dans la boucle For : les variables K et S n'ont plus le même sens que dans Do while. Surtout S qui passe d'un type double à un type long.
Enfin j'ai tout remis (enfin presque) dans la Sub-command et voici ce que cela donne :
==
Private Sub Command1_Click()
temps = Timer
'récupération de N en fct de text1.text
Dim N As Long
N = Val(Text1.Text)
'vérification de N
If N <0 Then MsgBox "Nombre incorrect", vbCritical: Text1.Text vbNullString: Exit Sub
'définitions des variables
Dim R(100000) As Double, S As Double
Dim K As Long, M As Long, MAX As Long
Dim E4 As Long, E5 As Long
Dim L As Long, L1 As Long
Dim RET As Long, B As Long, C2 As Long
Dim C1 As Double, B2 As Double, C As Double
Dim t As Long
Dim ef As String
'initialisation des variables
R(1) = 0.00001
M = 2
MAX = 1
E5 = 100000
E4 = 10000
Do While M <= N
DebutWhile:
S = R(K)
B = Int(S)
C = (RET + Int(E5 * (S - B) + 0.5) * M) / E5
C2 = Int(C)
C1 = Int(E5 * (C - C2) + 0.5) / E5
B2 = B * M + C2
If B2 >= E4 Then
'deuxième série
B2 = B2 / E4
RET = Int(B2)
R(K) = Int(0.5 + (B2 - RET) * E4) + C1
K = K + 1
If K <= MAX Then GoTo DebutWhile
R(K) = RET / E5
MAX = MAX + 1
If MAX > 10000 Then End
GoTo Increm
End If
R(K) = B2 + C1
RET = 0
If K <> MAX Then K = K + 1: GoTo DebutWhile
Increm:
'incrémentation de M; fin de la 'multiplication'
M = M + 1
K = 1
RET = 0
Loop
For t = MAX To 1 Step -1
S = Int(0.5 + R(t) * E5)
If S = 0 Then
L = 8
Else
L = 8 - Int(Log(S + 0.5) / Log(10))
If L 0 Or t MAX Then GoTo CreateString
End If
ef = ef & String(L, "0")
CreateString:
ef = ef & S 'rajoute le nouveau chiffre S au résultat
Next t
'Affichage de la durée d'exécution
MsgBox "Durée : " & Timer - temps
'CreateFile
chemin$ = App.Path & "mes documents"
Open chemin$ & "factorielle de " & N & " .txt" For Output As #1
Print #1, ef 'écriture
Close #1
MsgBox "Le fichier a été créé dans " & chemin$, vbOKOnly
End 'fin
End Sub
Private Sub Text1_KeyDown(KeyCode As Integer, Shift As Integer)
'appui de 'enter', donc lancement des calculs
If KeyCode = 13 Then Call Command1_Click
End Sub
==
ET le gain est au rendez-vous ! LE calcul de 3000! mets maintenant 6,6 secondes (au lieu de 18 avant)... Soit environ 3 fois plus vite...
JE pense qu'il reste 2 principes sur lequel ton algorithme pourrait être amélioré. LA structure des boucles, et les paramètres E4, E5 etc... qui me semble correspondent au nb de chiffre pris pour effectuer les calculs. On pourrait penser prendre jusqu'à 15 chiffres significatifs en passant en Double... enfin à voir...
A+
Us.
6 août 2005 à 09:37
Juste une petite correction 0! = 1 ( par convention ( c'est pour que la formule de calcul des combinaisons soit toujours juste et qu'on ne traite pas un cas particulier pour 0 ))
6 août 2005 à 02:35
Pense à repenser (!) tes déclarations de variables et tu verras que tu gagneras encore en vitesse : les types non précisés sont de type Variant et ont la réputation d'être lents.
Dès que tu remets la main sur la démonstration/explication de l'algo, tu mets à jour, hein
6 août 2005 à 00:47
Ah ! malgré l'heure tardive, je n'ai pas pu résister ! J'ai essayé ton code et je l'ai comparé avec le mien... ET verdict ! Pour 3000!, mon algo met 3,4 secondes.... hélas le tiens (en supprimant les affichages inutiles et les DoEvents) met 18,46 secondes (et avant écriture bien sur)... soit environ 5 fois moins rapide !
Donc : N'Oubliez pas TOUT ce que vous avez vu sur ce site en matière de calcul de factorielle, voici UN programme dans ce domaine. (c'est un poil plus modeste... LOL...)
Néanmoins, loin de moi de critiquer sévèrement ton programme, car je le trouve trés intéressant, dans le sens où il repose sur un principe de calcul que je n'ai pas vraiment compris... une explication mathématique de l'idée serait bienvenue, comme le souligne Jack. De plus, la rapidité n'est pas si mauvaise que ça... je pense, qu'en comprenant mieux le principe, on peut largement l'améliorer... (je pense que E4, E5 etc... sert à faire le calcul avec un certain nb de chiffres, on peut surement prendre plus (avec ce qui va avec) )...
La véracité du calcul ne pose pas de problème.
Pour en revenir aux remarques sur le codage, je pense qu'il reste des remarques exprimées par Jack encore valides... Bon, je dirais que :
- Les déclarations DIM dans :
"Dim N, R(100000), M, MAX, K, RET, S, B, A, C2, C1, E4, E5, B2, L, L1, C, bouc1, bouc2, bouc3, bouc4, CX, CY As Double"
n'est pas optimal. En effet, comme tu le déclares, seul le dernier CY est en Double. IL faut en fait à chaque fois déclarer le type à chaque variable.
Donc écrire :
Dim N as Double, R(100000) as Double, M as Double ...etc...
Là, c'est pour expliquer comment on déclare, mais il faut aussi voir quel type est le mieux pour le calcul à réaliser. Pour des entiers le type Long (par exemple) est le plus rapide...
- Le calcul CAL1 n'a pas d'intérêt d'être dans une SUB, puisqu'il n'y a qu'un seul appel...
- Dans CAL1, le calcul de la variable A pourrait être directement inclus dans le calcul suivant. C'est toujours une varaible en moins... (C'est une optimisation un peu plus poussée, je force un peu...)
- La variable boucl ne sert à rien.
- Les variables bouc2, bouc3, bouc4 etc... ne servent à aucun calcul.
- La syntaxe de l'étiquette DebutWhile: dans une boucle Do while...loop est étrange...
- La ligne : "If MAX > 10000 Then End" est aussi étrange, car elle signifie qu'on pourrait arrêter le calcul sans en connaitre le résultat... A moins qu'elle soit inutile ?...
Enfin, bref, la connaissance du principe mathématique, pourrait amener d'autres remarques... J'espère que toutes ces remarques seront t'encourager à mieux reprendre le codage, car c'est tout même un bon algorithme, qui pourrait devenir effectivement le meilleur que je connaisse... enfin... peut-être... le chalenge est lancé !
(Et je me réserve pour la suite pour le noter...)
Amicalement,
Us.
5 août 2005 à 19:19
En plus, c'est une de mes premières sources, j'ai fait bcp de progrès en VB depuis.
Donc bientôt une mise à jour: une programmation propre, commentée, plus courte et bien sur plus performante.
Et les calculs sont justes, je confirme.
5 août 2005 à 17:05
- pas d'indentation du code (illisible)
- pas de commentaire (faire des maths sans fil conducteur, pas pratique)
- mauvais dimensionnement des variables (quand on fait des maths, c'est un minimum)
Un "Dim" ne suffit pas : "Dim maVar1 As Double, maVar2 As Long ..."
- Pourquoi avoir dimensionné tes variables en Public (pas Global) dans un module ?
Comme elles ne concernent que ta forme, tu aurais pu les déclarer en private dans la partie "Déclaration" de ta forme.
- Utilisation de Labels numériques et de Goto (bof, c'est d'un autre temps)
Vaudrait mieux utiliser des Do-While-Loop ou des For-Next
- L'instruction Stop : pas terrible : ne libère pas la mémoire --> "End" ou "Exit Sub"
T'as recopié ça depuis une calculette Texas ?
N'empèche que faire ce genre de calcul sans limitation est très fort.
D'où proviennent ces équations ?