Z+exponent ou Q+exponent

Actuellement l'implémentation de F utilise une mantisse(Z) plus un exposant. Cependant cette écriture ne permet pas d'avoir une fonction de division sans arrondit alors que les autres fonctions de base ne le demande pas.

De plus dans les analyses il est très probable que l'on mélangera des rationnels avec les flottants. Donc il pourrait être intéressant d'utiliser Q+exponent.

De plus également cela donne une version de Q qui reste raisonable pour représenter le plus grand double.

@lcorrenson

Je ne connais pas bien ses représentations en série entière. Mais en googlelant un peu je suis tombé sur ce vielle article: A new representation of the rational numbers for fast easy arithmetic (1979). Où de manière amusante les écritures binaires avec une infinité de 1 à gauche écrit 1'.... sont étendues à d'autres répétitions 01'... -> ...0101010101... pour donner les rationnels ainsi -1=1' et 1/3= 01'1! J'imagine que @melquiond tu connais mais sinon c'est rigolo et rapide à lire.

Oui c'est possible, il faut faire attention à la normalisation : il faut faire oddify sur le numérateur et le dénominateur.

En fait, il n'y aurait normalement aucune raison de ne pas utiliser Q tout seul. La seule raison d'introduire F tient en deux objectifs:

• les quantités de la forme 2^n sont fréquentes en analyse de précision, on tend même à calculer sur des o(n) comme en analyse, en disant que x est un o(n) quand |x| < 2^-n. Or 2^-n n'a pas de représentation compacte dans Q pour n grand. Cependant, en général, on a rarement |n|>60 donc le Q associé reste en général entre 2 et 4 mots.
• beaucoup plus problématique, la représentation utilisée pour Q est bien connue pour être très inefficace : le nombre n/(n+1) est très proche de 1 mail il prend une immense taille en mémoire, alors qu'on peut l'encadrer avec un nombre F de taille log(n). Pour l'analyse réelle, il vaut mieux utiliser pour Q une représentation en série entière. C'était d'ailleurs mon autre idée pour faire les calculs sur Q.

En conclusion, je pense qu'il vaut mieux utiliser Q tout seul que Q+exponent.

Je me suis trompé, je voulais parler de fractions continues. https://en.wikipedia.org/wiki/Continued_fraction

Oui, c'est connu, et tu peux ensuite aller plus loin en représentant tes nombres (et pas juste les rationnels) par des automates arbitraires et en définissant des opérations arithmétiques entre automates, etc. Je ne suis pas sûr que ce soit très utile en pratique, même s'il y a des gens qui ont des implantations à base de transformations de Moebius par exemple.

Par contre, je n'ai pas compris cette histoire comme quoi un nombre de la forme n / (n + 1) ~= 1 - 1/n + 1/n^2 peut être approché par un nombre dans F de taille log(n). Une bonne approximation dans F va plutôt avoir une taille 2log(n) et comme c'est aussi la taille de la version exacte, je ne vois pas trop l'intérêt.

Par contre, je suis d'accord que les fractions continues permettent d'obtenir facilement des approximations compactes de nombres. Mais même dans le cas de n/(n+1), ça ne va pas être très utile puisque la seule approximation non exacte fournie par fraction continue est 1 (ce qui explique pourquoi il n'est pas possible de trouver un nombre dans F de taille log(n) qui approche n/(n+1)).

Peut-être que l'exemple est mal choisi. Mais l'idée est qu'en faisant les calculs sur Q, on a rapidement des tailles pour numérateurs et dénominateur qui explosent. Calculer dans F évite ce problème. Peut-être que le véritable besoin est de trouver une approximation dans Q à p-bits près.