Trouvé le numérateur et dénominateur le plus proche d'un rée

[Dlzlogic]

Bonjour,

Peux-tu nous expliquer d'avantage en quoi consistait le logiciel ? Que faisais-tu des nombres et que cherchais-tu à calculer ? (si bien sûr ces informations ne sont pas confidentielles :p).
J'ai un peu de mal à voir à quoi cela te sert de faire un changement de variable pour obtenir des valeurs plus petites.

C'est pas du tout confidentiel, mais ça risque d'être long, parce que c'est mon sujet préféré.
Donc, je suis géomètre, et la base de travail chez nous ce sont des plans. Depuis une trentaine d'années, on s'est informatisés, nous aussi et pour ce qui concerne le dessin, on a été parmi les premiers.
Les systèmes de coordonnées utilisés ont beaucoup de chiffres avant la virgule, puisque les origines sont mises suffisamment loin, on n'aime pas du tout les signes négatifs.
Par contre, comme la précision est notre règle d'or, on calcule généralement avec la précision du millimètre. Ca c'est pour expliquer le changement de variable par la translation.

En topométrie, les angles sont rarement des angles droits, donc tous les calculs utilisent la trigonométrie, et comme chacun sait, un nombre réel, comme une valeur trigonométrique, n'est jamais exacte.
Une conséquence de cela, on ne doit jamais comparer des valeurs réelles avec le signe égal.

Donc, pour la machine, au moment du calcul, si l'"unité de base" est le millimètre, toutes les valeurs ont été multipliées par 1000. Mais l'utilisateur ne s'en rend jamais compte.
A ta disposition pour tous les détails que tu veux.

[ampholyte]

Donc, pour la machine, au moment du calcul, si l'"unité de base" est le millimètre, toutes les valeurs ont été multipliées par 1000. Mais l'utilisateur ne s'en rend jamais compte.
A ta disposition pour tous les détails que tu veux.

Du coup, sachant que la machine va te renvoyer un entier pour ton calcul il ne te restera plus qu'à diviser par 1000 pour obtenir ton résultat à la précision demandée. Mais est-ce que le calcul est vraiment plus rapide ?

[Dlzlogic]

Du coup, sachant que la machine va te renvoyer un entier pour ton calcul il ne te restera plus qu'à diviser par 1000 pour obtenir ton résultat à la précision demandée. Mais est-ce que le calcul est vraiment plus rapide ?

Non, le souci n'est pas la rapidité, mais l'occupation mémoire.
Toutes les opérations mathématiques sont faites en double précision (15 chiffres significatifs).
On a une base de données. La première opération consiste à stocker les données en mémoire, à partir d'un fichier. Sur ce fichier, c'est un fichier texte, les données sont notées en mètres avec la précision du mm (par exemple) c'est à dire 3 chiffres après la virgule.
Au lieu de stocker la valeur telle qu'elle est lue, elle est stockée en nombre de mm après translation.
Tous les calculs sont faits avec ces valeurs et au moment d'écrire les résultats, l'opération inverse est faite.

Concernant des calculs longs, qu'ils soient faits en int ou en float, je ne pense pas que ça change grand-chose.

[ampholyte]

Non, le souci n'est pas la rapidité, mais l'occupation mémoire.
Toutes les opérations mathématiques sont faites en double précision (15 chiffres significatifs).
On a une base de données. La première opération consiste à stocker les données en mémoire, à partir d'un fichier. Sur ce fichier, c'est un fichier texte, les données sont notées en mètres avec la précision du mm (par exemple) c'est à dire 3 chiffres après la virgule.
Au lieu de stocker la valeur telle qu'elle est lue, elle est stockée en nombre de mm après translation.
Tous les calculs sont faits avec ces valeurs et au moment d'écrire les résultats, l'opération inverse est faite.

Concernant des calculs longs, qu'ils soient faits en int ou en float, je ne pense pas que ça change grand-chose.

Très bien merci pour ta réponse, je comprends mieux la conversion du coup.

Le problème qui se pose ici c'est plutôt les conditions nécessaires pour permettre d'optimiser un maximum les calculs.
Dans un premier temps pour répondre au problème de Polack77, j'ai exécuté ce code

Code: Tout sélectionner

#include
#include
#include

