Quel est le moyen le plus rapide de calculer le péché et le cos ensemble?

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:

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.

  • Sun a eu sinco () depuis 1987 au moins (vingt-trois ans; j’ai une page de manuel)
  • HPUX 11 l’a eu en 1997 (mais n’est pas dans HPUX 10.20)
  • Ajouté à la glibc dans la version 2.1 (février 1999)
  • Devient un intégré dans gcc 3.4 (2004), __builtin_sincos ().

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.