Jaki jest najszybszy sposób obliczenia razem grzechu i cos?

Chciałbym obliczyć zarówno sinus, jak i współsinus wartości razem (na przykład, aby utworzyć macierz rotacji). Oczywiście mógłbym je obliczyć osobno, jeden po drugim, npa = cos(x); b = sin(x); , ale zastanawiam się, czy istnieje szybszy sposób, gdy potrzebuję obu wartości.

Edycja: podsumowanie dotychczasowych odpowiedzi:

• Vlad powiedział, że istnieje polecenie asmFSINCOSobliczające oba z nich (prawie w tym samym czasie, co wywołanieFSINsamego)

• Jak zauważył Chi , ta optymalizacja jest czasami już wykonywana przez kompilator (przy użyciu flag optymalizacji).

• caf wskazał, że działasincosisincosfprawdopodobnie są dostępne i można je wywołać bezpośrednio, po prostu włączającmath.h

• Podejście Tanasciusa do korzystania z tabeli przeglądowej jest dyskutowane jako kontrowersyjne. (Jednak na moim komputerze iw scenariuszu porównawczym działa 3x szybciej niżsincosz prawie taką samą dokładnością dla 32-bitowych liczb zmiennoprzecinkowych).

• Joel Goodwin połączył się z ciekawym podejściem do ekstremalnie szybkiej techniki przybliżania z całkiem dobrą dokładnością (dla mnie jest to nawet szybsze niż przeglądanie tabeli)

Nowoczesne procesory Intel / AMD mają instrukcje FSINCOS do jednoczesnego obliczania funkcji sinus i cosinus. Jeśli potrzebujesz silnej optymalizacji, być może powinieneś jej użyć.

Oto mały przykład: http://home.broadpark.no/~alein/fsincos.html

Oto kolejny przykład (dla MSVC): http://www.codeguru.com/forum/showthread.php?t=328669

Oto kolejny przykład (z gcc): http://www.allegro.cc/forums/thread/588470

Mam nadzieję, że jeden z nich pomoże. (Sam nie skorzystałem z tej instrukcji, przepraszam.)

Ponieważ są obsługiwane na poziomie procesora, spodziewam się, że będą znacznie szybsze niż przeszukiwanie tabeli.

Edycja:
Wikipedia to sugerujeFSINCOS została dodana na 387 procesorach, więc trudno jest znaleźć procesor, który go nie obsługuje.

Edycja:
dokumentacja Intela stwierdza, że FSINCOSjest to tylko około 5 razy wolniejsze niż FDIV(tj. Dzielenie zmiennoprzecinkowe).

Edycja:
Należy pamiętać, że nie wszystkie współczesne kompilatory optymalizują obliczenia sinusa i cosinusa w wywołaniu funkcjiFSINCOS . W szczególności mój VS 2008 nie robił tego w ten sposób.

Edycja:
pierwszy link do przykładu jest martwy, ale nadal istnieje wersja w Wayback Machine .

Nowoczesne procesory x86 mają instrukcję fsincos, która zrobi dokładnie to, o co prosisz - oblicza sin i cos w tym samym czasie. Dobry kompilator optymalizujący powinien wykryć kod, który oblicza sin i cos dla tej samej wartości i użyć polecenia fsincos, aby to wykonać.

Aby to zadziałało, trzeba było trochę zmienić flagi kompilatora, ale:

$ 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, używa instrukcji fsincos!

Kiedy potrzebujesz wydajności, możesz użyć wstępnie obliczonej tabeli sin / cos (wystarczy jedna tabela, przechowywana jako słownik). Cóż, zależy to od potrzebnej dokładności (być może stół byłby za duży), ale powinien być naprawdę szybki.

