Rationnel à partir d'un réel

[François Guillet]

Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?

Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales,
il faudra choisir des contraintes supplémentaires.

Donc si j'essaie de reformuler la question, elle devient :
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

[Julien Arlandis]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales,
il faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Tu recherches quel D compris entre 0 et 1000 minimise la différence (r*D
- round(r*D)).
Après quoi N = round(r*D).

[Julien Arlandis]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales,
il faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Tu recherches quel D compris entre 0 et 1000 minimise la différence |r*D
- round(r*D)|.
Après quoi N = round(r*D).

[François Guillet]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité de
rationnels ou aucun, et que dans un cas comme j'ai donné le réel n'est
qu'une approximation à cause de son nombre limité de décimales, il faudra
choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le plus
près de r ?

Tu recherches quel D compris entre 0 et 1000 minimise la différence |r*D -
round(r*D)|.
Après quoi N = round(r*D).

Ok, merci, c'est le plus simple

[François Guillet]

Post by François Guillet

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité de
rationnels ou aucun, et que dans un cas comme j'ai donné le réel n'est
qu'une approximation à cause de son nombre limité de décimales, il faudra
choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le plus
près de r ?

Tu recherches quel D compris entre 0 et 1000 minimise la différence |r*D -
round(r*D)|.
Après quoi N = round(r*D).

Ok, merci, c'est le plus simple

Ca marche.
Il me restera à faire une table précalculée pour aller plus vite...

[Olivier Miakinen]

Je cherche un algorithme pour [approximer] un réel [par un] rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?

https://fr.wikipedia.org/wiki/Fraction_continue_et_approximation_diophantienne

[François Guillet]

Post by Olivier Miakinen

Je cherche un algorithme pour [approximer] un réel [par un] rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?

https://fr.wikipedia.org/wiki/Fraction_continue_et_approximation_diophantienne

Intéressant sur le fond, mais au-delà de mon besoin, je vais m'en tenir
à la méthode de Julien.

[Olivier Miakinen]

Post by François Guillet

Post by Olivier Miakinen

Je cherche un algorithme pour [approximer] un réel [par un] rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?

https://fr.wikipedia.org/wiki/Fraction_continue_et_approximation_diophantienne

Intéressant sur le fond, mais au-delà de mon besoin, je vais m'en tenir
à la méthode de Julien.

C'est pourtant beaucoup plus rapide et efficace : on obtient le résultat
500/3 au bout de seulement trois divisions, et le résultat optimal à
savoir 83333/500 avec seulement une division de plus. Certes il y a
quelques multiplications ensuite pour obtenir la fraction, mais cela
reste de l'ordre de 10, soit bien moins que les 1000 nécessaires avec
l'autre méthode¹.

166,666 = [166, 1, 1, 1, 166]

[166, 1] = 167/1
[166, 1, 1] = 333/2
[166, 1, 1, 1] = 500/3
[166, 1, 1, 1, 166] = 83333/500

¹ Quoique... en y réfléchissant, l'autre méthode peut se ramener à
des additions et soustractions, entre 3000 et 4000. Il faudrait savoir
si quatre divisions et une dizaine de multiplications prennent ou non
moins de temps que quelques milliers d'additions/soustractions.

[Julien Arlandis]

Post by Olivier Miakinen

Post by François Guillet

Post by Olivier Miakinen

Je cherche un algorithme pour [approximer] un réel [par un] rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?

https://fr.wikipedia.org/wiki/Fraction_continue_et_approximation_diophantienne

Intéressant sur le fond, mais au-delà de mon besoin, je vais m'en tenir
à la méthode de Julien.

C'est pourtant beaucoup plus rapide et efficace : on obtient le résultat
500/3 au bout de seulement trois divisions, et le résultat optimal à
savoir 83333/500 avec seulement une division de plus.

Je pense que François voulait une méthode très rapide à coder au delà
de sa performance, vu que D ne devait pas excéder 1000 je lui ai proposé
la méthode exhaustive qui n'est effectivement pas du tout optimale.

[François Guillet]

Post by Olivier Miakinen

Post by Olivier Miakinen

Je cherche un algorithme pour [approximer] un réel [par un] rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?

https://fr.wikipedia.org/wiki/Fraction_continue_et_approximation_diophantienne

Intéressant sur le fond, mais au-delà de mon besoin, je vais m'en tenir à
la méthode de Julien.

C'est pourtant beaucoup plus rapide et efficace : on obtient le résultat
500/3 au bout de seulement trois divisions, et le résultat optimal à
savoir 83333/500 avec seulement une division de plus.

Je pense que François voulait une méthode très rapide à coder au delà de sa
performance, vu que D ne devait pas excéder 1000 je lui ai proposé la méthode
exhaustive qui n'est effectivement pas du tout optimale.

Oui, je m'en doutais. En fait je ne sais pas pourquoi j'ai parlé de
table précalculée, le temps n'est pas critique ici, la formule ne sera
à calculer que de temps en temps. C'est pour des changements de
fréquences d'échantillonage de FFT entre 2 flux numériques, c'est plus
propre et facile de décimer d'un côté et de bourrer de l'autre, donc de
rester avec des entiers.

La méthode d'Oliver est plus élégante et sûrement aussi plus rapide, je
ne dis pas que je n'essaierai pas, j'aime bien aussi l'esthétique dans
le codage, mais comme tu m'as donné du tout cuit qui se code en 7
lignes, j'ai pris :-).

[Bruno Ducrot]

Bonjour,

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales,
il faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

r = 166,[6] (je noterai [] les chiffres correspondant à la période du
développement décimal).

(r - 100)/100 = 0,[6] = x (1)

On remarque que l'on a :
10x - 6 = 0,[6] = x

D'où 9x = 6, soit x = 2/3

En reportant dans (1), on obtient :
(r - 100)/100 = 2/3
soit
r = 200/3 + 100 = 500/3

Il me semble que c'est généralisable pour tout développement périodique.

À plus,

[Olivier Miakinen]

Post by Bruno Ducrot
r = 166,[6] (je noterai [] les chiffres correspondant à la période du
développement décimal).
[...]
Il me semble que c'est généralisable pour tout développement périodique.

Certes, mais je parierais que François avait en tête la représentation
d'un nombre à virgule flottante en informatique plutôt que celle d'un
rationnel avec développement périodique.

Par exemple, dans le nombre suivant on ne voit pas la période :
0,3058103975535168195718654434250764525993
... et pourtant ce nombre est très proche du rationnel 100/327.

[Bruno Ducrot]

Post by Olivier Miakinen

Post by Bruno Ducrot
r = 166,[6] (je noterai [] les chiffres correspondant à la période du
développement décimal).
[...]
Il me semble que c'est généralisable pour tout développement périodique.

Certes, mais je parierais que François avait en tête la représentation
d'un nombre à virgule flottante en informatique plutôt que celle d'un
rationnel avec développement périodique.
0,3058103975535168195718654434250764525993
... et pourtant ce nombre est très proche du rationnel 100/327.

Oui, tu as raison. J'ai mal lu.

Cependant, je me demande comment gérer des trucs du
genre 333,6666666.
On aura 333,6666666 = 1001/3 mais du coup 1001 est supérieur à 1000.

À plus,

[MAIxxxx]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales, il
faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Ben d'abord 166,666 est bien un rationnel qui peut s'écrire 166 666/1000
On peut se rappeler qu'un rationnel en notation décimale avec virgule
comporte une suite de chiffres périodique.
Pour un réel non rationnel comme Pi on a souvent utilisé 22/7 soit
3,142857 142857 ... évidemment c'est approximatif,
on peut faire pareil avec e =2,718281828...

Si on a une suite de x chiffres après la virgule seulement pour un
nombre en base dix par exemple p,abc on trouvera une notation
fractionnaire en sommant la série entière périodique correspondante p +
a/10 + b/100 + c/1000 +a/10000 +b/100000 + ...
qui converge un rationnel p +abc/999

Dans le cas de 166,666 p=166 et abc=666
p+abc/999= 166 +666/999 = 166 2/3 = (498 +2) /3 soit 500/3

là c'est intéressant parce que 666 = 2/3 (999) mais on peut avoir
intérêt à rallonger le nombre de chiffres après la virgule pour avoir un
résultat sympathique.

Par exemple pour Pi ~ 3.14 la formule donne 3 + 14/99 = 311/99 pas
sympathique.
On peut rajouter des décimales à 3,14 par exemple 3,14abcd donne 3+
14abcd/999999 et s'arranger pour que 14abcd/999999 soit réductible pas
difficile 999999= 27x7x11x13x37 on peut choisir abcd pour avoir un "bon"
dénominateur. Si on veut 7 comme dénominateur 14abcd doit être multiple
de 27x11x13x37 = 142857 déjà indiqué. ça donne 3 + 1/7 = 22/7 valeur
habituelle. On a le choix pour abcd.

[Samuel DEVULDER]

Post by François Guillet
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Ah je faisais ce genre de trucs avec ma calculette au collège. Comme l'a
indiqué Olivier, les fractions rationnelles sont le moyen le plus rapide
pour trouver p/q généraux. Avec la contrainte N<=1000 D<=1000 ca ne
marche plus, mais je trouve cette contrainte "arbitraire". En général on
veut simplement les N et D les plus petits. Ainsi 1/3 est quelquepar une
représentation plus sympathique de 0.3334 que 333/1000. Pourquoi cette
valeur 1000?

[Samuel DEVULDER]

Post by Samuel DEVULDER

Post by François Guillet
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Ah je faisais ce genre de trucs avec ma calculette au collège. Comme l'a
indiqué Olivier, les fractions rationnelles

Non! *continues* les fractions. Les fractions continues sont le point
clef. Elles convergent très vites vers la meilleure approximation
rationnelle.

Post by Samuel DEVULDER
sont le moyen le plus rapide pour trouver p/q généraux.

J'ai retrouvé un bout de code que j'avais fait en basic Thomson à
l'époque calculant les développement limités symboliquement[*] et qui
convertissait les flottants au format P/Q. Le basic est lent, très lent
même, surtout sur thomson et la méthode des fractions continues est de
loin la plus rapide. J'ai extrait le code que voici (3 lignes: 1 pour
l'init + 1 pour la sortie + 1 pour le calcul de l'approximation
suivante, X est le flottant à convertir/afficher):

------8>-------------------------------------------------------------------
2070 G=X:H=G:O=INT(G):B=O:E=1:A=1:D=0 ' INIT
2080 IF ABS(X-B/E)<1E-7 THEN PRINT B;:IF E<>1 THEN PRINT "/";E;: RETURN
ELSE RETURN ' SORTIE B/E (ou B si E=1) SI APPROX SUFFISANTE
2090 H=1/(H-O):O=INT(H):C=B*O+A:A=B:B=C:C=E*O+D:D=E:E=C:GOTO 2080 '
CALCUL APPROX SUIVANTE
------8>-------------------------------------------------------------------

sam.
____
[*] J'avais retrouvé ce programme en 2013 et je l'avais alors fait
tourné sur quelques exemples:
https://forum.system-cfg.com/viewtopic.php?p=72366#p72366

De fait la précision de 1E-8 dans le programme est trop grosse pour la
représentation flottante. C'est pour ca que j'ai utilisé 1E-7 ici. Dans
ton cas comme tu veux que D<=1000, je pense que 1E-3 devrait être le mieux.

[Emphyrio]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales, il
faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Quand il y a une périodicité c'est assez simple encore faut il avoir un
programme capable de la "lire".

En général, on fait r*10 - r si on obtient un entier N alors c'est réglé
puisque r = N/9 sinon on fait r*100 - r et alors r = N'/99 etc...

[ast]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une infinité
de rationnels ou aucun, et que dans un cas comme j'ai donné le réel
n'est qu'une approximation à cause de son nombre limité de décimales, il
faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

Avec quel langage travailles-tu ?

En python les objets de type "float" ont
une méthode "as_integer_ratio" qui fournit le
numérateur et le dénominateur du rationnel
qui est stocké pour représenter le réel

Les réels sont stockés sur 64 bits (IEEE754) et
sont donc toujours représentés par des rationnels

Post by François Guillet

r=1.25
r.as_integer_ratio()

(5, 4)


Attention quand même. Les rationnels ne peuvent
pas tous être représentés avec un nombre fini de
bits

r=1/3 # La valeur enregistrée est la meilleure
# approximation possible

Post by François Guillet

r=1/3
r.as_integer_ratio()

(6004799503160661, 18014398509481984)

[ast]

Post by ast

r=1/3
r.as_integer_ratio()

(6004799503160661, 18014398509481984)

r=0.3
r.as_integer_ratio()

(5404319552844595, 18014398509481984)

[ast]

Post by François Guillet
Je cherche un algorithme pour convertir un réel en rationnel.
Si j'ai r=166,666, comment trouver N/D = 500/3 ?
Je me doute que parce qu'à un réel donné peut correspondre une
infinité de rationnels ou aucun, et que dans un cas comme j'ai donné
le réel n'est qu'une approximation à cause de son nombre limité de
décimales, il faudra choisir des contraintes supplémentaires.
comment trouver N et D entiers inférieurs à 1000 tels que N/D soit le
plus près de r ?

encore mieux

Post by François Guillet

from fractions import Fraction
Fraction(3.1415926535897932).limit_denominator(10)

Fraction(22, 7)

Post by François Guillet

Fraction(3.1415926535897932).limit_denominator(100)

Fraction(311, 99)

Post by François Guillet

Fraction(3.1415926535897932).limit_denominator(1000)

Fraction(355, 113)