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

[Polack77]

Bonjour,

Je suis développeur et je cherche a faire un truc pas si simple :hum: .

En résumer, je reçois une valeur réel et je doit sortir deux entiers (un numérateur et un dénominateur) permettant d'obtenir une valeur la plus proche possible du réel de départ.

Mes contraintes :
- la valeur d'entrée ne peut être plus grande que 99 999 999
- la valeur d'entrée ne peut être plus petite que 1 / 999 999
- numérateur et dénominateur de sortie doivent être entiers
- numérateur de sortie sur 8 chiffres max
- dénominateur de sortie sur 6 chiffres max

Pour le moment je travail uniquement sur des multiple de 10 niveau dénominateur :--:. Il est forcément possible de faire mieux que ça.

Je pense que je doit faire ça par encadrement, mais je n'ai aucune idée de comment m'y prendre :mur: . Ce qui explique ma présence sur ce forum :lol3:

Un petit coup de pouce serait le bienvenu.
Merci d'avance

PS :
J'ai volontairement posté dans le forum "Défis" mais je ne suis pas certain que ça soit le bon-emplacement (je suis tout nouveau sur ce fofo). Je n'en voudrais à personne si mon message est déplacé.

[ampholyte]

Bonjour,

Est-ce que la fraction peut être une fraction continue ?
Si oui je te conseille de regarder l'article sur wikipedia qui pourra sûrement te débloquer ;)

Bon courage

[Dlzlogic]

Bonjour,
Je crois que l'exemple typique est l'évaluation de pi, on obtient successivement
3 ; 22/7 ; 317 ... quelque-chose, je sais plus.

[ampholyte]

Bonjour,
Je crois que l'exemple typique est l'évaluation de pi, on obtient successivement
3 ; 22/7 ; 317 ... quelque-chose, je sais plus.

Il y a l'évaluation de la fonction aussi qui donne une solution vraiment sympathique :ptdr: .

[Polack77]

ampholyte (1er message) :
Non le résultat final ne peut pas être une fraction continue. Mais il est imaginable que ça soit une étape dans le calcul.

Dlzlogic :
Je doit avouer que j'ai pas compris grand chose sur la méthode d'évaluation de Pi :stupid:

ampholyte (2eme message) :
L'évaluation des racines carrés éveille un quelque chose en moi.
Ça devrais donner un truc du genre de :
Cherche la racine carrée de RacineCherche :

Code: Tout sélectionner

Si RacineCherche > 1 (si non mon algo ne fonctionneras pas ^^)
    Inf = 1
    Sup = 1
    Temps que Sup * Sup  RacineCherche alors
            Sup = Sup - (Sup - Inf) / 2
        Sinon
            OK = Inf
            Inf = Sup
            Sup = Sup + (Sup - OK) / 2
            OK = 0
        Fin si
    Fin temps que
Le résultat se trouve dans OK


Heeeee par contre je ne voie pas comment adapté ce genre de truc pour une fraction ni même comment faire en sorte de répondre a mes contraintes :help:

[Dlzlogic]

Pour le cas de pi, le garnd jeu était de remplacer pi par une fraction. 22/7 est la plus simple, l'autre, je ne m'en souviens plus, mais ce n'est qu'un détail sans importance.

[Polack77]

:doute: Heeeee ok, mais alors comment faire pour passé de 3 à 22/7 puis à 333/106 ext ???

[ampholyte]

:doute: Heeeee ok, mais alors comment faire pour passé de 3 à 22/7 puis à 333/106 ext ???

J'ai trouvé un petit site avec un algorithme permettant d'obtenir ces valeurs (à confirmer et tester évidemment). En l'adaptant tu pourras sûrement résoudre ton problème .

http://www.apmep-aix-mrs.org/bulletin/num08/bonnet.htm

Autre solution pourrait être la suivante :

Code: Tout sélectionner

erreur = 100
n_max = 0
d_max = 0
Pour tout n jusqu'à 999 999 999:
      Pour tout d jusqu'à 999 999:
            a = n/d;
            erreur_tmp = abs(a-monReel)
            si erreur_tmp < erreur alors
               n_max = n
               d_max = d
               erreur = erreur_tmp
      fin
fin
Afficher n_max
Afficher d_max


