Thibaut (./1) :
Les calculs se limitant à des additions, des multiplications et des divisions, une solution pour s'affranchir des imprécisions serait de travailler sur Q. Vous connaissez peut être d'autres solutions.

MPFI peut être une solution : https://gforge.inria.fr/projects/mpfi/ (Arithmétique d'intervalle de flottant ==> A la fin tu as un intervalle entourant ta valeur).
Une autre solution est IRRAM : http://irram.uni-trier.de/ (Jamais utilisé par contre).

Thibaut (./1) :
Une idée qui me vient serait d'amortir le coût de la réduction. Après toute opération, on regarde si le numérateur ou le dénominateur du résultat dépassent sqrt(2^bits), ce qui se fait en O(1). S'ils sont inférieurs, je pense qu'aucune opération ne risque de les faire déborder dans l'immédiat. Si l'on dépasse cette limite, on lance un calcul de PGCD afin de diviser les deux composantes par le PGCD. On limite donc au minimum les survenues de cette opération très couteuse.

Faire le PGCD tout le temps n'est pas si inefficace car les facteurs augmentent très vite avec les rationels.
Une autre solution est de diviser par un gros facteur que l'on sait diviser les deux mais cela nécessite de connaitre l'algorithme exact de calcul (exemple sub resultant GCD ).
Sinon teste avec MPQ : gmplib.org