IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

déclaration tableau de rationnels


Sujet :

C++

  1. #21
    Membre émérite
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Par défaut
    Citation Envoyé par Aleph69 Voir le message
    4. enfin, comme dit précédemment, la stabilité des calculs avec des rationnels reste à démontrer.
    Les opérations + et * sont stables dans l'ensemble des rationnels. Au pire, on risque des dépassement d'entiers. Soit on contrôle ces débordements (a + b => MAX - b < a?), soit on prend des grands entiers et les grands rationnels qui vont avec (voir GMP).

    Dès lors, tu peux faire du calcul exact tant que tu n'as pas de racine carrée, de cosinus ou autre joyeuseté à calculer. Dans bien des cas, tu peux t'y ramener (tu travailles sur le carré des distances; tu ne compares pas tes distances à epsilon = 1.0e-5, tu multiplies tes données par 1.0e5 et tu compares le carré de la norme à 1, etc.)

    Citation Envoyé par Aleph69 Voir le message
    3. la stabilité des opérations flottantes est un phénomène complexe, en particulier les erreurs d'arrondis ne se cumulent pas contrairement à une idée reçue, et on sait très bien la contrôler (théorie des erreurs prograde et rétrograde);
    A ma connaissance, on arrive tout au mieux à estimer la précision à coup d'arrondi supérieur et d'arrondi inférieur dans les calculs pour savoir si la précision de calcul est suffisante.

    A moindre coût, on a les méthodes de compensation type somme de Kahan et autres dérivées, mais rien de très palpable qui fasse état d'une grande maîtrise des phénomènes...

    Pour ce qui est des performances, localement, les rationnels sont plus coûteux. Globalement, je serais curieux de voir ce que ça donne face à des arbres de construction en arithmétique flottante.

    Sans dire que ça soit le Graal, quand on a besoin de faire des calculs robustes sans faire de l'analyse numérique à la moindre formule et qu'on a une notion de précision sur les données qu'on manipuler, se reposer sur des rationnels ne me semble pas si farfelus.

  2. #22
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    Bonjour à tous,

    Les rationnels sont un sous-ensemble mathématiques qui n'ont, en général, aucun intérêt à être utilisés. Sauf, bien sûr, quand on fait du calcul exact.

    Pour les calculs rapides, on a les floats et les doubles.
    C'est la raison pour laquelle je pense que l'implémentation des rationnels devrait être pensée pour l'exactitude.

  3. #23
    Membre confirmé
    Homme Profil pro
    Apprenti
    Inscrit en
    Décembre 2010
    Messages
    86
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Apprenti

    Informations forums :
    Inscription : Décembre 2010
    Messages : 86
    Par défaut suite
    Bonjour,

    voilà un morceau de code et mes questions figurent après :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
     
    #include <iostream>
    #include <cstdlib>
     
    using namespace std;
     
    class Q{
    public:
            int num; // stocke le numérateur
            int den; // stocke le dénominateur
            Q(int a=0,int b=1); // le constructeur de la classe Q (le nombre 1 par défaut)
            Q operator+(Q a); // Définit l'opérateur +                                    // Le premier Q désigne le type de sortie
            void show(); // Affiche le nombre rationnel                                    // void est un type vide, il n'a pas de type
    };
     
    Q::Q(int a,int b){ // Le constructeur                                                // le constructeur est une méthode
            num=a;
            den=b;
    }
     
    Q Q::operator+(Q a){
            Q t; // crée un nouveau nombre rationnel                                      // Le Q le plus à gauche, désigne le type de sortie de la méthode, alors que le deuxième dans Q::operator permet d'accéder à la méthode de la classe Q
            t.num=num*a.den+den*a.num; // stock le numérateur des nombres additionnés
            t.den=den*a.den;  // stock le dénominateur des nombres additionnés.
            return t; // retourne le résultat de l'addition
    }
     
    void Q::show(){
         std::cout << num << " / " << den << " = " << (float)(num)/(float)(den) << "\n";
    }
     
    int main(void){                                                                            // le type d'élément de sortie de la fonction principale main est le type entier. preuve : return 0
    Q a(3,4),b(1,2); // définit deux nouveaux nombres rationnels a et b
    a=a+b; // additionne a et b est stocke le résultat sous a.
    a.show(); // affiche a
    return 0; 
    }

    1) Un ami m'a aidé à modifier ce code. Et m'expliquait qu'en linux(avec quoi je travaille) il faut impérativement mettre "int main" et pas seulement "main"car avec le seul main, nous avions un message d'erreur (avec les autres modifications qui s'imposent). Il m'expliquait qu'il y a différentes versions de c++. Alors que dans certains livres d'une bibliothèque , j'ai qu'il y a des programmes de C++, dans lesquels, il n'y a pas forcément le int....

    Pourquoi ?

    2) Dans la partie du code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    Q Q::operator+(Q a){
            Q t; // crée un nouveau nombre rationnel                                      // Le Q le plus à gauche, désigne le type de sortie de la méthode, alors que le deuxième dans Q::operator permet d'accéder à la méthode de la classe Q
            t.num=num*a.den+den*a.num; // stock le numérateur des nombres additionnés
            t.den=den*a.den;  // stock le dénominateur des nombres additionnés.
            return t; // retourne le résultat de l'addition
    }
    je ne comprends pas comment le programme fait pour savoir que le "t" qui est une variable déclarée à l'intérieur de la méthode, est le deuxième élément avec lequel on va additionner le "a" qui lui est une variable d'entrée si j'ai bien compris.

    Comment le programme sait-il que le "t" est une variable d'entrée ?

    3) Qu'est-ce-que c'est : cstdlib ?


    En espérant avoir été clair.


    merci, cordialement

  4. #24
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    Citation Envoyé par matlab_ Voir le message
    1) Un ami m'a aidé à modifier ce code. Et m'expliquait qu'en linux(avec quoi je travaille) il faut impérativement mettre "int main" et pas seulement "main"car avec le seul main, nous avions un message d'erreur (avec les autres modifications qui s'imposent). Il m'expliquait qu'il y a différentes versions de c++. Alors que dans certains livres d'une bibliothèque , j'ai qu'il y a des programmes de C++, dans lesquels, il n'y a pas forcément le int....

    Pourquoi ?
    Dans l'ancien temps, le C indiquait que toute fonction déclarée sans type de retour utiliserait int par principe. En ce temps-là, pour des raisons stylistiques, on n'écrivait pas le int du main, pour aider à le distinguer.

    Cependant, dans le code implicite, il est présent.
    De nos jours, ce n'est plus accepté, et normativement parlant, c'est interdit.


    Citation Envoyé par matlab_ Voir le message
    2) Dans la partie du code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    Q Q::operator+(Q a){
            Q t; // crée un nouveau nombre rationnel                                      // Le Q le plus à gauche, désigne le type de sortie de la méthode, alors que le deuxième dans Q::operator permet d'accéder à la méthode de la classe Q
            t.num=num*a.den+den*a.num; // stock le numérateur des nombres additionnés
            t.den=den*a.den;  // stock le dénominateur des nombres additionnés.
            return t; // retourne le résultat de l'addition
    }
    je ne comprends pas comment le programme fait pour savoir que le "t" qui est une variable déclarée à l'intérieur de la méthode, est le deuxième élément avec lequel on va additionner le "a" qui lui est une variable d'entrée si j'ai bien compris.

    Comment le programme sait-il que le "t" est une variable d'entrée ?
    Comme tu l'as indiqué, ce code est la définition de Q Q::operator+(Q a). En réalité, cette fonction est déclarée dans la classe Q, et donc est une méthode de cette classe.
    Chaque méthode d'une classe possède un "argument discret" nommé this, qui est une référence à l'objet sur laquelle il est appelé.

    Ici, si alpha et beta sont deux Q, Q somme = alpha+beta; est une liberté syntaxique traduite à la compilation par Q somme = alpha.operator+(beta);. c'est à dire l'exécution de Q::operator+, ce qui donnerait un code équivalent au suivant (sauf que somme serait initialisé dans cet équivalent)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Q somme;
    {
    //ces deux lignes représentent les arguments
            Q& this=alpha;//argument implicte de toute méthode d'un objet
            Q a=beta;//argument de la fonction, tel que déclaré
    //code de la fonction
            Q t;//variable locale t
            t.num=num*a.den+den*a.num;
            t.den=den*a.den;
            somme = t;//code effectif de "return t;"
    }
    Par ailleurs,
    t.den=den*a.den; s'explicite en t.den=this.den*a.den;.

    La fonction serait mieux codée avec
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    Q& Q::operator+=(const Q& a){
            num=num*a.den+den*a.num;
            den*=a.den;
            return *this;
    }
    Q operator+(const Q& a, const Q& b){
            return Q(a.num*b.den+a.den*b.num, a.den*b.den);
    }
    ou encore
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Q& Q::operator+=(const Q& a){
            num=num*a.den+den*a.num;
            den*=a.den;
            return *this;
    }
    Q operator+(const Q& a, const Q& b){
            Q res(a);
            return res+=b;
    }
    Citation Envoyé par matlab_ Voir le message
    3) Qu'est-ce-que c'est : cstdlib ?
    Simplement la version C++isée de stdlib.h, un entête standard hérité du C. Il contient la définition de exit(), entre autre.
    C'est un fichier que tu peux tout à fait lire (mais ne le modifie pas, surtout...), mais son contenu risque d'être rébarbatif.
    Tu trouvera un résumé sur cppreference, qui est un très bon compagnon.

  5. #25
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Par défaut
    Citation Envoyé par bretus Voir le message
    Les opérations + et * sont stables dans l'ensemble des rationnels. Au pire, on risque des dépassement d'entiers.
    Oui, c'est bien des dépassements d'entiers dont je parle.

    Citation Envoyé par bretus Voir le message
    Soit on contrôle ces débordements (a + b => MAX - b < a?), soit on prend des grands entiers et les grands rationnels qui vont avec (voir GMP).
    Je ne vais pas répéter à chaque fois ma question initiale, mais il faut a priori que tu raisonnes avec des nombres premiers. A moins que tu saches me dire quels sont les rapports de deux nombres premiers représentables par un flottant. Moi je n'en sais absolument rien!

    Citation Envoyé par bretus Voir le message
    Dès lors, tu peux faire du calcul exact tant que tu n'as pas de racine carrée, de cosinus ou autre joyeuseté à calculer. Dans bien des cas, tu peux t'y ramener (tu travailles sur le carré des distances; tu ne compares pas tes distances à epsilon = 1.0e-5, tu multiplies tes données par 1.0e5 et tu compares le carré de la norme à 1, etc.)
    Oui, d'accord. La question est plutôt de savoir si et quand le jeu en vaut la chandelle dans le cadre d'un calcul numérique. Quel avantage a un rationnel, pour lequel tu as possiblement besoin d'étendre les entiers, sur un flottant, même étendu? Sans même parler des problèmes d'overflow, la précision est exacte, certes, mais à quoi sert-elle? Quelle méthode numérique a besoin d'une telle précision?

    Citation Envoyé par bretus Voir le message
    A ma connaissance, on arrive tout au mieux à estimer la précision à coup d'arrondi supérieur et d'arrondi inférieur dans les calculs pour savoir si la précision de calcul est suffisante.

    A moindre coût, on a les méthodes de compensation type somme de Kahan et autres dérivées, mais rien de très palpable qui fasse état d'une grande maîtrise des phénomènes...
    Je ne comprends pas ton interprétation. L'analyse de la méthode de Kahan,
    http://en.wikipedia.org/wiki/Kahan_summation_algorithm,
    comme l'analyse des algorithmes standards (horner, gauss, ...), permet d'obtenir une majoration de l'erreur relative par le produit d'un terme ne dépendant que des données, le conditionnement, et d'un terme dépendant de l'algorithme, l'erreur rétrograde. Dès lors, il est très facile de contrôler l'erreur relative à l'aide de méthodes de préconditionnement, d'autant que les majorations obtenues sont toujours pessimistes. Bref, je ne vois pas bien ce que tu cherches à dire à ce sujet.

    Citation Envoyé par bretus Voir le message
    Pour ce qui est des performances, localement, les rationnels sont plus coûteux. Globalement, je serais curieux de voir ce que ça donne face à des arbres de construction en arithmétique flottante.
    Un contre-exemple m'intéresserait aussi si tu en as sous la main.

    Citation Envoyé par bretus Voir le message
    Sans dire que ça soit le Graal, quand on a besoin de faire des calculs robustes sans faire de l'analyse numérique à la moindre formule et qu'on a une notion de précision sur les données qu'on manipuler, se reposer sur des rationnels ne me semble pas si farfelus.
    L'idée d'utiliser en soi des rationnels n'est pas farfelue. Je m'interrogeais seulement sur l'algorithme de conversion d'un flottant en rationnel et par suite sur la manière de les manipuler sans faire de dépassement. Pour un entier ou flottant, le phénomène de dépassement dans un sens où dans l'autre est facile à comprendre car il varie de façon monotone : tu as un intervalle défini dans lequel il faut rester. Pour les rationnels, c'est beaucoup plus compliqué car cette monotonie est perdue : sur l'ensemble des rationnels, ceux qui ne sont pas représentables avec un type d'entier fixé ne forment pas un intervalle. Tu peux t'amuser à le vérifier avec des nombres premiers connus si tu veux :
    http://fr.wikipedia.org/wiki/Liste_de_nombres_premiers
    Cela me paraît plutôt légitime de s'interroger sur l'algorithmique liée à ces nombres.

  6. #26
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    Citation Envoyé par aleph69
    Pour un entier ou flottant, le phénomène de dépassement dans un sens où dans l'autre est facile à comprendre car il varie de façon monotone : tu as un intervalle défini dans lequel il faut rester.
    Non, les flottants ne sont pas continuement précis, il y a des débordements partout dans l'espace représentables (qui n'est pas un intervalle, du coup…).
    32769 = 2^15+1 n'est pas représentable par un float alors que 2080768 = 127*2^14 l'est très bien.

    il faut bien comprendre, qu'un float, c'est deux entiers: la mantisse et l'exposant. Il y a 2 * (nombre de valeurs de l'exposants) possibilitées de dépassements. C'est la raison même de l'erreur flottante.

  7. #27
    Membre confirmé
    Homme Profil pro
    Apprenti
    Inscrit en
    Décembre 2010
    Messages
    86
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Apprenti

    Informations forums :
    Inscription : Décembre 2010
    Messages : 86
    Par défaut suite
    Bonjour,

    y'a-t-il une libraire c++ ou un code c++, pour pouvoir obtenir la forme irréductible d'un rationnel ?

    (l'algorithme qui va avec serait instructif pour moi)

    Cordialemnt

  8. #28
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    Surement, cherche donc, ou écris la, c'est tout bête.

    Suppose p et q deux entiers.
    p/q est réductible s'il existe un entier d>1 tel que p=d*p' et q=d*q'. auquel cas, p/q = p'/q'.
    Cet entier d est appelé diviseur commun de p et q.
    Réduire p/q revient donc simplement à chercher le plus grand diviseur commun de p et q (leur PGCD)

    Pour ce faire, il existe la méthode d'Euclide.
    Tu trouveras de plus ample renseignement sur wikipedia

  9. #29
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Par défaut
    Citation Envoyé par leternel Voir le message
    Non, les flottants ne sont pas continuement précis, il y a des débordements partout dans l'espace représentables (qui n'est pas un intervalle, du coup…).
    32769 = 2^15+1 n'est pas représentable par un float alors que 2080768 = 127*2^14 l'est très bien.

    il faut bien comprendre, qu'un float, c'est deux entiers: la mantisse et l'exposant. Il y a 2 * (nombre de valeurs de l'exposants) possibilitées de dépassements. C'est la raison même de l'erreur flottante.
    Merci, je suis au courant.
    Je crois qu'on ne parle pas de la même chose et à mon avis c'est parce les deux problèmes sont justement liés dans le cas des rationnels.

    Je disais simplement qu'un type de flottant étant fixé, tu as bien un plus petit flottant et un plus grand flottant qui définissent un intervalle. Qu'il n'y ait pas que des flottants dans cet intervalle n'intervient pas dans ma remarque car on n'a jamais prétendu que les flottants sont les réels. On fait bien des calculs en précision finie.

    Pour faire du calcul exact avec des rationnels, il faut justement que tu puisses représenter TOUS les rationnels supérieurs à un certain nombre et inférieurs à un autre nombre, ces deux nombres étant fixés par un typage. Or, je me demande dans quelle mesure il est possible de le faire en gardant à l'esprit l'existence de rapports de nombres premiers. C'est pour cela que je dis qu'il me semble y avoir des "trous" ou, si tu préfères, que le calcul exact avec des rationnels n'est finalement peut-être pas possible.

  10. #30
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    si, les langages de calculs formels en sont la preuve.

    Par contre, ce que je disais, c'est que la précision des nombres flottants n'est pas absolument constante. En effet, elle est proportionnelle au nombre représenté.
    Ce qui est le contraire des entiers ou des relatifs (précisions de 1 et 1/int_max, respectivement).

  11. #31
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : Mars 2010
    Messages : 1 218
    Par défaut
    Citation Envoyé par leternel Voir le message
    si, les langages de calculs formels en sont la preuve.
    Le calcul formel est un tout autre problème. Depuis le début, on parle bien de calcul numérique avec une classe de rationnels dont le typage est subordonné à ceux de deux entiers.

    Citation Envoyé par leternel Voir le message
    Par contre, ce que je disais, c'est que la précision des nombres flottants n'est pas absolument constante. En effet, elle est proportionnelle au nombre représenté.
    Encore fois, ça ne pose aucun problème car cette précision est majorée en valeur absolue (permettant l'analyse de stabilité à la Kahan) et signée en valeur relative (pas d'accumulation en moyenne, distribution brownienne des erreurs).

Discussions similaires

  1. [Toutes versions] Déclaration Tableau public
    Par CyberMen dans le forum VBA Access
    Réponses: 2
    Dernier message: 02/04/2009, 21h24
  2. Déclaration Tableau 2 dimensions
    Par vincent.gad dans le forum Débuter
    Réponses: 5
    Dernier message: 21/11/2008, 18h02
  3. [Tableaux] Déclaration tableau multidimension
    Par P4board dans le forum Langage
    Réponses: 2
    Dernier message: 22/10/2007, 21h18
  4. déclaration tableau javascript
    Par kohsaka dans le forum Général JavaScript
    Réponses: 2
    Dernier message: 14/06/2007, 16h44
  5. Réponses: 1
    Dernier message: 09/03/2006, 17h25

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo