Comment fonctionnent les fonctions trigonométriques?

Ainsi, au lycée, et probablement à l'université, on nous apprend à utiliser les fonctions trigonométriques, ce qu'elles font et les types de problèmes qu'elles résolvent. Mais ils m'ont toujours été présentés comme une boîte noire. Si vous avez besoin du sinus ou du cosinus de quelque chose, vous appuyez sur le bouton sin ou cos de votre calculatrice et vous êtes prêt. Ce qui est bien.

Ce que je me demande, c'est comment les fonctions trigonométriques sont généralement implémentées.

Tout d'abord, vous devez faire une sorte de réduction de portée. Les fonctions de déclenchement sont périodiques, vous devez donc réduire les arguments à un intervalle standard. Pour commencer, vous pouvez réduire les angles entre 0 et 360 degrés. Mais en utilisant quelques identités, vous réalisez que vous pourriez vous en tirer avec moins. Si vous calculez des sinus et des cosinus pour des angles compris entre 0 et 45 degrés, vous pouvez démarrer votre façon de calculer toutes les fonctions trigonométriques pour tous les angles.

Une fois que vous avez réduit votre argument, la plupart des puces utilisent un algorithme CORDIC pour calculer les sinus et les cosinus. Vous pouvez entendre des gens dire que les ordinateurs utilisent la série Taylor. Cela semble raisonnable, mais ce n'est pas vrai. Les algorithmes CORDIC sont bien mieux adaptés à une implémentation matérielle efficace . ( Les bibliothèques de logiciels peuvent utiliser la série Taylor, par exemple sur du matériel qui ne prend pas en charge les fonctions trigonométriques.) Il peut y avoir un traitement supplémentaire, en utilisant l'algorithme CORDIC pour obtenir d'assez bonnes réponses, mais en faisant autre chose pour améliorer la précision.

Il y a quelques améliorations à ce qui précède. Par exemple, pour les très petits angles thêta (en radians), sin (thêta) = thêta à toute la précision que vous avez, il est donc plus efficace de simplement renvoyer thêta que d'utiliser un autre algorithme. Donc, dans la pratique, il y a beaucoup de logique de cas spécial pour obtenir toutes les performances et la précision possibles. Les puces avec des marchés plus petits peuvent ne pas faire autant d'efforts d'optimisation.

edit: Jack Ganssle a une discussion décente dans son livre sur les systèmes embarqués, "The Firmware Handbook" .

FYI: Si vous avez des contraintes de précision et de performance, les séries de Taylor ne doivent pas être utilisées pour approximer des fonctions à des fins numériques. (Conservez-les pour vos cours de calcul.) Ils utilisent l' analyticité d'une fonction en un seul point , par exemple le fait que toutes ses dérivées existent à ce point. Ils ne convergent pas nécessairement dans l'intervalle d'intérêt. Souvent, ils font un mauvais travail de distribution de la précision de l'approximation de la fonction afin d'être "parfait" juste à côté du point d'évaluation; l'erreur grossit généralement vers le haut lorsque vous vous en éloignez. Et si vous avez une fonction avec une dérivée non continue (par exemple, les ondes carrées, les ondes triangulaires et leurs intégrales), une série de Taylor vous donnera la mauvaise réponse.

La meilleure solution "facile", lorsqu'on utilise un polynôme de degré maximum N pour approcher une fonction f (x) donnée sur un intervalle x0 <x <x1, est de l' approximation de Chebyshev ; voir Recettes numériques pour une bonne discussion. Notez que Tj (x) et Tk (x) dans l'article de Wolfram que j'ai lié à utilisé le cos et le cosinus inverse, ce sont des polynômes et en pratique vous utilisez une formule de récurrence pour obtenir les coefficients. Encore une fois, voir Recettes numériques.

edit: Wikipedia a un article semi-décent sur la théorie de l'approximation . L'une des sources qu'ils citent (Hart, "Computer Approximations") est épuisée (et les copies utilisées ont tendance à être chères) mais entre dans de nombreux détails sur des choses comme celle-ci. (Jack Ganssle le mentionne dans le numéro 39 de son bulletin The Embedded Muse .)

edit 2: Voici quelques métriques d'erreur tangibles (voir ci-dessous) pour Taylor vs Chebyshev pour sin (x). Quelques points importants à noter:

1. que l'erreur maximale d'une approximation de série de Taylor sur une plage donnée est beaucoup plus grande que l'erreur maximale d'une approximation de Chebyshev du même degré. (Pour à peu près la même erreur, vous pouvez vous en tirer avec un terme de moins avec Chebyshev, ce qui signifie des performances plus rapides)
2. La réduction de la portée est une énorme victoire. Cela est dû au fait que la contribution des polynômes d'ordre supérieur diminue lorsque l'intervalle d'approximation est plus petit.
3. Si vous ne pouvez pas vous en sortir avec la réduction de plage, vos coefficients doivent être stockés avec plus de précision.

