[math] calcul sur flottants

Version imprimable

27/10/2009, 19h07
r0d

[math] calcul sur flottants

Bonjour à tous,

voilà, j'ai un gros soucis: j'avais fait un moteur de calcul (un truc qui récupère des chiffres en entrée, qui mouline un max, et qui ressort des suites de chiffres, le tout en flottants). Je n'ai pas le droit aux erreurs de calculs, alors pour éviter tout problème, j'avais commencé par implémenter une structure toute bête: 2 entiers, un pour la partie entière, un pour la partie décimale. Et voilà qu'aujourd'hui je reçois un mail qui pose quelques "petits" problèmes, dont le suivant:
je dois maintenant appliquer des formules qui contiennent des logarithmes (ln) - ce qui, au passage, j'avais demandé dès le départ et on m'a dit qu'il n'y en aurait pas.

Et là j'avoue que je ne sais pas comment faire des logarithmes sur ma structure. D'autant plus que mon code doit être le plus rapide possible (et il est déjà trop lentm je dois améliorer ça aussi), et sans erreur d'approximation.

J'ai jeter un coup d'oeil du côté de boost, mais je ne parviens pas à trouver une solution qui offre:
1. la justesse de calcul (pas d'erreur d'approximation)
2. la rapidité ultime d'exécution.

Si vous avez des pistes, des idées, des liens, quoi que ce soit sur le sujet, je suis preneur :D

merci
27/10/2009, 21h54
androz

Sans vouloir être indiscret, quelle est l'utilité d'avoir une aussi grande précision ? En plus, les logarithme sont déjà des fonction approximées ou tabulées par des méthodes annexes, il n'en existe pas de réelle valeur exacte.
Je demande ça parce que si ça se trouve, il existe des manière plus simple en reprenant le problème à la base.

Quel est le format des nombres à traiter ? Combien de chiffres avant/après la virgule ? Est-il possible de les représenter par des rationnels ? n'y a-t-il pas un moyen dès le départ de les tronquer (par exemple dans un programme de calcul utilisant un algo de Runge-Kutta pour résoudre des équa diff, j'avais des variables du style 2e8 et donc les résultats ne convergeaient jamais. En mettant un facteur d'échelle j'ai gagné en précision...) ?

Désolé de ne pouvoir t'apporter de réponse miracle, mais tu n'es pas le seul à avoir des problèmes de précision sur les nombres.....
27/10/2009, 22h30
Invité
Salut r0d,

Comment tu gères ta partie décimale? Tu as pour tes nombres une structure comme ca?
Code:

1 2 3 4 struct { int ent; int frac; }
Et la partie fractionnaire s'exprime en milliardièmes? (donc frac<1000000000) c'est ca? ou alors tu raisonnes en base 2 et ta partie fractionnaire fait 31 ou 32 bits?

Si tu es en base 10, ton système représente tous les nombres décimaux compris entre 2 milliards et moins deux milliards, avec neuf décimales de précision. Je ne suis pas certain que ce soit la meilleure façon de gérer ce genre de calcul, mais bon, si tout est déjà implémenté comme ça...

Pour le logarithme (je te montre le népérien, les autres il faut multiplier en fin de parcours par une constante que tu précalculeras), tu procèdes en deux étapes :

1- D'abord, tu cherches la partie entière, qui est la plus grande puissance de la base inférieure à ton nombre... En base 10, le logarithme de 2135.3345 a pour partie entière 3 (1000 est la plus grande puissance de 10 inférieure à 2134,3345).

A cette fin, tu peux précalculer une table de toutes les puissances de ta base, et y faire une recherche dichotomique. Comme ton format de données est fait d'entiers, les comparaisons vont être très rapides.

En fait, tu peux utiliser cette méthode de recherche dans une table pour calculer une valeur approchée à une décimale, en précalculant, par exemple les puissances 1 1,1 1,2 etc... de la base. L'intéret de cette première étape, c'est qu'elle va accélérer la suivante.

2- Ensuite, tu divises ton nombre par la puissance obtenue, et tu utilises une formule d'approximation.
La plus immédiate (pour le log népérien) est
Code:

1 2 3 log(1+x)=x-x^2/2+x^3/3-x^4/4+ .... -1<x<1
Comme la série est alternée, pour des valeurs positives de x, cette formule te permet de maîtriser l'erreur d'approximation... Pour de petites valeurs absolues de x, elle converge très vite.