Technicznie rzecz biorąc, osiągnąłbyś to używając liczb zespolonych i wzoru Eulera . Tak więc coś w stylu (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();

powinien dać ci sinus i cosinus w jednym kroku. Jak to się robi wewnętrznie, jest kwestią używanego kompilatora i biblioteki. Zrobienie tego w ten sposób mogłoby (i mogłoby) zająć więcej czasu (tylko dlatego, że formuła Eulera jest głównie używana do obliczania złożonego expprzy użyciu sini cos- a nie na odwrót), ale może być możliwa pewna teoretyczna optymalizacja.

Edytować

Nagłówki w <complex>GNU C ++ 4.2 używają jawnych obliczeń sini coswewnątrz polar, więc nie wygląda to zbyt dobrze do optymalizacji, chyba że kompilator zrobi trochę magii (zobacz przełączniki -ffast-mathi -mfpmathtak, jak napisano w odpowiedzi Chi ).

Możesz obliczyć jedną z nich, a następnie użyć tożsamości:

cos (x) 2 = 1 - sin (x) 2

ale jak mówi @tanascius, najlepszym rozwiązaniem jest tabela obliczona wcześniej.

Jeśli używasz biblioteki GNU C, możesz:

#define _GNU_SOURCE
#include <math.h>

a dostaniesz oświadczeń o sincos(), sincosf()i sincosl()funkcje, które obliczają obie wartości razem - przypuszczalnie w najszybszy sposób do architektury docelowej.

Na tej stronie forum jest bardzo interesująca rzecz, która koncentruje się na wyszukiwaniu dobrych i szybkich przybliżeń: http://www.devmaster.net/forums/showthread.php?t=5784

Zastrzeżenie: Sam nie używałem żadnych z tych rzeczy.

Aktualizacja z 22 lutego 2018 r .: Wayback Machine to jedyny sposób, aby teraz odwiedzić oryginalną stronę: https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate- sinus-cosinus

Wiele bibliotek matematycznych języka C, jak wskazuje caf, ma już sincos (). Godnym uwagi wyjątkiem jest MSVC.

• Sun ma sincos () od co najmniej 1987 (dwadzieścia trzy lata; mam papierową stronę podręcznika)
• HPUX 11 miał go w 1997 roku (ale nie ma go w HPUX 10.20)
• Dodano do glibc w wersji 2.1 (luty 1999)
• Stał się wbudowany w gcc 3.4 (2004), __builtin_sincos ().

A jeśli chodzi o wyszukiwanie, Eric S. Raymond w Art of Unix Programming (2004) (rozdział 12) mówi wyraźnie, że to zły pomysł (w chwili obecnej):

„Innym przykładem jest wstępne obliczanie małych tabel - na przykład tabela sin (x) na stopień do optymalizacji obrotów w silniku grafiki 3D zajmie 365 × 4 bajty na nowoczesnej maszynie. Zanim procesory osiągną wystarczająco dużo szybkości niż pamięć, aby wymagać buforowania była to oczywista optymalizacja szybkości. Obecnie może być szybsze przeliczanie za każdym razem, niż płacenie za procent dodatkowych błędów pamięci podręcznej spowodowanych przez tabelę.

„Ale w przyszłości sytuacja może się powtórzyć, gdy pamięci podręczne będą się powiększać. Ogólnie rzecz biorąc, wiele optymalizacji ma charakter tymczasowy i może łatwo przekształcić się w pesymizację, gdy zmieniają się wskaźniki kosztów. Jedynym sposobem na poznanie jest mierzenie i oglądanie”. (z Art of Unix Programming )

Ale sądząc po powyższej dyskusji, nie wszyscy się zgadzają.

Nie wierzę, że tabele przeglądowe są koniecznie dobrym pomysłem na ten problem. O ile wymagania dotyczące dokładności nie są bardzo niskie, stół musi być bardzo duży. Nowoczesne procesory mogą wykonywać wiele obliczeń, podczas gdy wartość jest pobierana z pamięci głównej. Nie jest to jedno z tych pytań, na które można właściwie odpowiedzieć argumentacją (nawet moją), przetestować, zmierzyć i rozważyć dane.

Spojrzałbym jednak na szybkie implementacje SinCos, które można znaleźć w bibliotekach, takich jak ACML AMD i MKL Intela.

Jeśli chcesz korzystać z produktu komercyjnego i obliczasz jednocześnie kilka obliczeń sin / cos (abyś mógł używać funkcji wektorowych), powinieneś sprawdzić bibliotekę jąder matematycznych firmy Intel.

Posiada funkcję SinCos

Zgodnie z tą dokumentacją uśrednia on 13,08 zegarów / element na rdzeniu 2 duo w trybie wysokiej dokładności, co, jak sądzę, będzie nawet szybsze niż fsincos.

W tym artykule pokazano, jak skonstruować algorytm paraboliczny, który generuje zarówno sinus, jak i cosinus:

DSP Trick: Równoczesne paraboliczne przybliżenie sinusa i cos

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

Gdy wydajność ma kluczowe znaczenie dla tego rodzaju rzeczy, wprowadzenie tabeli przeglądowej nie jest niczym niezwykłym.

Jeśli chodzi o kreatywne podejście, co powiesz na rozszerzenie serii Taylor? Ponieważ mają podobne terminy, możesz zrobić coś podobnego do następującego pseudo:

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
}