#define NUMERATEUR_MAX 99999999
#define DENOMINATEUR_MAX 999999

int main()
{
    double valeur = 0;
    double ecart = 0;

    double erreur = 100;
    double erreur_tmp = 0;
    double tmp = 0;
    int n_max = 0;
    int d_max = 0;
    int n = 0;
    int d = 0;


    printf("valeur : ");
    scanf("%lf", &valeur);
    printf("ecart : ");
    scanf("%lf", &ecart);


    for(n = 0; n < NUMERATEUR_MAX; n++){ // On parcourt l'ensemble des numérateurs
        for(d = 1; d < DENOMINATEUR_MAX; d++){ // On parcourt l'ensemble des dénumérateurs
            tmp = n*1.0/d; // On enregistre la valeur réelle de la fraction
            erreur_tmp = fabs(tmp-valeur); // On calcule l'erreur temporaire
            if(erreur_tmp < erreur){
                n_max = n; // On stocke le nouveau numérateur
                d_max = d; // On stocke le nouveau dénominateur
                erreur = erreur_tmp; // On stocke notre nouvelle erreur
            }
            if(erreur < ecart) break; // Si l'erreur est inférieur à l'écart de l'utilisateur, on sort des for
        }
        if(erreur < ecart) break;
    }
    printf("%d\n",n_max); // On affiche les résultats
    printf("%d",d_max);

    return 0;
}


Le problème comme tu peux le constater c'est que très rapidement on tombe obtient un nombre de calcul faramineux (99 999 999 * 999 999). C'est pour cette raison qu'on a introduit l'écart. Malgré tout, la durée de calcul est vraiment énorme. De retour chez moi je testerais par GPU mais je ne pense pas obtenir des résultats beaucoup plus probant.

Sais-tu s'il existe une méthode de dichotomie permettant de trouver à partir d'un réel, la fraction la plus proche ? Ou aurais-tu une idée permettant de résoudre le problème soulevé par Polack77 ?

[Polack77]

Oui le temps d’exécution avec cette façon de faire est pharaonique. Le lien que tu m'avais fournis (oui je tutoie toujours sur fofo dzl si ça dérange) contient un code beaucoup plus malin je trouve (idée que j'exploite de mon coté).
Ensuite (pour la petite histoire) je négocie avec ma hiérarchie une évolution du format pour passer à un format variable.
Je m'explique :
Aujourd'hui j'ai 8 carac numérateur 6 dénominateur.
Je voudrais sacrifier un de ce caractère pour en faire un flag. Voila le petit schéma que j'ai fournis à ma hiérarchie (je pense que ça sera plus claire qu'une longue explication)

De mon coté (même si mon après-midi à dû être consacré en grande partie à un autre sujet) j'ai pondu ça :

Code: Tout sélectionner

#include

bool Cherchenumerateurdenominateur(const double valeur, const unsigned long numerateurMax, const unsigned long denominateurMax,const double ecartAcceptable,const char indicePressision,unsigned long* outNumerateur,unsigned long* outDenominateur,double* outEcart);

bool Cherchenumerateurdenominateur(const double valeur, const unsigned long numerateurMax, const unsigned long denominateurMax,const double ecartAcceptable,const char indicePressision,unsigned long* outNumerateur,unsigned long* outDenominateur,double* outEcart)
{
   double myEcartAcceptable;
   myEcartAcceptable = abs(ecartAcceptable);
   if (valeur != floor(valeur))
   {
      unsigned long numerateurCourant,denominateurCourant; //numérateur et dénominateur en cour de test
      long numerateurOkAvContraintes; //numerateur à tester sur la contrainte de numérateur
      double delta,delta1,delta2; //Les deltas dans les résultats
      char util;

      *outEcart = valeur;
      for (denominateurCourant = 1;denominateurCourant<=denominateurMax;denominateurCourant++)
      {
         numerateurCourant = (unsigned long)floor(valeur * denominateurCourant);
         delta1 = valeur - (double)numerateurCourant / (double)denominateurCourant;
         delta2 = (double)(numerateurCourant + 1) / (double)denominateurCourant;
         if (delta1 < delta2)
         {
            delta = delta1;
            util = 1;
         }
         else
         {
            delta = delta2;
            util = -1;
         }
         if (delta < *outEcart)
         {
            numerateurOkAvContraintes = numerateurCourant + (1 - util) / 2;
            if (numerateurOkAvContraintes <= numerateurMax && denominateurCourant <= denominateurMax)
            {
               *outNumerateur = numerateurOkAvContraintes;
               *outDenominateur = denominateurCourant;
               *outEcart = delta;
            }
         }
      }
   }
   else
   {
      *outNumerateur = valeur;
      *outDenominateur = 1;
      *outEcart = 0;
   }
   return (*outEcart <= ecartAcceptable);
}