Quelques choses dans ce gout là. Par contre le calcul risque d'être assez long. Peut-être passer par le GPU serait une bonne idée.

[Polack77]

:zen: YES merci pour ce lien :++:
J'ai mit pas mal de temps à tout comprendre (et j'ai été déranger). J'ai pris le aussi temps de faire quelques tests.
Résultat : Le temps d’exécution n'est pas acceptable en l'état.
Mais je tiens le bon bout là.
(ce n'est pas le langage final mais voila un version VB de "ton" code, donc plus simple à comprendre)

Code: Tout sélectionner

    Dim ecart As Double
    Dim util As Long
   
    Dim nominateurCourant As Long
    Dim denominateurCourant As Long
   
    Dim denominateurOk As Long
    Dim nominateurOk As Double
    Dim nominateurOkAvContraintes As Double
    Dim varRech As Double
   
    Dim delta As Double
    Dim delta1 As Double
    Dim delta2 As Double
    Dim Pressision As Long
    Dim nominateurMax As Long
    Dim denominateurMax As Long
    nominateurMax = 99999999
    denominateurMax = 999999
    Pressision = 99999999
   
    varRech = 0.123456789
    ecart = 1
    For denominateurCourant = 1 To Pressision
        nominateurCourant = Int(varRech * denominateurCourant)
        delta1 = varRech - nominateurCourant / denominateurCourant
        delta2 = (nominateurCourant + 1) / denominateurCourant - varRech
        If delta1 < delta2 Then
            delta = delta1
            util = 1
        Else
            delta = delta2
            util = -1
        End If
        If delta < ecart Then
            nominateurOkAvContraintes = nominateurCourant + (1 - util) / 2
            If nominateurOkAvContraintes <= nominateurMax And denominateurCourant <= denominateurMax Then
                ecart = delta
                denominateurOk = denominateurCourant
                nominateurOk = nominateurOkAvContraintes
            End If
        End If
    Next
    Debug.Print "meilleur résultat jusqu'à d=" & Pressision
    Debug.Print nominateurOk & " / " & denominateurOk & " = " & nominateurOk / denominateurOk
    Debug.Print "Ecrat : " & ecart

[nodjim]

C'est curieux cette distorsion entre le numérateur et le dénominateur. Conséquence: les meilleures estimations pour ton réel seront celles à 2 chiffres avant la virgule, par exemple 100PI. il faut regarder de près l'erreur que tu vas faire avec ton rationnel proche. Enfin, maintenant, ça dépendra de ce que tu en feras.
Sinon, tu peux estimer le réel comme un rationnel proche dont la longueur de la séquence décimale est 6. ça devrait donner une approxim assez fiable et facile à calculer.
314,15928

[Polack77]

Bonjour nodjim

Code: Tout sélectionner

Sinon, tu peux estimer le réel comme un rationnel proche dont la longueur de la séquence décimale est 6. ça devrait donner une approxim assez fiable et facile à calculer.

Oulalala j'ai rien compris :doh:

PS :
Oui cette distorsion est curieuse, tout comme de devoir transformer un réel en deux entiers... Surtout que par la suite cette valeur est re-transformée en réel :mur:. Tout ceci est en faite dû à un format de transfert de donnée qui n’a pas pas vraiment bien évolué. Je cherche à changer ça mais on ne veux m’entende "et re :mur: ". En attendant je voudrais réduire les erreurs.

On fait pas toujours ce qu'on voudrait :ptdr:

Heeee comment fait-on une citation sur ce fofo svp ?

[ampholyte]

Bonjour nodjim

Heeee comment fait-on une citation sur ce fofo svp ?

Utilise la balise [QUOTE ] [/quote] sans l'espace dans la première balise.

Sinon tu peux faire répondre en dessous du poste d'une personne.


As-tu une précision recherchée précise ? (centième près, millième près, millionième près ?) Ou est-ce un paramètre de ta fonction ?

(Je vais essayer de mon côté)

[Polack77]

Utilise la balise sans l'espace dans la première balise.

Sinon tu peux faire répondre en dessous du poste d'une personne.

Vue merci :happy3:

As-tu une précision recherchée précise ? (centième près, millième près, millionième près ?) Ou est-ce un paramètre de ta fonction ?

C'est un paramètre

(Je vais essayer de mon côté)

Merci encore

----------------------------------------------------------

De mon coté, je cherche à "filtré" les les calcul avec deux règles que j'ajoute :
- Si ma valeur d'entrée a 5 chiffres après la virgule, il n'est pas utile de testé les dénominateur de moins de 1000 (heeee encore que... En écrivant ça j'ai un gros doute... L'impression qu'il vas falloir aussi un quelque-chose sur la partie entière et fonction de la précision attendu... Encore que... J'y réfléchi...)
- J'ajoute le paramètre "ecartAcceptable". Dé que je respecte l'écart imposé je stop le calcul. Si je n’arrive pas a respecter l’écart j'en informe la fonction appelante (en gros je remonte une erreur qui devras être gérée en amont de cette fonction... Sans doute découpé ma valeur en deux, la partie entière, et le restant sur le quel je relancerais le calcul)

Enfin encore en réfection tout ça quoi ^^

[ampholyte]

Tes valeurs d'entrées et de sortie sont vraiment énormes. Est-ce vraiment nécessaire de monter aussi haut pour ton numérateur et dénominateur ? Car si les réels entrés en paramètre sont assez petit, il n'y a peut-être pas besoin de monter autant.

[Polack77]

Oui, c'est bien pour ça que je veux ajouter la notion d’écart acceptable pour ne pas prolonger le calcul inutilement.
Le problème est que mes réels d'entrés peuvent aussi bien être "très" important comme "très" petit. Le maximum et le minimum de ces valeurs ont été imposé par moi.

[ampholyte]

Oui, c'est bien pour ça que je veux ajouter la notion d’écart acceptable pour ne pas prolonger le calcul inutilement.
Le problème est que mes réels d'entrés peuvent aussi bien être "très" important comme "très" petit. Le maximum et le minimum de ces valeurs ont été imposé par moi.

Hum je vois, la notion d'écart acceptable te permettra de sortir plus rapidement de la "boucle infernale". J'ai pu retrouver avec mon code les valeurs de pi (du moins 355/113). Je vais essayer de voir avec cette notion d'écart acceptable. Je te tiens au courant .

[nodjim]

Attention, je déconseille formellement de retravailler avec ce rationnel approximatif pour reconstituer le nombre réel. On va droit dans le mur avec cette méthode...

[ampholyte]

Attention, je déconseille formellement de retravailler avec ce rationnel approximatif pour reconstituer le nombre réel. On va droit dans le mur avec cette méthode...

Je suis d'accord, la méthode ne fonctionne que si le numérateur et dénominateur sont assez petits, ce qui n'est pas le cas ici. De quel rationnel parles-tu ? (l'ecart ? ou le réel de base ?)

[Dlzlogic]

Bonjour,
Je ne sais pas si ça peut servir, mais je vais donner un exemple.
Mon logiciel travaille sur des données très grandes, 6 chiffres avant la virgule, et normalement 3 chiffres après.
Je fais une première étape qui consiste à faire un changement de variable, une translation, pour avoir des valeurs plus petites.
En fait, je veux me limiter à 7 chiffres significatifs, ce qui correspond à un float en C.
Là j'avais 2 choix, soit travailler en float, soit travailler en long, le nombre de décimales est conservé, je profitais donc des 2 chiffres supplémentaires de la caractéristique.
J'ai bien réfléchi une quinzaines de jours avant de me décider, et le résultats est tout à fait satisfaisant.

[ampholyte]

Bonjour,
Je ne sais pas si ça peut servir, mais je vais donner un exemple.
Mon logiciel travaille sur des données très grandes, 6 chiffres avant la virgule, et normalement 3 chiffres après.
Je fais une première étape qui consiste à faire un changement de variable, une translation, pour avoir des valeurs plus petites.
En fait, je veux me limiter à 7 chiffres significatifs, ce qui correspond à un float en C.
Là j'avais 2 choix, soit travailler en float, soit travailler en long, le nombre de décimales est conservé, je profitais donc des 2 chiffres supplémentaires de la caractéristique.
J'ai bien réfléchi une quinzaines de jours avant de me décider, et le résultats est tout à fait satisfaisant.

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.