LES FONCTIONS DE MATH.H REPROGRAMMÉES
MoDDiB
Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
-
26 nov. 2003 à 20:40
w0lverine_xx Messages postés 1 Date d'inscription dimanche 26 février 2006 Statut Membre Dernière intervention 18 février 2007 - 18 févr. 2007 à 12:17
w0lverine_xx Messages postés 1 Date d'inscription dimanche 26 février 2006 Statut Membre Dernière intervention 18 février 2007 - 18 févr. 2007 à 12:17
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/18234-les-fonctions-de-math-h-reprogrammees
https://codes-sources.commentcamarche.net/source/18234-les-fonctions-de-math-h-reprogrammees
18 févr. 2007 à 12:17
((Par contre, asin et acos ne sont pas définies en -1 et 1 c'est normal que Belzel ait une erreur...))
15 juin 2006 à 01:49
Il faut trouver une autre solution, en passant par une transformée, par exemple pour la fonction tangente aux points proches de PI/2 (modulo PI).
Généralement la transformation utilisera une fonction simple à calculer possèdant la même discontinuité, par exemple l'hyperbole (calculée avec l'opétation d'inversion c'est à dire une division), et en assurant la continuité avec les autres points de la fonction en scindant l'intervalle de définition en plusieurs parties: certaines calculées avec un développement limité simple, d'autres calculées avec la transformée préalable et un autre développement limité de la fonction transformée.
Pour le calcul de l'exponentielle ou du logarithme, on fait de même en tirant partie du fait que les flottants sont représentés en interne sous une forme exponentielle (de base 2, mais la base utilisée n'a pas d'incidence sur le choix de la méthode, étant donné les propriétés des logarithmes et exponentielles), ce qui ramène le calcul à un intervalle restreint (borné par des valeurs finies) où le développement limité de la fonction transformée assure la précision demandée (même aux valeurs extrèmes de l'intervalle si le développement limité utilisé est défini en prenant un point médian convenablement choisi dans l'intervalle) et représentable dans le type flottant du résultat (puisqu'il ne sert à rien de calculer avec une meilleure précision).
8 juin 2006 à 00:20
* Le développement limité d'une fonction est son expression sous forme d'un polynome au voisinage d'un point à partir desvaleurs de ses dériviées en ce point. C'est une série dont la limite tend vers la fonction. Elle comprend une infinité de termes quisont despuissances de la variable pondérées par les coefficients du polynome, eux-mêmes ne dépendant que desvaleurs des dérivées successives en un seul point. Onconnait précisement les valeurs des dérivées successives en 0 des fonctions trigonométriques (ces valeurs de dérivées sont établies par démonstration de théorèmes à partie des définitions des fonctions, et chaque valeur détermine une identité remarquable, mais le développement limité n'est pasune identité remarquable)
* Une identité remarquable n'est pas forcément polynomiale et s'exprime le plus souvent sous forme d'une formule finie. Une identité remarquable est par exemple: sin(x)=cos(x+PI/2)
Je n'ai pas fait de confusion: une fonction approchante à l'infini n'est PAS mathématiquement identique à lafonction elle-même, donc le développement limité d'une fonction en un point reste différent de la fonction, même s'il permet d'approcher la valeur de la fonction avec un écart aussi petit que l'on veut. L'identité n'est établie QUE pour la valeur de la fonction au même point que celui pour lequel le développement limité a été défini. Pour toutes les autres valeurs, on obtient seulement une valeur approchante.
On utilise les développements limités pour approcher la fonction car on connait à l'avance la limite de précision du résultat,ce qui permet de déterminer le nombre de termes suffisants pour la série du développpement limité.
7 juin 2006 à 22:45
merci pour ces précisions, il me semble que cette fois-ci ton commentaire est constructif car il apporte une vraie méthode pour améliorer ces algorithmes. Je t'encourage d'ailleurs à publier une source qui tiendrait compte de ces techniques.
Je mettrais cependant 2 bémols :
- je trouve ton "Si vous voulez vraiment être utiles" un poil désagréable... et surtout pas très malin! D'après les commentaires qui te précédent j'ai la sensation (et la satisfaction) que plusieurs personnes ont appris qqc grace à cette source. Il est certain qu'il ne s'agit que d'une introduction à l'analyse numérique, mais je crois qu'elle était nécessaire sur un site comme celui-ci.
- je pense que tu confonds "identité remarquable" et "développement limité"... non ?
2 juin 2006 à 01:27
Les meilleures librairies mathématiques actuellement (les plus rapides et les plus précises) pour PC sont celles écrites par Intel (mais elles sont sous licence commerciale). Microsoft a développé ses propres versions, mais elles sont moins bonnes et légèrement moins précises. Le compilateur GNU/C dispose de librairies mathématiques excellentes (meilleures que celles de Microsoft) mais pas encore au niveau de celles d'Intel.
Toutefois, dèsqu'on sort du cadre des calculs numériques sur les flottants normalisés IEEE, les librairies Intel sont insuffisantes. A ce jour, les meilleures librairies en haute précision sont celles de MathLab (licence commerciale), loin devant SCILab (commercial aussi), en attendant que le projet GNU améliore son projet concurrent et libre.
Si vous voulez vraiement être utiles, participez aux projets mathématiques GNU... Il y a beaucoup à apprendre, et dans les discussions vous aurez accès àdestas de travaux de référence libres publiés par des chercheurs mathématiciens d'universités publiques (donc travauxlibres de droit) ou publiés depuis longtemp (travaux désormais libres de droit, leurs brevets ayant expiré).
2 juin 2006 à 01:17
Tout algorithme de calcul mathématique (dans une librairie ou implanté dansle silicium d'un processeur) a été normalement soigneusement étudiée pour borner avec précision les erreurs de calcul intermédiaires: on doit utiliser les théorèmes issus de l'analyse!
D'ailleurs, cette recherche des algorithmes de calcul est une branche à part entière des mathématiques, appelée "l'analyse numérique", et est l'objet de nombreux traités et ouvrages de référence, et elle dispose de ses propres théorèmes. C'est aujourd'hui d'ailleurs la branche la plus active des mathématiques du fait de ses applications concrètes en informatique et dans l'ingéniérie pour la simulation numérique.
Consultez donc les nombreuses publications de l'ACM et de l'IEEE à ce sujet, l'IEEE ayant même défini des normes internationales très précises à ce sujet, normes appliquées dans les systèmes informatiques (processeurs) et langages de programmation normalisés (langages C/C++, Java, Fortran, Cobol, ADA, Pascal, etc...).
2 juin 2006 à 01:02
Pour que le critère de convergence soit applicable il faut évidemment ramener la valeur absolue (non relative) à une valeur inférieure à 1. Dans le cas des fonctions sinusoïdales, une fois ramené par symétries et congruences à l'intervalle [0,PI/2], l'intervalle de lavaleur x dans l'intervalle est encore trop grand pour assurer la convergence, cependant x*2/PI est dans l'intervalle[0,1].
On traite alors le cas de x=PI/2 à part (résultat connnu: sin(PI/2)=1,cos(PI/2)=0) car le critère de convergence n'est pas satisfait. Notez qu'on peut aussi utiliser deux développements limités séparés pour sinus et cosinus, et les utiliser chacun sur l'intervalle [0,PI/4] où le critère de convergence est garanti (et offre une meilleure précision finale, avec un degré inférieur dans le développement limité nécessaire pour la valeur maximale, donc une plus grande rapidité de calcul).
(Noter que pour les valeurs négatives, le développement limité converge moins bien et est plus instable et moins précis à cause de l'alternance du signe des termes du polynome; onévite le probème en necalculant les développements limités que sur les valeurs positives)
D'autre part, on gagne en temps de calcul (et en précision finale) en écrivant les polynomes de développements limités sous la forme:
(...(((x+C[n])*x+C[n-1])*x+C[n-2])...)*x+C[0]
(puisqu'en effet on n'évalue pas les exposants successifs de x)
On notera que sous cette forme, les termes de plus grands degrés sont calculés depuis le début et leur apport s'amenuise au fur et à mesure puisque x est inférieur à 1. On évite l'imprécision du résultat final causée par l'accumulation d'erreurs d'arrondis. Pour garantir cela, ondoit veiller à ce que chaque terme contribue au maximum pour la moitié de lavaleur finale. Or, si on calcule le développement limité de sin(x/(PI/2)) dans l'intervalle [0,PI/4], on garantie effectivement cela.
Le dernier pas à faire pour l'optimisation est dans la façon de ramener le calcul dans l'intervalle:celanécessite normalement un calcul de congruence modulo 2PI, et laséparation des cas entre les diférents octants. Or c'est simple à faire: ondivise d'abord la valeur de x par 2PI, et alors leflottant se décompose souslaforme d'une puissance de 2 et d'une mantisse. Lapuissancepeut être ignorée par masquage en le forçant à 0 après une dénormalisation si l'exposant est négatif (équivalent à un décalage binaire de la mantisse), ce qui réalise la congruence, il ne reste alors plus qu'une mantisse dans [0,1], et on traite séparément les cas où la mantisse vaut 0 ou 1 et dont le résultat est connu. Il ne reste plus alors qu'à calculer le développement limité comme indiqué ci-dessus.
Des optimisations similaires existent aussi pour le calcul du logarithme et de l'exponentielle. Il suffit de connaître et appliquer les identités remarquables de ces fonctions!
On trouve ces optimisations (qui ont aussi l'énorme avantage de borner les erreurs d'arrondis et d'assurer la continuité des fonctions et de leurs différentielles) dans TOUTE bonne librairie mathématique.
1 juin 2006 à 12:33
http://www.cse.iitk.ac.in/users/manindra/primality.pdf
20 mai 2006 à 17:01
Le site des nombres premiers n'existent plus maintenant je crois.
Peux-tu donner la formule stp?
6 févr. 2006 à 14:34
Je te demandais comment on gagnait des termes. Ce que je lis dans ta réponse c'est grosso-modo "si si ça marche"...
Par exemple tu dis "on le met à profit [...] pour réduire la mantisse à [0, 2^-32]", OK mais comment ?
2 févr. 2006 à 21:37
On le met à profit dans l'évaluation des fonctions cycliques (sin, cos...), ou même pour réduire la variable mantisse à un intervalle encore plus faible par exemple dans [0, 2?-32] ce qui accroit très sensiblement la vitesse de convergence du développement limité (d.l.), en enréduisant le dégré, puisque les termes résiduels non calculés dedegré plus élevés du d.l. deviennent inférieurs àlalimite de précision de la somme du polynome (et donc non représentables).
Cette optimisation est très efficace pour les valeurs les plus grandes de la mantisse x, et pour les mantisses les plus petites, le degré des termes du polynome les rend déjà faibles encore plus rapidement.
Les fonctions optimisables de cette façon:
* sin, cos, tan (exploitation du cycle, et des symétries)
* log, exp, sqrt (exploitation de la séparation mantisse/exposant)
Le but est évidemment de réduire le nombre de boucles avecuncritère basé nonpassur une précision absolue (différenceavec la valeur exacte théorique) mais une précision relative (ou pourcentage), cette dernière étant déjà connue à l'avance en fonction du type de nombre (parexemple un long double sur 80 bits possède une mantisse de 64 bits dont la précision relative est de 2^-64).
Ces optimisations sont encore plus essentielles si on travaille sur des nombres à très grande précision (comme BigDecimal en Java)
2 févr. 2006 à 09:34
Concernant les optimisations pour un calcul de collisions, ok.
Concernant les critiques sur ce code, je te dirais de lire l'introduction : "Les algos utilisés ici ne sont ni plus précis ni plus performants que math.h. Il s'agit juste de comprendre comment un ordinateur calcule les cos, sin ,tan, log, exp, pow, ...". Il est certain qu'en pratique toutes ces opérations sont implémentées en hard. Ce code est purement pédagogique et explique de façon algorithmique une manière de faire ces opérations. D'autre part il répond à plusieurs post du forum.
Soit l'implémentation de LibC est de loin plus performante. Mais qui arrive à relire un tel code ???
Je te rappelle que cppfrance est un site pédagogique, et non pas un lieu de combat entre plusieurs codes concurrents.
De même pour le test de primalité, il est vrai que le tri des 100 premiers nombres premiers permettrait d'optimiser le calcul par dichotomie. Mais là encore ce n'est pas l'objectif de la source.
En revanche je ne vois pas en quoi l'ecriture du nombre au format IEEE (signe/mantisse/exposant) permettrait de s'arrêter plus tôt dans le développement limité. Quelle simplification y vois-tu ?
29 janv. 2006 à 00:20
je ne comprends pas cette phrase, tu peux expliquer?
28 janv. 2006 à 21:18
Toutes les vraies implémentations des fonctions trigo utilisent cela car ça accélère énormément la convergence des développements limités (c'est-à-dire que la précision relative demandée est atteinte avec undegré de polynome très nettement inférieur, qu'on peut prédéterminer à l'avance et donc écrire sans boucle avec un nombre limité et fixe d'opérations linéaires).
Le test deprimalitéest non optimum aussi: il ne profite pas dufait que les 100 premiers nombres premiers sont triés,et la boucle évalue sqrt(x) à chaque étape...
Bref c'est bien à titre pédagogique mais ce code est inutile et trop lent en pratique.
Regardez plutôt l'implémentation dans la LibC de GNUGCC (ou même celle fournie avec votre compilateur). Le FPU interne de votre processeur implémente de façon matérielle de tels algorithmes optimisés pour les flottants float,double, et long double.
Une telle librairie pour des nombres plus précis pourrait utiliser une telle librairie mais devrait autant que possible profiter des opérations réalisées de façon matérielle (et c'est possible pour réduire le nombre d'opérations à effectuer de façon logicielle).
Autre fonctions mathématiques utiles et manquantes: le calcul dans des espaces vectoriels de polynomes, dans les champs cycliques, la fonction powmod() très utilisée en cryptographie (RSA, logarithmes discrets)...
28 janv. 2006 à 20:57
en partant du développement limité de chacun, mais en lescalculant en parallèle puisqu'il y a de nombreux facteurs communs, et puisque la séparation des quadrants est identique pour sinus et cosinus. D'ailleurs je m'étonne que la librairie C standard ne fournisse pas cette fonction de calcul simultané de sinus et cosinus.
Maintenant je m?étonne que pour tester la collision de deux points tu doivent passer par un calcul d'angles et de fonctions trigonométrique alors qu'un simple calcul de distance (ou plutôt du carré de la distance) suffit et n'emploie que des opérations linéaires simples avec polynomes du second degré uniquement, même en 3D (ou même en 4D si tu tiens compte du temps avec la vitesse des particules, ce qui permet d'anticiper leurs collisions et réduire considérablement le nombre de couples de particules à tester, notamment si tu veux réduire l'espace de recherche aux seuls points de l'univers présents dans un trapézoïde de visibilité qu'on peut approximer facilement avec une demi-sphère englobante exprimée par un simple point et un rayon: tout point hors de cette demi-sphère 4D ne peut être présent à l'image suivante, et il est possible de préduire à l'avance quand ce point y entrera pour alorsqppliquer une réelle projection, ce qui réduit aussi le nombre de projections à calculer).
Notes: une projection 3D ne nécessite pas de réexécuter un calcul trigonométrique pour chaque point, il suffit de calculer une seule fois la matrice 4D de transformation en 3D et de l'utiliser pour tous les points à représenter dans la scène (l'application de la matrice à un point se réduit alors à un simple calcul linéaire réduit à quelques termes).
Sinon la collision ne dépend pas non plus de cette matrice de transformation, et le calcul du sous-ensemble de points de la scène où il est utile de faire un test de collision ne dépend pas non plus de cette transformation.
1 oct. 2005 à 22:08
En fait, il faudrait mettre par exemple :
if ( x == +1 ) return PI/2.0;
if ( x == -1 ) return -PI/2.0;
Sinon, je bosse sur un moteur de collisions 3D. Il doit calculer 16 cos() et 16 sin() pour chaque collision (et il peut y avoir + de 100 000 particules). Et pour info, je n'ai pas gagné de temps de calcul, j'en ai même perdu. Pourquoi ?
Parce que le compilateur (gcc, avec devcpp) peut optimiser le code, et accélérer de 900% le temps de calcul des cos/sin. J'arrive à calculer 20 000 000 de cos() / secondes avec mon Duron 1 GHz.
1 oct. 2005 à 21:36
1 oct. 2005 à 20:38
J'ai testé ...
if (x<=-1 || x>=1) return numeric_limits<double>::quiet_NaN();
... mais j'ai des problèmes avec acos ( 1 ) et acos ( -1 )
alors j'ai fait ca :
if ( x == +1 ) return 1.5707963267948966192313216916398;
if ( x == -1 ) return 4.7123889803846898576939650749193;
if (x<-1 || x>1) return numeric_limits<double>::quiet_NaN();
30 nov. 2003 à 15:58
30 nov. 2003 à 13:36
http://perso.wanadoo.fr/mathprepa/calc/analyse/bessely.html
Very useful
29 nov. 2003 à 12:02
Pour ceux que ça interesse :
http://www.cse.iitk.ac.in/news/primality.pdf
Par contre c'est un peu pipo de dire que l'algo ne fait que 13 lignes. Le tout premier test étant : si N est de la forme a^b alors le nombre n'est pas premier ! Je veux pas dire mais c'est pas si facile à voir (pas trop compliqué non-plus). Mais bref, c'est juste pour dire que pour le coder il faut plus de 13 lignes !
J'en ferai peut-être une source...
27 nov. 2003 à 22:46
27 nov. 2003 à 22:44
Pour Kirua ... oh la feignasse... t'aurais pu au moins jeter un coup d'oeil !
Mon algo n'a rien de bien sorcier! Sur le principe c'est effectivement tester tous les nombres impairs jusqu'à la racine de x; mais avant de passer à cette méthode radicale, je me sers d'une base de connaissance : les 100 plus petits nombres premiers. Le centième est qqc comme 541 il me semble et du coup vérifier un nombre inférieur à 541² = 292681 est quasiment immédiat! Bien sur plus la base de connaissances est grande pus l'algo est rapide pour les vérifier les grands nombres. Tu vois ça n'a rien de révolutionnaire mais je ne me souvient pas avoir déjà vu la combinaison de ces deux principes.
Sinon je ne connaissais pas l'alog des 3 indiens, tu pourrais me le filer que je regarde ça ?
Quant au crible d'érato c'est une méthode que je trouve très élégante mais pour être efficace elle demande bcp de mémoire ce qui la limite au petits nombres (elle devient donc sans interet). Pour mémoire (et pour ceux que ça interesse) je vais quand même décrire rapidement cette méthode. En gros on regarde si le nombre est multple de 2. Non ? Alors on retire tous les multiples de 2 de la liste des possiblités. Ensuite on fait pareil avec 3. Puis avec 5 (puisque 4 est dejà retiré). Etc...
Sinon je réitere ma demande concernant les fonctions de Bessel de deuxieme espece....Quelqu'un aurait-il la formule ?
27 nov. 2003 à 22:26
Baravo.
Seb, 18 ans, maubeuge
27 nov. 2003 à 17:02
pour les nombres premiers, c'est quoi (en français) ton algo?
en gros, moi je vois 3 possibilités:
1/ tester tous les nombres premiers inférieurs à la racine du nombre en question
2/ l'algo en 11 lignes des 3 étudiants indiens dont ils parlaient dans le Sciences & Vie Hors-Série Les Nombres Premiers :-P (oulà, dur ^^)
3/ générer une liste grâce au crible d'eratosthène jusqu'à avoir dépassé ou atteint le nombre cherché
à savoir qu'i lfaut qd meme utiliser le crible pour la méthode 1 donc... la 3 devient désuète, voir idiote lol :-P
c'est quoi ta manière de faire, si originale :-) :-)
26 nov. 2003 à 23:53
26 nov. 2003 à 20:40