Oznacza to, że robisz coś takiego: zaczynając od x i 1 dla sin i cosinus, postępuj zgodnie ze wzorem - odejmij x ^ 2/2! od cosinusa odejmij x ^ 3/3! od sinusa dodaj x ^ 4/4! do cosinusa dodaj x ^ 5/5! sine ...

Nie mam pojęcia, czy to byłoby skuteczne. Jeśli potrzebujesz mniejszej precyzji niż dają ci wbudowane funkcje sin () i cos (), może to być opcja.

W bibliotece CEPHES jest fajne rozwiązanie, które może być dość szybkie i możesz dodawać / usuwać dokładność dość elastycznie, aby uzyskać nieco więcej / mniej czasu procesora.

Pamiętaj, że cos (x) i sin (x) to rzeczywiste i urojone części exp (ix). Chcemy więc obliczyć exp (ix), aby uzyskać oba. Obliczamy wstępnie exp (iy) dla niektórych dyskretnych wartości y między 0 a 2pi. Przesuwamy x do przedziału [0, 2pi). Następnie wybieramy y, które jest najbliższe x i piszemy
exp (ix) = exp (iy + (ix-iy)) = exp (iy) exp (i (xy)).

Otrzymujemy exp (iy) z tabeli przeglądowej. A ponieważ | xy | jest mała (co najwyżej połowa odległości między wartościami y), szereg Taylora będzie się dobrze zbiegał w zaledwie kilku terminach, więc używamy tego dla exp (i (xy)). A potem potrzebujemy złożonego mnożenia, aby otrzymać exp (ix).

Inną fajną właściwością tego jest to, że możesz go wektoryzować za pomocą SSE.

Możesz zajrzeć na http://gruntthepeon.free.fr/ssemath/ , który oferuje wektoryzowaną implementację SSE inspirowaną biblioteką CEPHES. Ma dobrą dokładność (maksymalne odchylenie od sin / cos rzędu 5e-8) i prędkość (nieznacznie przewyższa fsincos na podstawie pojedynczego wywołania i wyraźny zwycięzca w wielu wartościach).

Opublikowałem tutaj rozwiązanie obejmujące montaż inline ARM zdolny do obliczania zarówno sinusa, jak i cosinusa dwóch kątów naraz: Szybki sinus / cosinus dla ARMv7 + NEON

Dokładne, ale szybkie przybliżenie funkcji sin i cos jednocześnie, w javascript, można znaleźć tutaj: http://danisraelmalta.github.io/Fmath/ (łatwe importowanie do c / c ++)

Czy myślałeś o zadeklarowaniu tabel przeglądowych dla tych dwóch funkcji? Nadal musiałbyś „obliczyć” sin (x) i cos (x), ale byłoby to zdecydowanie szybsze, gdybyś nie potrzebował wysokiego stopnia dokładności.

Kompilator MSVC może używać (wewnętrznych) funkcji SSE2

 ___libm_sse2_sincos_ (for x86)
 __libm_sse2_sincos_  (for x64)

w zoptymalizowanych kompilacjach, jeśli określono odpowiednie flagi kompilatora (co najmniej / O2 / arch: SSE2 / fp: fast). Nazwy tych funkcji zdają się sugerować, że nie obliczają one oddzielnych wartości sin i cos, ale obie „w jednym kroku”.

Na przykład:

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

Montaż (dla x86) z / fp: szybki:

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

Assembly (dla x86) bez / fp: fast, ale z / fp: precyzyjne zamiast tego (co jest domyślne) wywołuje oddzielne sin i cos:

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

So / fp: fast jest obowiązkowe dla optymalizacji sincos.

Ale proszę o tym pamiętać

___libm_sse2_sincos_

może nie jest tak dokładny jak

__libm_sse2_sin_precise
__libm_sse2_cos_precise

ze względu na brak słowa „precyzyjne” na końcu jego nazwy.

Na moim "nieco" starszym systemie (Intel Core 2 Duo E6750) z najnowszym kompilatorem MSVC 2019 i odpowiednimi optymalizacjami mój test porównawczy pokazuje, że wywołanie sincos jest około 2,4 razy szybsze niż oddzielne wywołania sin i cos.