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

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 twiddling de drapeaux 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 elle 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 de compilateur et de bibliothèque utilisés. Cela pourrait (et pourrait) prendre plus de temps pour le faire de cette façon (juste parce que la formule D'Euler est principalement utilisée pour calculer le complexe exp en utilisant sin et cos - et pas l'inverse) mais il pourrait y avoir un peu de théorie optimisation possible.

Modifier

Les en-têtes de <complex> pour GNU C++ 4.2 utilisent des calculs explicites de sin et cos à l'intérieur de polar, donc cela ne semble pas trop bon pour les optimisations sauf si le compilateur fait de la magie (voir les commutateurs -ffast-math et -mfpmath comme é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, alors vous pouvez faire:

#define _GNU_SOURCE
#include <math.h>

Et vous obtiendrez des déclarations du sincos(), sincosf() et sincosl() fonctions 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 caf l'indique, ont déjà sincos (). L'exception notable est MSVC.

• Sun a sincos () depuis au moins 1987 (vingt-trois ans; j'ai une page de manuel sur 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 élément intégré dans gcc 3.4 (2004), __builtin_sincos ().

Et en ce qui concerne 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 de précalculer de petites tables-par exemple, une table de sin (x) par degré pour optimiser les rotations dans un moteur graphique 3D prendre 365 × 4 octets sur une machine moderne. Avant que les processeurs aient assez plus rapide que la mémoire pour exiger la mise en cache, c'était une vitesse évidente optimisation. De nos jours il peut être plus rapide de recalculer à chaque fois plutôt que de payer pour le pourcentage de erreurs de cache causées par le table.

" mais à l'avenir, cela pourrait se retourner à mesure que les caches grossissent. Plus généralement, de nombreuses optimisations sont temporaires et peuvent facilement tourner dans les pessimisations à mesure que les ratios de coûts changent. La seule façon de savoir est de mesurer et voir."(de l'Art de la programmation Unix )

Mais, à en juger par 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 se concentre sur la recherche de bonnes approximations qui sont rapides: http://www.devmaster.net/forums/showthread.php?t=5784

Avertissement: pas utilisé tout ce genre de choses moi-même.

Mise à jour 22 février 2018: Wayback Machine est la seule façon de visiter la page d'origine maintenant: https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate-sine-cosine

Je ne crois pas que les tables de recherche soient nécessairement une bonne idée pour ce problème. Sauf si vos exigences de précision sont très faibles, la table doit être très grande. Et les processeurs modernes peuvent faire beaucoup de calcul 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 argument (pas même le mien), tester et mesurer et considérer les données.

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

Si vous êtes prêt à utiliser un produit commercial, et calculez un certain nombre de calculs sin/cos en même temps (de sorte que vous pouvez utiliser des fonctions vectorisées), vous devriez consulter la Bibliothèque du noyau Math D'Intel.

Il est un sincos fonction

Selon cette documentation, il est en moyenne 13.08 horloges / élément sur core 2 duo 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 critiques pour ce genre de chose, il n'est pas inhabituel d'introduire une table de recherche.

Pour une approche créative, que diriez-vous d'é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: en commençant par x et 1 pour le péché et le cosinus, suivez le modèle - soustrayez x^2 / 2! du cosinus, soustrayez x^3 / 3! de sinus, ajouter x^4 / 4! pour cosinus, ajouter x^5 / 5! siné...

Je n'ai aucune idée si ce serait performant. Si vous avez besoin de moins de précision que les sin() et cos intégrés() vous donner, il peut être une option.

Il y a une bonne solution dans la bibliothèque CEPHES qui peut être assez rapide et vous pouvez ajouter / supprimer 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é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 comprises entre 0 et 2pi. Nous décalons x à l'intervalle [0, 2pi). Ensuite, nous sélectionnons le y le plus proche de x et écrivons
exp(ix)=exp(iy+(ix-iy))=exp(iy)exp(i(x-y)).

Nous obtenons exp(iy) de la table de recherche. Et puisque |x-y| est petit (au plus la moitié de la distance entre les valeurs y), la série de Taylor convergera bien en quelques termes, donc nous l'utilisons pour exp (i(x-y)). Et puis 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 jeter un oeil à 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 maximum de sin / cos de l'ordre de 5e-8) et la vitesse (légèrement surclasse fsincos sur une base d'appel unique, et un gagnant clair sur plusieurs valeurs).

J'ai posté une solution impliquant un assemblage de bras 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 de la fonction sin et cos simultanément, en javascript, peut être trouvée ici: http://danisraelmalta.github.io/Fmath/ (facilement importé en C / C++)

Avez-vous pensé à déclarer des tables de recherche pour les deux fonctions? Vous devrez toujours "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.