Si x vaut 1/10, 8 termes suffisent pour la précision que tu veux. D'où l'intéret de l'étape précédente (et pour les logarithmes népériens, e^0,1 = 1,1...). Par ailleurs, comme tous les termes seront compris entre 1 et 1e-9, tu peux effectuer tous les calculs en double, ce sera largement assez précis (les doubles ont 16 décimales) et bien plus rapides...

Donc, si tu as un nombre compris entre 1e-9 et 4e9 (c'est ton cas, je crois). Tu vas

1- précalculer une table d'environ 500 entrées, donnant toutes les puissances à une décimale de e entre exp(-21) et exp(23) (environ 1e-9 et 4e9).
2- rechercher dans cette table (par dichotomie) l'approximation à une décimale de ton log (ca va te faire 9 comparaisons en moyenne)
3- diviser ton nombre par la puissance trouvée précédemment, et appliquer la formule de taylor au huitième ordre. (ca devrait te faire environ 8multiplications et 7 additions).
4- ajouter les résultats des étapes 2 et 3
5- si tu es dans une autre base, multiplier par une constante...

Si tu as déjà défini les 4 opérations de base et les comparaisons sur tes structures, ceci devrait fonctionner.

Maintenant, il y a certainement des routines en boite, il y a aussi des approximations plus rapides (mais pas intuitives), mais si tu veux essayer de le faire toi même, c'est la bonne façon, et ca doit tourner assez vite (d'autant plus que tu peux faire le calcul du polynome en flottants double précision, et les comparaisons en entiers, ce qui va très très vite...)

Côté vitesse, tu remarqueras qu'il y a un trade-off entre les deux premières étapes.

Si tu précalcules une table à une décimale, il te faut une table de 500 entrées, et donc 9 comparaisons pour trouver la valeur. Puis il te faut une série de 8 termes (donc 8 multiplications)

Si tu précalcules à 2 décimales tu auras une table de 5000 entrées, et donc 12 comparaisons. Mais il ne te faudras plus qu'une série de 4 termes (4 multiplications). Il est vraisemblable que cela ira un peu plus vite...

C'est probablement l'optimum. Pour trois décimales, tu vas avoir 15 comparaisons, et 3 multiplications...

Ensuite, tu dois pouvoir améliorer un peu le calcul du polynôme: la formule de Taylor n'est pas la meilleure approximation du logarithme, dans un très petit intervalle, et à 3 ou 4 termes. Tu peux peut être gagner encore une multiplication ou une comparaison comme cela...

Francois
28/10/2009, 09h44
r0d

Citation:

Envoyé par androz

Sans vouloir être indiscret, quelle est l'utilité d'avoir une aussi grande précision ?

Le truc c'est que j'ai une grande chaîne de calculs, avec l'erreur qui va se répercuter et s'amplifier.

Citation:

Envoyé par androz

En plus, les logarithme sont déjà des fonction approximées ou tabulées par des méthodes annexes, il n'en existe pas de réelle valeur exacte.

Oui je sais bien. J'ai juste besoin de trouver la meilleure approximation.

Citation:

Envoyé par androz

Quel est le format des nombres à traiter ? Combien de chiffres avant/après la virgule?

Les chiffres à traiter peuvent aller jusqu'à 2^30 (et c'est une contrainte que j'ai posé moi. Autrement dit, je dois la vérifier à certains endroits de mon moteur). Et la partie décimale, ben je dois juste trouver le meilleur compromis...

Citation:

Envoyé par androz

Est-il possible de les représenter par des rationnels ?

Non, pas moyen, il y a des flottants partout dans mes calculs (constantes, etc.), et même en entrée je reçois des double.

Citation:

Envoyé par androz

Désolé de ne pouvoir t'apporter de réponse miracle, mais tu n'es pas le seul à avoir des problèmes de précision sur les nombres.....

Oui je sais bien. S'il existait une réponse claire et définitive, je ne poserais pas la question ici ;)

@fcharton: merci pour ta réponse, je vais de ce pas implémenter ça et voir ec que ça donne.
28/10/2009, 12h31
Mac LAK

Si tu as besoin de "bases" mathématiques à ce sujet, les articles suivants de Wikipédia sont plutôt corrects : [ame]http://fr.wikipedia.org/wiki/Logarithme[/ame] [ame]http://fr.wikipedia.org/wiki/Table_de_logarithmes[/ame] [ame]http://fr.wikipedia.org/wiki/Logarithme_naturel[/ame]

C'est, à très peu de choses près, ce qu'explique fcharton. Simplement, là, tu as les formules exactes. Je sais que, pour ma part, je préfère causer directement aux maths dans ce genre de cas, je vois plus facilement les optimisations de calcul possibles.