Ne vous méprenez pas: la série Taylor fonctionnera correctement pour sinus / cosinus (avec une précision raisonnable pour la plage -pi / 2 à + pi / 2; techniquement, avec suffisamment de termes, vous pouvez atteindre la précision souhaitée pour toutes les entrées réelles, mais essayez de calculer cos (100) en utilisant des séries de Taylor et vous ne pouvez pas le faire à moins d'utiliser l'arithmétique à précision arbitraire). Si j'étais coincé sur une île déserte avec une calculatrice non scientifique et que j'avais besoin de calculer le sinus et le cosinus, j'utiliserais probablement la série de Taylor car les coefficients sont faciles à retenir. Mais les applications du monde réel pour avoir à écrire vos propres fonctions sin () ou cos () sont suffisamment rares pour que vous feriez mieux d'utiliser une implémentation efficace pour atteindre la précision souhaitée - ce qui n'est pas le cas de la série Taylor .

Plage = -pi / 2 à + pi / 2, degré 5 (3 termes)

• Taylor: erreur max autour de 4.5e-3, f (x) = xx ³ /6 + x ⁵ /120
• Chebyshev: erreur maximale autour de 7e-5, f (x) = 0,9996949x-0,1656700x ³ + 0,0075134x ⁵

Plage = -pi / 2 à + pi / 2, degré 7 (4 termes)

• Taylor: erreur max d' environ 1.5E-4, f (x) = xx ^trois / 6 + x ⁵ /120 x ^sept / 5 040
• Chebyshev: erreur max d' environ 6E-7, f (x) = 0.99999660x-0.16664824x ³ + 0.00830629x ⁵ -0.00018363x ⁷

Plage = -pi / 4 à + pi / 4, degré 3 (2 termes)

• Taylor: erreur max autour de 2.5e-3, f (x) = xx ³ /6
• Chebyshev: erreur maximale autour de 1,5e-4, f (x) = 0,999x-0,1603x ³

Plage = -pi / 4 à + pi / 4, degré 5 (3 termes)

• Taylor: erreur max autour de 3.5e-5, f (x) = xx ³ /6 + x ⁵
• Chebyshev: erreur maximale autour de 6e-7, f (x) = 0,999995x-0,1666016x ³ + 0,0081215x ⁵

Plage = -pi / 4 à + pi / 4, degré 7 (4 termes)

• Taylor: erreur max d' environ 3E-7, f (x) = xx ³ /6 + x ⁵ /120 x ⁷ /5040
• Chebyshev: erreur max d' environ 1.2E-9, f (x) = 0.999999986x-0.166666367x ³ + 0.008331584x ⁵ -0.000194621x ⁷

Je crois qu'ils sont calculés en utilisant la série Taylor ou CORDIC . Certaines applications qui font un usage intensif des fonctions trigonométriques (jeux, graphiques) construisent des tables trigonométriques au démarrage afin de pouvoir simplement rechercher des valeurs plutôt que de les recalculer encore et encore.

Consultez l'article de Wikipédia sur les fonctions trigonométriques. Les recettes numériques sont un bon endroit pour en savoir plus sur leur implémentation dans le code .

Je ne suis pas vraiment mathématicien, mais ma compréhension de l'origine du péché, du cos et du tan est qu'ils sont, en un sens, observés lorsque vous travaillez avec des triangles à angle droit. Si vous prenez des mesures de la longueur des côtés d'un groupe de différents triangles à angle droit et que vous tracez les points sur un graphique, vous pouvez en extraire sin, cos et tan. Comme le souligne Harper Shelby, les fonctions sont simplement définies comme des propriétés de triangles à angle droit.

Une compréhension plus sophistiquée est obtenue en comprenant comment ces rapports se rapportent à la géométrie du cercle, ce qui conduit aux radians et à toute cette bonté. Tout est là dans l'entrée Wikipedia.

Le plus souvent pour les ordinateurs, la représentation des séries de puissance est utilisée pour calculer les sinus et les cosinus et ceux-ci sont utilisés pour d'autres fonctions trigonométriques. L'élargissement de ces séries à environ 8 termes calcule les valeurs nécessaires avec une précision proche de l'epsilon de la machine (le plus petit nombre à virgule flottante non nul pouvant être conservé).

La méthode CORDIC est plus rapide puisqu'elle est implémentée sur du matériel, mais elle est principalement utilisée pour les systèmes embarqués et non pour les ordinateurs standards.

Je voudrais étendre la réponse fournie par @Jason S.En utilisant une méthode de subdivision de domaine similaire à celle décrite par @Jason S et en utilisant des approximations de la série Maclaurin, une accélération moyenne (2-3) X sur le tan (), sin () Les fonctions, cos (), atan (), asin () et acos () intégrées au compilateur gcc avec l'optimisation -O3 ont été réalisées. Les meilleures fonctions d'approximation de la série Maclaurin décrites ci-dessous ont obtenu une précision double.

