Calculer avec des rationnels - Page 1

Bonjour,

Avec un algo que je suis en train de (tenter de) mettre au point, les résultats risquent de ne pas être très précis après les nombreuses itérations qui composent le calcul. En effet, l'inexactitude des nombres flottants se cumulera et risque de mener à des résultats sous optimaux, ou plutôt de provoquer de nombreuses itérations superflues pour réussir à bouffer les miettes d'imprécision qui font croire qu'on n'a pas convergé.

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.

Si l'on part sur des rationnels, la question est : y a-t-il des méthodes pour gérer efficacement les débordements ? En effet, au fil des opérations, les numérateurs et dénominateurs peuvent devenir énormes (a/b + c/d entraine une multiplication de b par d). Comment réduire efficacement les fractions ?

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.

Il existe sans doute des voies plus intelligentes...

Je crois qu'il touche sa bille dans le traitement des nombres décimaux avec une grande précision.

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

Merci beaucoup pour avoir pris un peu de ton temps !

MPFI, je pense que je mets de côté. De ce que j'ai compris dans mes cours, l'arithmétique d'intervalle c'est beau mais
1 - lent
2 - ça mène à des fourchettes très larges (notamment dans mon cas où la condition du théorème de Moore n'est pas respectée)

IRRAM : Super intéressant. On a la garantie de travailler sur R !? Impressionnant Dommage que ce soit en C++.

GMP : Parfait. S'annonce rapide et adapté pour les gros gros calculs. C'est visiblement pile poil ce qu'il me faut.

Tu as un peu plus d'infos sur le "subresultant GCD" ? (ah ah, quand on tape "subresultant pgcd" dans google, ce topic arrive en 1ère page). On dirait que ça s'applique à des calculs de PGCD de polynômes, pas d'entiers.

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 ?

Il y a aussi MPIR, dont la raison d'être, d'après http://mpir.org/ , est

MPIR is an open source multiprecision integer library.

Developer friendly community.
Links with hardware and software vendors.
Development of parallel algorithms.
Support out-of-the-box for Linux, Apple, Sun and Microsoft Windows.
GNU LGPL license. Full interface compatibility with GMP.

Thibaut (./4) :
MPFI, je pense que je mets de côté. De ce que j'ai compris dans mes cours, l'arithmétique d'intervalle c'est beau mais
1 - lent 2 - ça mène à des fourchettes très larges (notamment dans mon cas où la condition du théorème de Moore n'est pas respectée)

L’arithmétique d'intervalle est juste deux fois plus lent qu'une arithmétique normale.
Par contre les fourchettes très larges sont effectivement possibles, mais en général, il suffit de prendre de grosse précisions et ca passe, sauf si c'est ton calcul est vraiment chiant, auquel cas, toute solution est couteux.
C'est en tout le cas plus simple (et c'est basé sur MPFR qui est basé sur GMP).

Thibaut (./4) :
IRRAM : Super intéressant. On a la garantie de travailler sur R !? Impressionnant Dommage que ce soit en C++.

Jamais utilisé mais ca ne sera pas plus rapide que l'arithmétique d'intervalle.

Thibaut (./4) :
GMP : Parfait. S'annonce rapide et adapté pour les gros gros calculs. C'est visiblement pile poil ce qu'il me faut.

Oui GMP est très utilisé pour çà

Thibaut (./4) :
Tu as un peu plus d'infos sur le "subresultant GCD" ? (ah ah, quand on tape "subresultant pgcd" dans google, ce topic arrive en 1ère page). On dirait que ça s'applique à des calculs de PGCD de polynômes, pas d'entiers.

Oui c'est un algo sur les polynome, mais il y a une technique pour éviter que les coefficients internes ne grossissent trop vite sans utiliser de GCD.
Voir http://www-fourier.ujf-grenoble.fr/~parisse/giac/doc/fr/algo.html#htoc16

Thibaut (./5) :
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 ?

Oui MPFR. Et la perte de vitesse est d'environ d'un facteur 20 à 100 selon les calculs (et tu multiplies par 2 pour MPFI), mais ensuite le cout d'augmenter la précision de 53 à 530 bits est très faible.
Toute solution hors double sera aussi lente voir plus. Et la solution des rationnels aussi.

Si tu veux une solution rapide, il n'y a pas d'autres solutions que de calculer les erreurs dans toute la chaine de calcul et de faire avec. Voir http://lipforge.ens-lyon.fr/www/crlibm/ qui implante une telle solution pour calculer sur les cosinus / sinus / ....
Tu peux aussi utiliser la technique des "double double" pour augmenter la précision. Voir http://en.wikipedia.org/wiki/Quadruple_precision_floating-point_format

Lionel Debroux (./5) :
MPIR is an open source multiprecision integer library.

MPIR est un fork de GMP qui n'apporte d'intérêt que si tu veux utiliser Microsoft Visual C++.

L’arithmétique d'intervalle est juste deux fois plus lent qu'une arithmétique normale.

Si j'ai bien retenu la partie de mon cours d'intervalles qui nous intéresse ici :
On a deux intervalles [a;b] et [c,d].
- Addition : [a+c;b+d] soit 2 opérations
- Soustraction : [a-d;b-c] soit 2 opérations
- Multiplication : [min{ac,ad,bc,bd} ; max{ac,ad,bc,bd}] soit 4 opérations + 6 tests = 10 (à la louche)
- Division : C'est le bordel. Si l'intervalle dénominateur contient 0, on obtient une union de deux intervalles disjoints ne contenant pas zéro et ayant respectivement une borne tendant vers -oo et +oo.

Les multiplications sont très gourmandes et les divisions par des intervalles contenant zéro :
A) pourrissent la précision du résultat si on remplace l'union par [-oo;+oo]
B) font gonfler la quantité d'intervalles à gérer dans tous les calculs qui suivront si on conserve une union (qui, elle -même, pourra générer de nouvelles unions).
Dans le premier cas, j'aurais une précision pourrie (surtout que le théorème de Moore ne s'applique pas à mes calculs ("si chaque variable apparaît une seule fois dans l'expression à calculer, alors l'extension naturelle est la plus précise possible")).
Dans le second cas, mon programme sera plus que nombres d'unions x 10 fois plus lent.

De plus, j'ai pas de bol, mon algorithme compare des résultats avec zéro. A chaque intervalle résultat contenant zéro, je serais obligé de créer 3 branches. J'aurais une explosion exponentielle du nombre de sous problèmes à résoudre en appliquant à chacun mon algo (lui-même exponentiel au pire)


Merci pour tes nouvelles suggestions, idem pour Lionel
GMP me parait vraiment bien. Dans un premier temps, j'essaierai la quadruple précision (double double), qui semble le meilleur compromis vitesse de calcul / itérations superflues pour détruire les miettes.