CALCUL DE LA FACTORIELLE D'UN NOMBRE AVEC TOUS SES CHIFFRES (AUCUNE LIMITE !)

Commentaire de jack le 05/08/2005 17:05:23 administrateur CS

Je n'ai pas vérifié la véracité des calculs, mais ce projet manque de clarté :
- 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 ?

Commentaire de us_30 le 06/08/2005 00:47:54

Bonsoir,

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.

Commentaire de Julien39 le 06/08/2005 09:37:27 administrateur CS

C'est pas mal j'ai mis 10/10 pour réparer l'injustice du 1/10.

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 ))

Commentaire de violent_ken le 06/08/2005 09:58:18

Merci à Julien39 pour sa note, çà remonte le moral...
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 !

Commentaire de us_30 le 07/08/2005 10:05:22

A oui ! Je commence à y voir vraiment plus clair. Si on tient compte de la valeur Max, la variable K devient inutile, car elle ne fait que incrémenter la base R(). Donc il suffit de la mettre dans une boucle FOR. La deuxième boucle, For t = MAX To 1 Step -1 ... sert à combler les nombres de la base R() inférieur à 9 en nb de chiffre... Au lieu d'utiliser la fonction LEN, tu utilise le calcul du nb de chiffre mathématiquement par le LOG en base 10; avec Int(Log(S + 0.5) / Log(10)).

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.

Commentaire de orelec le 15/10/2006 01:20:00

Aucune limite ? La suite prouve le contraire :
À 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

Commentaire de violent_ken le 15/10/2006 19:03:48

Salut, alors tout d'abord : ce code est très vieux à l'échelle de mes connaissances. Autrement dit, c'est ma première source sur ce site, donc je débutais.

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, @+

Commentaire de BruNews le 15/10/2006 19:32:22 administrateur CS

L'espace mémoire accordé au processus en mode normal (hors switch 3 Go sur system serveur) est de 2 Go system 32 bits, les 2 autres Go sont réservés à la zone kernel.
String dynamique ou non n'y changera rien.

Commentaire de orelec le 15/10/2006 23:33:11

Je m'excuse de vous avoir réveillé mais si je connais si bien le sujet c'est parce que je n'ai pas les moyens de me payer Maple ou un équivalent. J'ai donc dû développer ma propre application de calcul scientifique (j'en suis encore au noyau de base) mais en Java (même raisons que Maple) qui est également orienté web.
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.