Je voudrais calculer le sinus et le co-sinus d’une valeur ensemble (par exemple pour créer une masortingce de rotation). Bien sûr, je pourrais les calculer séparément l’un après l’autre comme a = cos(x); b = sin(x);
a = cos(x); b = sin(x);
, mais je me demande s’il existe un moyen plus rapide lorsque les deux valeurs sont nécessaires.
Edit: Pour résumer les réponses à ce jour:
Vlad a dit qu’il y a la commande asm FSINCOS
les deux calculant (presque en même temps qu’un appel à la seule FSIN
)
Comme Chi l’a remarqué, cette optimisation est parfois déjà effectuée par le compilateur (lors de l’utilisation des indicateurs d’optimisation).
caf a souligné, que les fonctions sincos
et sincosf
sont probablement disponibles et peuvent être appelés directement en incluant simplement math.h
L’ approche tanascius consistant à utiliser une table de consultation est discutée. (Cependant, sur mon ordinateur et dans un scénario de référence, il est 3 fois plus rapide que sincos
avec presque la même précision pour les virgules flottantes 32 bits.)
Joel Goodwin s’est associé à une approche intéressante d’une technique d’approximation extrêmement rapide avec une assez bonne précision (pour moi, c’est encore plus rapide que la consultation de la table)
Les processeurs Intel / AMD modernes ont des instructions FSINCOS
pour calculer simultanément les fonctions sinus et cosinus. Si vous avez besoin d’une optimisation forte, vous devriez peut-être l’utiliser.
Voici un petit exemple: http://home.broadpark.no/~alein/fsincos.html
Voici un autre exemple (pour MSVC): http://www.codeguru.com/forum/showthread.php?t=328669
Voici encore un autre exemple (avec gcc): http://www.allegro.cc/forums/thread/588470
J’espère que l’un d’eux aide. (Je n’ai pas utilisé cette instruction moi-même, désolé.)
Comme ils sont pris en charge au niveau du processeur, je m’attends à ce qu’ils soient beaucoup plus rapides que les recherches de table.
Modifier:
Wikipedia suggère que FSINCOS
été ajouté à 387 processeurs, vous pouvez donc difficilement trouver un processeur qui ne le supporte pas.
Modifier:
La documentation d’Intel indique que FSINCOS
est environ 5 fois plus lent que FDIV
(c.-à-d. La division en virgule flottante).
Modifier:
Veuillez noter que tous les compilateurs modernes n’optimisent pas le calcul du sinus et du cosinus dans un appel à FSINCOS
. En particulier, mon VS 2008 ne l’a pas fait de cette façon.
Modifier:
Le premier exemple de lien est mort, mais il existe toujours une version sur Wayback Machine .
Les processeurs x86 modernes ont une instruction fsincos qui fera exactement ce que vous demandez: calculez sin et cos en même temps. Un bon compilateur d’optimisation devrait détecter le code qui calcule sin et cos pour la même valeur et utiliser la commande fsincos pour l’exécuter.
Il a fallu quelques modifications des indicateurs du compilateur pour que cela fonctionne, mais:
$ gcc --version i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5488) Copyright (C) 2005 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ cat main.c #include struct Sin_cos {double sin; double cos;}; struct Sin_cos fsincos(double val) { struct Sin_cos r; r.sin = sin(val); r.cos = cos(val); return r; } $ gcc -c -S -O3 -ffast-math -mfpmath=387 main.c -o main.s $ cat main.s .text .align 4,0x90 .globl _fsincos _fsincos: pushl %ebp movl %esp, %ebp fldl 12(%ebp) fsincos movl 8(%ebp), %eax fstpl 8(%eax) fstpl (%eax) leave ret $4 .subsections_via_symbols
Tada, il utilise l’instruction fsincos!
Lorsque vous avez besoin de performances, vous pouvez utiliser une table sin / cos pré-calculée (une table le fera, stockée dans un dictionnaire). Eh bien, cela dépend de la précision dont vous avez besoin (peut-être que la table serait trop grande), mais elle devrait être très rapide.
Techniquement, vous y parvenez en utilisant des nombres complexes et la formule d’Euler . Ainsi, quelque chose comme (C ++)
complex res = exp(complex (0, x)); // or equivalent complex res = polar (1, x); double sin_x = res.imag(); double cos_x = res.real();
devrait vous donner sinus et cosinus en une seule étape. La façon dont cela se fait en interne est une question de compilateur et de bibliothèque utilisés. Cela pourrait (et pourrait) prendre plus de temps à le faire de cette façon (juste parce que la formule d’Euler est principalement utilisée pour calculer l’ exp
complexe en utilisant sin
et cos
– et non l’inverse), mais une optimisation théorique est possible.
modifier
Les en-têtes de
pour GNU C ++ 4.2 utilisent des calculs explicites de sin
et de cos
dans la polar
, donc cela ne semble pas très bon pour les optimisations à moins que le compilateur ne fasse de la magie (voir les -ffast-math
et -mfpmath
comme écrit en réponse de Chi ).
Vous pouvez calculer l’un ou l’autre puis utiliser l’identité:
cos (x) 2 = 1 - sin (x) 2
mais comme le dit @tanascius, une table précalculée est la voie à suivre.
Si vous utilisez la bibliothèque GNU C, vous pouvez alors:
#define _GNU_SOURCE #include
et vous obtiendrez des déclarations des fonctions sincos()
, sincosf()
et sincosl()
qui calculent les deux valeurs ensemble – probablement de la manière la plus rapide pour votre architecture cible.
De nombreuses bibliothèques mathématiques C, comme l’indique caf, ont déjà sincos (). L’exception notable est MSVC.
Et en ce qui concerne la recherche, Eric S. Raymond dans Art of Unix Programming (2004) (chapitre 12) dit explicitement ceci comme une mauvaise idée (au moment présent):
“Un autre exemple consiste à précalculer les petites tables – par exemple, une table de sin (x) par degré pour optimiser les rotations dans un moteur graphique 3D nécessitera 365 × 4 octets sur une machine moderne. , il s’agissait là d’une optimisation évidente de la vitesse: de nos jours, il peut être plus rapide de recalculer à chaque fois plutôt que de payer le pourcentage d’échecs de cache supplémentaires causés par la table.
“Mais à l’avenir, cela pourrait se reproduire à mesure que les caches s’agrandissent. Plus généralement, de nombreuses optimisations sont temporaires et peuvent facilement se transformer en pessimisations à mesure que les ratios de coûts changent. (de l’ art de la programmation Unix )
Mais à en juger d’après la discussion ci-dessus, tout le monde n’est pas d’accord.
Il y a des choses très intéressantes sur cette page du forum, qui sont axées sur la recherche de bonnes approximations rapides: http://www.devmaster.net/forums/showthread.php?t=5784
Disclaimer: Je n’ai utilisé aucun de ces trucs.
Mise à jour 22 février 2018: Wayback Machine est le seul moyen de visiter la page d’origine maintenant: https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate- sinus-cosinus
Je ne crois pas que les tables de consultation soient nécessairement une bonne idée pour ce problème. À moins que vos exigences de précision ne soient très faibles, la table doit être très volumineuse. Et les processeurs modernes peuvent effectuer beaucoup de calculs pendant qu’une valeur est extraite de la mémoire principale. Ce n’est pas une de ces questions auxquelles on peut répondre par des arguments (même pas les miens), tester et mesurer et considérer les données.
Mais je me tournerais vers les implémentations rapides de SinCos que vous trouverez dans des bibliothèques telles que ACML et Intel MKL.
Si vous êtes prêt à utiliser un produit commercial et que vous calculez un certain nombre de calculs sin / cos en même temps (pour pouvoir utiliser des fonctions vectorielles), vous devriez consulter la bibliothèque Math Kernel d’Intel.
Il a une fonction sincos
Selon cette documentation, la moyenne est de 13,08 horloges / élément sur le duo Core 2 en mode haute précision, ce qui, je pense, sera encore plus rapide que fsincos.
Cet article montre comment construire un algorithme parabolique qui génère à la fois le sinus et le cosinus:
DSP Trick: Approximation parabolique simultanée de Sin et Cos
http://www.dspguru.com/dsp/sortingcks/parabolic-approximation-of-sin-and-cos
Lorsque la performance est critique pour ce genre de chose, il n’est pas rare d’introduire une table de consultation.
Pour une approche créative, pourquoi ne pas élargir la série Taylor? Comme ils ont des termes similaires, vous pouvez faire quelque chose comme le pseudo suivant:
numerator = x denominator = 1 sine = x cosine = 1 op = -1 fact = 1 while (not enough precision) { fact++ denominator *= fact numerator *= x cosine += op * numerator / denominator fact++ denominator *= fact numerator *= x sine += op * numerator / denominator op *= -1 }
Cela signifie que vous faites quelque chose comme ceci: à partir de x et 1 pour le péché et le cosinus, suivez le modèle – soustrayez x ^ 2/2! du cosinus, soustrayez x ^ 3/3! du sinus, ajoutez x ^ 4/4! au cosinus, ajoutez x ^ 5/5! pour sine …
Je n’ai aucune idée si cela serait performant. Si vous avez besoin de moins de précision que sin () et cos (), cela peut être une option.
Il y a une solution intéressante dans la bibliothèque CEPHES qui peut être assez rapide et vous pouvez append / supprimer de la précision de manière assez flexible pour un peu plus de temps processeur.
Rappelez-vous que cos (x) et sin (x) sont les parties réelles et imaginaires de exp (ix). Nous voulons donc calculer exp (ix) pour obtenir les deux. Nous pré-calculons exp (iy) pour certaines valeurs discrètes de y comsockets entre 0 et 2pi. Nous décalons x sur l’intervalle [0, 2pi]. Ensuite, nous sélectionnons le plus proche de x et écrivons
exp (ix) = exp (iy + (ix-iy)) = exp (iy) exp (i (xy)).
Nous obtenons exp (iy) de la table de consultation. Et depuis | xy | est faible (au plus la moitié de la distance entre les valeurs y), la série de Taylor convergera bien en quelques termes, nous l’utilisons donc pour exp (i (xy)). Et alors nous avons juste besoin d’une multiplication complexe pour obtenir exp (ix).
Une autre bonne propriété de ceci est que vous pouvez le vectoriser en utilisant SSE.
Vous pouvez consulter http://gruntthepeon.free.fr/ssemath/ , qui propose une implémentation vectorisée SSE inspirée de la bibliothèque CEPHES. Il a une bonne précision (déviation maximale de sin / cos de l’ordre de 5e-8) et de la vitesse (légèrement supérieur à la valeur de fsincos sur une base d’appel unique, et un net gagnant sur plusieurs valeurs).
J’ai posté une solution impliquant un assemblage ARM en ligne capable de calculer à la fois le sinus et le cosinus de deux angles: Sinus / cosinus rapide pour ARMv7 + NEON
Une approximation précise et rapide de la fonction sin et cos simultanément, en javascript, peut être trouvée ici: http://danisraelmalta.github.io/Fmath/ (facilement importé vers c / c ++)
Avez-vous pensé à déclarer des tables de consultation pour les deux fonctions? Vous devrez quand même “calculer” sin (x) et cos (x), mais ce sera nettement plus rapide si vous n’avez pas besoin d’un degré élevé de précision.