Pour les fonctions tan (), sin () et cos (), et par souci de simplicité, un domaine superposé de 0 à 2pi + pi / 80 a été divisé en 81 intervalles égaux avec des «points d'ancrage» à pi / 80, 3pi / 80, ..., 161 ppp / 80. Ensuite, tan (), sin () et cos () de ces 81 points d'ancrage ont été évalués et stockés. À l'aide des identités trigonométriques, une seule fonction de série Maclaurin a été développée pour chaque fonction trigonométrique. Tout angle compris entre ± l'infini peut être soumis aux fonctions d'approximation de trig parce que les fonctions traduisent d'abord l'angle d'entrée dans le domaine de 0 à 2pi. Cette surcharge de traduction est incluse dans la surcharge d'approximation.

Des méthodes similaires ont été développées pour les fonctions atan (), asin () et acos (), où un domaine qui se chevauchait de -1,0 à 1,1 était divisé en 21 intervalles égaux avec des points d'ancrage à -19/20, -17/20, .. ., 19/20, 21/20. Ensuite, seul atan () de ces 21 points d'ancrage a été stocké. Encore une fois, avec l'aide des identités trigonométriques inverses, une seule fonction de série Maclaurin a été développée pour la fonction atan (). Les résultats de la fonction atan () ont ensuite été utilisés pour approximer asin () et acos ().

Puisque toutes les fonctions d'approximation de trig inverse sont basées sur la fonction d'approximation atan (), toute valeur d'entrée d'argument à double précision est autorisée. Cependant, l'argument entré dans les fonctions d'approximation asin () et acos () est tronqué au domaine ± 1 car toute valeur en dehors de celui-ci n'a pas de sens.

Pour tester les fonctions d'approximation, un milliard d'évaluations de fonctions aléatoires ont été forcées d'être évaluées (c'est-à-dire que le compilateur d'optimisation -O3 n'était pas autorisé à contourner l'évaluation de quelque chose car certains résultats calculés ne seraient pas utilisés.) Pour supprimer le biais de l'évaluation d'un milliard nombres aléatoires et en traitant les résultats, le coût d'une exécution sans évaluation d'aucune fonction de trig ou de trig inverse a été effectué en premier. Ce biais a ensuite été soustrait de chaque test pour obtenir une approximation plus représentative du temps réel d'évaluation des fonctions.

Tableau 2. Temps passé en secondes à exécuter la ou les fonctions indiquées un milliard de fois. Les estimations sont obtenues en soustrayant le coût en temps de l'évaluation d'un milliard de nombres aléatoires indiqués dans la première ligne du tableau 1 des lignes restantes du tableau 1.

Temps passé dans le bronzage (): 18.0515 18.2545

Temps passé dans TAN3 (): 5.93853 6.02349

Temps passé dans TAN4 (): 6.72216 6.99134

Temps passé dans sin () et cos (): 19,4052 19,4311

Temps passé dans SINCOS3 (): 7.85564 7.92844

Temps passé dans SINCOS4 (): 9,36672 9,57946

Temps passé à atan (): 15,7160 15,6599

Temps passé dans ATAN1 (): 6.47800 6.55230

Temps passé dans ATAN2 (): 7.26730 7.24885

Temps passé dans ATAN3 (): 8.15299 8.21284

Temps passé dans asin () et acos (): 36.8833 36.9496

Temps passé dans ASINCOS1 (): 10.1655 9.78479

Temps passé dans ASINCOS2 (): 10,6236 10,6000

Temps passé dans ASINCOS3 (): 12.8430 12.0707

(Dans l'intérêt d'économiser de l'espace, le tableau 1 n'est pas montré.) Le tableau 2 montre les résultats de deux exécutions distinctes d'un milliard d'évaluations de chaque fonction d'approximation. La première colonne est la première exécution et la deuxième colonne est la deuxième exécution. Les nombres «1», «2», «3» ou «4» dans les noms de fonction indiquent le nombre de termes utilisés dans la fonction de série Maclaurin pour évaluer l'approximation de trig ou de trig inverse. SINCOS # () signifie que sin et cos ont été évalués en même temps. De même, ASINCOS # () signifie que asin et acos ont été évalués en même temps. Il y a peu de frais généraux supplémentaires pour évaluer les deux quantités en même temps.

Les résultats montrent que l'augmentation du nombre de termes augmente légèrement le temps d'exécution comme on pouvait s'y attendre. Même le plus petit nombre de termes a donné une précision d'environ 12 à 14 chiffres partout, sauf pour l'approximation tan () près de l'endroit où sa valeur s'approche de ± l'infini. On s'attendrait à ce que même la fonction tan () y ait des problèmes.

Des résultats similaires ont été obtenus sur un ordinateur portable MacBook Pro haut de gamme sous Unix et sur un ordinateur de bureau haut de gamme sous Linux.

Si vous demandez une explication plus physique du péché, du cos et du bronzage, réfléchissez à leur relation avec les triangles à angle droit. La valeur numérique réelle de cos (lambda) peut être trouvée en formant un triangle à angle droit avec l'un des angles étant lambda et en divisant la longueur du côté des triangles adjacent à lambda par la longueur de l'hypoténuse. De même pour le péché, utilisez le côté opposé divisé par l'hypoténuse. Pour la tangente, utilisez le côté opposé divisé par le côté adjacent. Le mémonique classique à retenir est SOHCAHTOA (prononcé socatoa).