Ca m'embête un peu quand même cette histoire de rationnels. La complexité de mon algo sera multipliée par la taille des données à cause des PGCD (avec, en plus, un gros facteur invisible grâce à Landau mais qui se sentira dans les temps d'exécution).

Je me demande si travailler avec des flottants 80 bits et tolérer un epsilon d'écart sur la condition d'arrêt ne serait pas plus judicieux. M'enfin il va forcément faire quelques itérations supplémentaires de temps en temps, pour rectifier les erreurs. Faut voir leur coût par rapport au x constante x O(bits) introduit par les rationnels...
Tu avais bossé sur une bibliothèque rapide de gros flottants non ? Par rapport à l'utilisation de flottants natifs, la perte de vitesse est sensible ? Tu penses que ta bibliothèque serait adaptée ?