Sinon, une autre possibilité serait de convertir ta structure dans un long double, effectuer l'opération de logarithme dessus, puis revenir à une structure en utilisant la fonction modf et deux casts (pour passer des deux long double issus de modf vers des entiers).
28/10/2009, 20h31
Invité

Citation:

Envoyé par Mac LAK

C'est, à très peu de choses près, ce qu'explique fcharton. Simplement, là, tu as les formules exactes. Je sais que, pour ma part, je préfère causer directement aux maths dans ce genre de cas, je vois plus facilement les optimisations de calcul possibles.

Je suis d'accord. Sur ce sujet, je recommande fermement le site de mathématica : http://mathworld.wolfram.com/Logarithm.html

C'est généralement un peu mieux gaulé que wiki.

Sur l'utilisation des maths, un point à bien comprendre c'est que l'approximation des fonctions (ou les calculs sur un ordinateur en général) font parfois appel à des astuces pas du tout évidentes. Un exemple que j'aime bien est la série de Taylor qui donne les fonctions trigonométriques (qu'on trouve sur tous les wiki). Elle est juste, elle converge sur tout R, mais très lentement si on ne prend pas de précaution... Et, sur un intervalle et à un degré donné, elle est toujours (nettement) moins bonne que l'approximation de Tchebitcheff d'ordre équivalent...

Il faut donc lire des maths, mais surtout des maths appliquées...

Pour des formules "toutes prêtes", je vais refaire de la pub gratuite pour mon ouvrage préféré: le Handbook of Mathematical Functions, d'Abramowitz et Stegun (Mac Lak, si t'as pas ca, jette toi dessus... c'est un peu difficile d'abord, mais c'est presque aussi bien que Knuth, et bon, Knuth, hein?).

Sinon, dans les trucs de bases, il y a le tome 2 de Knuth (en fait le début du chapitre 4 sur l'arithmétique), le Hardy et Wright sur la théorie des nombres (c'est pas fait pour les informaticiens, mais c'est fou le nombre d'idées utiles qu'on y trouve).

Pour les calculs de fonctions, et pour bien comprendre les problèmes sous jacents, je recommande (dans la catégorie "pas cher") "Theory of Approximation" d'Achieser (chez Dover). C'est un vieux livre, c'est assez pointu niveau maths (bacs S et prépas intégrées, passez votre chemin!), mais c'est vraiment très très bien, et très appliqué à l'informatique.

Citation:

Envoyé par Mac LAK

Sinon, une autre possibilité serait de convertir ta structure dans un long double, effectuer l'opération de logarithme dessus, puis revenir à une structure en utilisant la fonction modf et deux casts (pour passer des deux long double issus de modf vers des entiers).

Oui. En fait, les données de r0d ont 18 chiffres significatifs, soit à peine plus que la mantisse des double. Donc, si on élimine (par une recherche dichotomique) les logs les plus élevés, on doit pouvoir travailler en double, avec deux conversions.

C'est ce que je voulais dire en disant que la façon de coder n'est pas optimale. Moyennant quelques adaptations mineures pour les (très) grands nombres, les double classiques devraient suffire à l'utilisation qu'il en fait.

Francois
29/10/2009, 09h57
Mac LAK

Citation:

Envoyé par fcharton

C'est généralement un peu mieux gaulé que wiki.

Tout à fait. L'avantage de Wikipédia, c'est que c'est en général un peu plus accessible à celui dont les neurones matheux ont pris la poussière... ;)

Citation:

Envoyé par fcharton

(Mac Lak, si t'as pas ca, jette toi dessus... c'est un peu difficile d'abord, mais c'est presque aussi bien que Knuth, et bon, Knuth, hein?).

Noté, merci !

Citation:

Envoyé par fcharton

Oui. En fait, les données de r0d ont 18 chiffres significatifs, soit à peine plus que la mantisse des double. Donc, si on élimine (par une recherche dichotomique) les logs les plus élevés, on doit pouvoir travailler en double, avec deux conversions.

Au moins sur cette opération-là, en tout cas, où la double conversion sera à mon avis nettement moins coûteuse que le calcul de la série en virgule fixe...
Après, suivant la machine et le FPU installé, ça peut se négocier, effectivement. Mais pour UNE opération, moi, je passerais par la conversion et le FPU.

Citation:

Envoyé par fcharton

C'est ce que je voulais dire en disant que la façon de coder n'est pas optimale. Moyennant quelques adaptations mineures pour les (très) grands nombres, les double classiques devraient suffire à l'utilisation qu'il en fait.

Boaf, à la limite, des long double s'il le faut, mais c'est le principe de précaution plus qu'autre chose alors...