Cette fonction n'est pas terminé mais est en bonne voie.
Tu noteras que le paramètre d'entrée "indicePressision" n'est pas encore utilisé (à vrais dire je ne sait pas encore comment ni même si je vais l'utilisé, même si j'en ai une vague idée : l'objectif serait de limiter le nombre de test sur le dénominateur grâce à une analyse de l'évolution de l’écart).
Ensuite l'écart acceptable ne vas pas rester non plus en l'état. Cette écart est aujourd'hui absolu (par exemple un écart de 0,001) alors que je vais le faire devenir relatif (précision au millième de ma valeur d'entrée par exemple).
Pas terminé (certaines choses sont aberrante dans ce code, comme le test "denominateurCourant <= denominateurMax" par exemple) mais en bonne voie (en prime cette fonction serait réutilisable et elle est relativement rapide)
Même si la problématique vitesse est très importantes car énormément de valeur vont être à traiter (environ 2 millions de valeurs max / jours)

Bon weekend et à lundi (je ne pense pas travailler la dessus ce weekend à vrais dire)

MERCI BEAUCOUP à tous (et a toutes ^^) de m'avoir aidé ça fait vraiment plaisir :lol5:

[Dlzlogic]

J'avoue que j'ai un peu de mal à voir l'intérêt de la chose.
Je reformule à ma façon
En entrée on a un nombre réel. En mémoire il est connu sous forme mantisse et caractéristique.
On veut l'utiliser sous forme de fraction de 2 entiers.
Ne serait-ce pas plus simple de transformer la mantisse en numérateur et la caractéristique en dénominateur avec la convention : puissance de 10.
La précision est respectée, puisque tous les chiffres significatifs peuvent être stockés.

Y'a aussi une chose qui m'échappe on peu.
D'après le tableau, le format stocké est sur 14 caractères, donc de l'alphanumérique.
Or au début de l'explication tu dis que tu reçois un réel.
Donc, j'ai toujours pas compris le problème.

[Polack77]

J'avoue que j'ai un peu de mal à voir l'intérêt de la chose.
Je reformule à ma façon
En entrée on a un nombre réel. En mémoire il est connu sous forme mantisse et caractéristique.
On veut l'utiliser sous forme de fraction de 2 entiers.
Ne serait-ce pas plus simple de transformer la mantisse en numérateur et la caractéristique en dénominateur avec la convention : puissance de 10.
La précision est respectée, puisque tous les chiffres significatifs peuvent être stockés.

Y'a aussi une chose qui m'échappe on peu.
D'après le tableau, le format stocké est sur 14 caractères, donc de l'alphanumérique.
Or au début de l'explication tu dis que tu reçois un réel.
Donc, j'ai toujours pas compris le problème.

Cette façon de faire et totalement sans intérêt je suis bien d’accord... Je le dit, le crie, le pleure même... Mais on ne veux pas m’entendre
Ensuite le transfert de données se fait via fichier texte (oui je sait c'est aberrant mais encore une fois on ne veux pas me léser touché à ça).
Les convention puissance de 10 ne me permette pas d'avoir une précision suffisante car admettons que je reçoive la valeur 0,333333333333333333. En puissance de 10 je vais renvoyer "00333333" et "100000" (sauf erreur je fait un peut vite). Avec cette méthode je vais retourné 1/3 ce qui BEAUCOUP plus précis.

[ampholyte]

edit : réponse ci dessus

[fatal_error]

slt,

pourquoi pas tout simplement

Code: Tout sélectionner

#include
#include
#include
#include
#define MAX_DENOM 999999
#define MAX_NUM 99999999
inline size_t findNumerator(const size_t &denom, const float &goal){
  float fnum = goal*denom;
  size_t numerator = floor(fnum);
  if(fnum - numerator > 0.5){
    numerator++;
  }
  return numerator;
}

int main(int argc, char** argv)
{
  float goal=153565441.11576;
  int denom=1;
  size_t bestNum=findNumerator(denom, goal);
  size_t bestDenom=denom;
  float bestValue=(float)bestNum/denom;
  float bestError=fabs(bestValue-goal);
 
  for(size_t denom=1; denomMAX_NUM) break;
    float value=(float)num/denom;
    if(fabs(value-goal)<bestError){
      bestError = fabs(value-goal);
      bestNum=num;
      bestDenom=denom;
      bestValue=(float)num/denom;
    }
  }
  std::cout<<"best found ="<<bestNum<<"/"<<bestDenom<<"="<<bestValue<<std::endl;
}



