Quel est le moyen le plus rapide de calculer le sin et le cos ensemble?

Je voudrais calculer à la fois le sinus et le cosinus d'une valeur ensemble (par exemple pour créer une matrice de rotation). Bien sûr, je pourrais les calculer séparément l'un après l'autre a = cos(x); b = sin(x);, mais je me demande s'il existe un moyen plus rapide lorsque vous avez besoin des deux valeurs.

Edit: Pour résumer les réponses à ce jour:

• Vlad a dit qu'il y avait la commande asm qui calculaitFSINCOSles deux (presque en même temps qu'un appel àFSINseul)

• 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 fonctionssincosetsincosfsont probablement disponibles et peuvent être appelées directement en incluant simplementmath.h

• l' approche tanascius consistant à utiliser une table de consultation est controversée. (Cependant, sur mon ordinateur et dans un scénario de référence, il fonctionne 3 fois plus vitesincosqu'avec presque la même précision pour les virgules flottantes 32 bits.)

• Joel Goodwin lié à 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 recherche de table)

Les processeurs Intel / AMD modernes ont des instructions FSINCOSpour 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 aidera. (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.

Edit:
Wikipedia suggère qu'il a FSINCOSété ajouté à 387 processeurs, vous pouvez donc difficilement trouver un processeur qui ne le prend pas en charge.

Edit:
la documentation d'Intel indique que FSINCOSc'est à peu près 5 fois plus lent que FDIV(c'est-à-dire la division en virgule flottante).

Edit:
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.

Edit:
Le premier exemple de lien est mort, mais il existe toujours une version sur la Wayback Machine .

Les processeurs x86 modernes ont une instruction fsincos qui fera exactement ce que vous demandez - calculer 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 changements d'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 <math.h> 

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 fera l'affaire, stockée sous forme de dictionnaire). Eh bien, cela dépend de la précision dont vous avez besoin (peut-être que la table serait trop grande), mais cela devrait être très rapide.

Techniquement, vous y parviendrez en utilisant des nombres complexes et la formule d'Euler . Ainsi, quelque chose comme (C ++)

complex<double> res = exp(complex<double>(0, x));
// or equivalent
complex<double> res = polar<double>(1, x);
double sin_x = res.imag();
double cos_x = res.real();

devrait vous donner sinus et cosinus en une seule étape. Comment cela est fait en interne est une question du compilateur et de la bibliothèque utilisés. Cela pourrait (et pourrait) bien prendre plus de temps pour le faire de cette façon (simplement parce que la formule d'Euler est principalement utilisée pour calculer le complexe en exputilisant sinet cos- et non l'inverse) mais il pourrait y avoir une optimisation théorique possible.

Éditer

Les en-têtes <complex>de GNU C ++ 4.2 utilisent des calculs explicites de sinet à l' cosintérieur polar, donc cela ne semble pas trop bon pour les optimisations à moins que le compilateur ne fasse un peu de magie (voir les commutateurs -ffast-mathet -mfpmathcomme écrit dans la 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 faire:

#define _GNU_SOURCE
#include <math.h>

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.

Il y a des choses très intéressantes sur cette page du forum, qui se concentre sur la recherche de bonnes approximations rapides: http://www.devmaster.net/forums/showthread.php?t=5784

Avis de non-responsabilité: Je n'ai utilisé aucun de ces produits moi-même

Mise à jour du 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

De nombreuses bibliothèques de mathématiques C, comme l'indique caf, ont déjà sincos (). L'exception notable est MSVC.

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

Et concernant la recherche, Eric S. Raymond dans l' Art de la programmation Unix (2004) (chapitre 12) dit explicitement que c'est une mauvaise idée (à l'heure actuelle):

"Un autre exemple est le précalcul de petites tables - par exemple, une table de sin (x) par degré pour optimiser les rotations dans un moteur graphique 3D prendra 365 × 4 octets sur une machine moderne. Avant que les processeurs soient suffisamment plus rapides que la mémoire pour exiger la mise en cache , il s'agissait d'une optimisation évidente de la vitesse. De nos jours, il peut être plus rapide de recalculer à chaque fois plutôt que de payer pour le pourcentage d'échecs de cache supplémentaires causés par la table.

"Mais à l'avenir, cela pourrait changer à 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ût changent. La seule façon de savoir est de mesurer et de voir." (de l' art de la programmation Unix )

Mais, à en juger par la discussion ci-dessus, tout le monde n'est pas d'accord.

Je ne pense 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 grande. Et les processeurs modernes peuvent faire 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 correctement par un argument (pas même le mien), tester et mesurer et examiner les données.

Mais je regarderais les implémentations rapides de SinCos que vous trouvez dans des bibliothèques telles que ACML d'AMD et MKL d'Intel.

Si vous êtes prêt à utiliser un produit commercial et que vous calculez un certain nombre de calculs sin / cos en même temps (afin que vous puissiez utiliser des fonctions vectorisées), vous devriez consulter la bibliothèque du noyau mathématique d'Intel.

Il a une fonction sincos

Selon cette documentation, il fait en moyenne 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:

Astuce DSP: Approximation parabolique simultanée de Sin et Cos

http://www.dspguru.com/dsp/tricks/parabolic-approximation-of-sin-and-cos

Lorsque les performances sont essentielles pour ce genre de choses, il n'est pas rare d'introduire une table de consultation.

Pour une approche créative, que diriez-vous d'élargir la série Taylor? Puisqu'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: en commençant à x et 1 pour sin et cosinus, suivez le modèle - soustrayez x ^ 2/2! du cosinus, soustrayez x ^ 3/3! à partir de sinus, ajoutez x ^ 4/4! au cosinus, ajoutez x ^ 5/5! à sinus ...

Je ne sais pas si ce serait performant. Si vous avez besoin de moins de précision que les valeurs intégrées de sin () et cos (), cela peut être une option.

Il existe une solution intéressante dans la bibliothèque CEPHES qui peut être assez rapide et vous pouvez ajouter / supprimer de la précision de manière assez flexible pour un peu plus / moins de temps CPU.

Rappelez-vous que cos (x) et sin (x) sont les parties réelle et imaginaire 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 comprises entre 0 et 2pi. Nous décalons x à l'intervalle [0, 2pi). Ensuite, nous sélectionnons le y qui est 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 recherche. Et puisque | xy | est petit (au plus la moitié de la distance entre les valeurs y), la série de Taylor convergera bien en quelques termes seulement, nous utilisons donc cela pour exp (i (xy)). Et puis nous avons juste besoin d'une multiplication complexe pour obtenir exp (ix).

Une autre propriété intéressante de ceci est que vous pouvez le vectoriser en utilisant SSE.

Vous pouvez jeter un œil à 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 (écart maximal de sin / cos de l'ordre de 5e-8) et de la vitesse (surpasse légèrement fsincos sur une base d'appel unique, et un gagnant clair sur plusieurs valeurs).

J'ai publié une solution impliquant un assemblage ARM en ligne capable de calculer à la fois le sinus et le cosinus de deux angles à la fois ici: Sinus / cosinus rapide pour ARMv7 + NEON

Une approximation précise mais rapide des fonctions 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 recherche pour les deux fonctions? Vous auriez encore à "calculer" sin (x) et cos (x), mais ce serait décidément plus rapide, si vous n'avez pas besoin d'un haut degré de précision.

Le compilateur MSVC peut utiliser les fonctions SSE2 (internes)

 ___libm_sse2_sincos_ (for x86)
 __libm_sse2_sincos_  (for x64)

dans les versions optimisées si les indicateurs de compilateur appropriés sont spécifiés (au minimum / O2 / arch: SSE2 / fp: fast). Les noms de ces fonctions semblent impliquer qu'elles ne calculent pas séparément sin et cos, mais les deux "en une seule étape".

Par exemple:

void sincos(double const x, double & s, double & c)
{
  s = std::sin(x);
  c = std::cos(x);
}

Assemblage (pour x86) avec / fp: rapide:

movsd   xmm0, QWORD PTR _x$[esp-4]
call    ___libm_sse2_sincos_
mov     eax, DWORD PTR _s$[esp-4]
movsd   QWORD PTR [eax], xmm0
mov     eax, DWORD PTR _c$[esp-4]
shufpd  xmm0, xmm0, 1
movsd   QWORD PTR [eax], xmm0
ret     0

L'assembly (pour x86) sans / fp: fast mais avec / fp: precise à la place (qui est la valeur par défaut) appelle sin et cos séparés:

movsd   xmm0, QWORD PTR _x$[esp-4]
call    __libm_sse2_sin_precise
mov     eax, DWORD PTR _s$[esp-4]
movsd   QWORD PTR [eax], xmm0
movsd   xmm0, QWORD PTR _x$[esp-4]
call    __libm_sse2_cos_precise
mov     eax, DWORD PTR _c$[esp-4]
movsd   QWORD PTR [eax], xmm0
ret     0

Donc / fp: fast est obligatoire pour l'optimisation sincos.

Mais veuillez noter que

___libm_sse2_sincos_

n'est peut-être pas aussi précis que

__libm_sse2_sin_precise
__libm_sse2_cos_precise

en raison du "précis" manquant à la fin de son nom.

Sur mon système "légèrement" plus ancien (Intel Core 2 Duo E6750) avec le dernier compilateur MSVC 2019 et les optimisations appropriées, mon point de repère montre que l'appel sincos est environ 2,4 fois plus rapide que les appels séparés sin et cos.