même idée qu'ampholyte, sauf qu'au lieu du n2, on a du n, vu qu'on sait trouver c'est quoi le meilleur numérateur pour un dénominateur donné
edit: on peut aussi remarquer que pour un certain dénominateur trop grand, si le numérateur dépasse la valeur maximale imposée, alors augmenter le dénominateur imposera d'augmenter le numérateur donc on peut directement s'arrêter

[ampholyte]

slt,

même idée qu'ampholyte, sauf qu'au lieu du n2, on a du n, vu qu'on sait trouver c'est quoi le meilleur numérateur pour un dénominateur donné
edit: on peut aussi remarquer que pour un certain dénominateur trop grand, si le numérateur dépasse la valeur maximale imposée, alors augmenter le dénominateur imposera d'augmenter le numérateur donc on peut directement s'arrêter

Je n'ai pas eu le temps de tester ton code, mais ce que tu as fait me paraît plus intéressant. Est-ce que j'envoie d'une réponse est toujours longue ? Ou la réponse est quasi immédiat ?

[fatal_error]

0.07s dans des cas un peu pourris

Code: Tout sélectionner

best found :(goal=5.89745) 4792007/812556=5.89745
time elapsed : 0.074599
best found :(goal=5.63364) 4224737/749912=5.63364
time elapsed : 0.071881
best found :(goal=7.70331) 6704876/870389=7.70331
time elapsed : 0.071105
best found :(goal=2.31341) 2257743/975937=2.31341
time elapsed : 0.071137

best found :(goal=9.91085e+06) 19821693/2=9.91085e+06
time elapsed : 7e-06
best found :(goal=4.34415e+06) 73850476/17=4.34415e+06
time elapsed : 8e-06
best found :(goal=8.99012e+06) 26970355/3=8.99012e+06
time elapsed : 7e-06
best found :(goal=3.09183e+06) 92754977/30=3.09183e+06
time elapsed : 9e-06
best found :(goal=2.42173e+06) 89603913/37=2.42173e+06
time elapsed : 9e-06

[ampholyte]

0.07s dans des cas un peu pourris

Code: Tout sélectionner

best found :(goal=5.89745) 4792007/812556=5.89745
time elapsed : 0.074599
best found :(goal=5.63364) 4224737/749912=5.63364
time elapsed : 0.071881
best found :(goal=7.70331) 6704876/870389=7.70331
time elapsed : 0.071105
best found :(goal=2.31341) 2257743/975937=2.31341
time elapsed : 0.071137

best found :(goal=9.91085e+06) 19821693/2=9.91085e+06
time elapsed : 7e-06
best found :(goal=4.34415e+06) 73850476/17=4.34415e+06
time elapsed : 8e-06
best found :(goal=8.99012e+06) 26970355/3=8.99012e+06
time elapsed : 7e-06
best found :(goal=3.09183e+06) 92754977/30=3.09183e+06
time elapsed : 9e-06
best found :(goal=2.42173e+06) 89603913/37=2.42173e+06
time elapsed : 9e-06

Vraiment sympa, merci pour ton partage

[Polack77]

Oui pas mal,

Le principe de ton code est le même que le mien en faite ^^
Et oui, les temps de réponses sont vraiment bon :++: même si c'est encore "optimisable". Par exemple dans certains cas (tout tes tests tests en faite) et à un moment donnée l’écart tombe à 0 (bestError dans ton code, *outEcart dans le mien). On peut alors stopper les boucles.

Merci de ton intérêt en tout cas :happy2: