Apa cara tercepat untuk menghitung dosa dan cos bersama-sama?

Saya ingin menghitung sinus dan co-sinus dari suatu nilai bersama-sama (misalnya untuk membuat matriks rotasi). Tentu saja saya dapat menghitungnya secara terpisah satu demi satu seperti a = cos(x); b = sin(x);, tetapi saya bertanya-tanya apakah ada cara yang lebih cepat ketika membutuhkan kedua nilai tersebut.

Edit: Untuk meringkas jawaban sejauh ini:

• Vlad berkata, bahwa ada perintah asm yangFSINCOSmenghitung keduanya (dalam waktu yang hampir bersamaan dengan panggilan untukFSINsendiri)

• Seperti yang diperhatikan Chi , pengoptimalan ini terkadang sudah dilakukan oleh compiler (saat menggunakan flag pengoptimalan).

• caf menunjukkan, bahwa fungsisincosdansincosfmungkin tersedia dan dapat dipanggil langsung dengan hanya memasukkanmath.h

• Pendekatan tanascius menggunakan tabel look-up dibahas kontroversial. (Namun di komputer saya dan dalam skenario benchmark, ini berjalan 3x lebih cepat daripadasincosdengan akurasi yang hampir sama untuk floating point 32-bit.)

• Joel Goodwin ditautkan ke pendekatan menarik dari teknik pendekatan yang sangat cepat dengan akurasi yang cukup baik (bagi saya, ini bahkan lebih cepat daripada pencarian tabel)

Prosesor Intel / AMD modern memiliki instruksi FSINCOSuntuk menghitung fungsi sinus dan kosinus secara bersamaan. Jika Anda membutuhkan pengoptimalan yang kuat, mungkin Anda harus menggunakannya.

Berikut adalah contoh kecilnya: http://home.broadpark.no/~alein/fsincos.html

Berikut adalah contoh lain (untuk MSVC): http://www.codeguru.com/forum/showthread.php?t=328669

Berikut adalah contoh lain (dengan gcc): http://www.allegro.cc/forums/thread/588470

Semoga salah satu dari mereka membantu. (Saya tidak menggunakan instruksi ini sendiri, maaf.)

Karena mereka didukung pada tingkat prosesor, saya berharap mereka jauh lebih cepat daripada pencarian tabel.

Sunting:
Wikipedia menyarankan FSINCOSitu ditambahkan pada prosesor 387, sehingga Anda hampir tidak dapat menemukan prosesor yang tidak mendukungnya.

Edit:
Dokumentasi Intel menyatakan bahwa FSINCOShanya sekitar 5 kali lebih lambat daripada FDIV(yaitu, pembagian floating point).

Edit:
Perlu diketahui bahwa tidak semua penyusun modern mengoptimalkan kalkulasi sinus dan cosinus menjadi panggilan ke FSINCOS. Secara khusus, VS 2008 saya tidak melakukannya seperti itu.

Sunting:
Tautan contoh pertama sudah mati, tetapi masih ada versi di Mesin Wayback .

Prosesor x86 modern memiliki instruksi fsincos yang akan melakukan apa yang Anda minta - hitung sin dan cos pada saat yang bersamaan. Kompiler pengoptimalan yang baik harus mendeteksi kode yang menghitung sin dan cos untuk nilai yang sama dan menggunakan perintah fsincos untuk menjalankannya.

Butuh beberapa twiddling dari flag compiler untuk bekerja, tapi:

$ 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, ini menggunakan instruksi fsincos!

Ketika Anda membutuhkan kinerja, Anda dapat menggunakan tabel sin / cos yang telah dihitung sebelumnya (satu tabel akan dilakukan, disimpan sebagai Kamus). Yah, itu tergantung pada akurasi yang Anda butuhkan (mungkin tabelnya akan terlalu besar), tetapi itu harus sangat cepat.

Secara teknis, Anda akan mencapai ini dengan menggunakan bilangan kompleks dan Rumus Euler . Jadi, sesuatu seperti (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();

harus memberi Anda sinus dan cosinus dalam satu langkah. Bagaimana ini dilakukan secara internal adalah pertanyaan tentang kompilator dan pustaka yang digunakan. Ini bisa (dan mungkin) membutuhkan waktu lebih lama untuk melakukannya dengan cara ini (hanya karena Formula Euler sebagian besar digunakan untuk menghitung kompleks expmenggunakan sindan cos- dan bukan sebaliknya) tetapi mungkin ada beberapa optimasi teoritis yang mungkin.

Edit

Header di <complex>untuk GNU C ++ 4.2 menggunakan kalkulasi eksplisit sindan cosdi dalamnya polar, sehingga tidak terlihat terlalu bagus untuk pengoptimalan di sana kecuali jika kompilator melakukan sihir (lihat -ffast-mathdan -mfpmathberalih seperti yang tertulis dalam jawaban Chi ).

Anda dapat menghitung salah satunya dan kemudian menggunakan identitas:

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

tetapi seperti yang dikatakan @tanascius, tabel yang telah dihitung sebelumnya adalah cara yang tepat.

Jika Anda menggunakan perpustakaan GNU C, maka Anda dapat melakukan:

#define _GNU_SOURCE
#include <math.h>

dan Anda akan mendapatkan deklarasi sincos(), sincosf()dan sincosl()fungsi yang menghitung kedua nilai bersama - mungkin dengan cara tercepat untuk arsitektur target Anda.

Ada hal yang sangat menarik di halaman forum ini, yang difokuskan untuk menemukan perkiraan yang baik dan cepat: http://www.devmaster.net/forums/showthread.php?t=5784

Penafian: Saya sendiri tidak menggunakan barang ini.

Pembaruan 22 Feb 2018: Wayback Machine adalah satu-satunya cara untuk mengunjungi halaman asli sekarang: https://web.archive.org/web/20130927121234/http://devmaster.net/posts/9648/fast-and-accurate- sinus-kosinus

Banyak perpustakaan matematika C, seperti yang ditunjukkan oleh caf, sudah memiliki sincos (). Pengecualian penting adalah MSVC.

• Sun telah memiliki sincos () setidaknya sejak 1987 (dua puluh tiga tahun; saya memiliki halaman manual hard copy)
• HPUX 11 memilikinya pada tahun 1997 (tetapi tidak ada di HPUX 10.20)
• Ditambahkan ke glibc pada versi 2.1 (Feb 1999)
• Menjadi bawaan di gcc 3.4 (2004), __builtin_sincos ().

Dan mengenai pencarian, Eric S.Raymond dalam Art of Unix Programming (2004) (Bab 12) secara eksplisit mengatakan ini Ide Buruk (pada saat ini dalam waktu):

"Contoh lain adalah prakomputasi tabel kecil - misalnya, tabel sin (x) menurut derajat untuk mengoptimalkan rotasi dalam mesin grafis 3D akan membutuhkan 365 × 4 byte pada mesin modern. Sebelumnya prosesor mendapatkan cukup waktu lebih cepat daripada memori untuk menuntut penyimpanan dalam cache , ini jelas merupakan pengoptimalan kecepatan. Saat ini, mungkin lebih cepat untuk menghitung ulang setiap kali daripada membayar persentase cache tambahan yang hilang yang disebabkan oleh tabel.

"Namun di masa mendatang, ini mungkin berbalik lagi karena cache tumbuh lebih besar. Secara lebih umum, banyak pengoptimalan bersifat sementara dan dapat dengan mudah berubah menjadi pesimisasi saat rasio biaya berubah. Satu-satunya cara untuk mengetahuinya adalah dengan mengukur dan melihat." (dari Seni Pemrograman Unix )

Tapi, dilihat dari pembahasan di atas, tidak semua orang setuju.

Saya tidak percaya bahwa tabel pencarian merupakan ide bagus untuk masalah ini. Kecuali jika persyaratan akurasi Anda sangat rendah, tabel harus berukuran sangat besar. Dan CPU modern dapat melakukan banyak komputasi saat sebuah nilai diambil dari memori utama. Ini bukan salah satu pertanyaan yang dapat dijawab dengan benar dengan argumen (bahkan bukan milik saya), menguji dan mengukur dan mempertimbangkan data.

Tapi saya akan melihat implementasi cepat SinCos yang Anda temukan di perpustakaan seperti ACML AMD dan MKL Intel.

Jika Anda ingin menggunakan produk komersial, dan menghitung jumlah penghitungan sin / cos pada saat yang sama (sehingga Anda dapat menggunakan fungsi vektor), Anda harus memeriksa Pustaka Kernel Matematika Intel.

Ini memiliki fungsi sincos

Menurut dokumentasi itu, rata-rata 13.08 jam / elemen pada inti 2 duo dalam mode akurasi tinggi, yang menurut saya akan lebih cepat daripada fsincos.

Artikel ini menunjukkan cara membangun algoritme parabola yang menghasilkan sinus dan kosinus:

Trik DSP: Pendekatan Parabola Simultan dari Sin dan Cos

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

Ketika kinerja sangat penting untuk hal semacam ini, bukan hal yang aneh untuk memperkenalkan tabel pencarian.

Untuk pendekatan kreatif, bagaimana dengan memperluas seri Taylor? Karena mereka memiliki istilah yang mirip, Anda dapat melakukan sesuatu seperti berikut ini:

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
}

Ini berarti Anda melakukan sesuatu seperti ini: mulai dari x dan 1 untuk sin dan cosinus, ikuti polanya - kurangi x ^ 2/2! dari cosinus, kurangi x ^ 3/3! dari sinus, tambahkan x ^ 4/4! ke kosinus, tambahkan x ^ 5/5! untuk sinus ...

Saya tidak tahu apakah ini akan menjadi performant. Jika Anda membutuhkan presisi yang kurang dari yang diberikan oleh sin () dan cos (), ini bisa menjadi pilihan.

Ada solusi bagus di pustaka CEPHES yang bisa sangat cepat dan Anda dapat menambah / menghapus akurasi dengan cukup fleksibel untuk waktu CPU yang lebih banyak / lebih sedikit.

Ingatlah bahwa cos (x) dan sin (x) adalah bagian nyata dan imajiner dari exp (ix). Jadi kami ingin menghitung exp (ix) untuk mendapatkan keduanya. Kami menghitung sebelumnya exp (iy) untuk beberapa nilai diskrit y antara 0 dan 2pi. Kami menggeser x ke interval [0, 2pi). Kemudian kami memilih y yang paling dekat dengan x dan menulis
exp (ix) = exp (iy + (ix-iy)) = exp (iy) exp (i (xy)).

Kami mendapatkan exp (iy) dari tabel pencarian. Dan sejak | xy | kecil (paling banyak setengah jarak antara nilai y), deret Taylor akan bertemu dengan baik hanya dalam beberapa suku, jadi kami menggunakannya untuk exp (i (xy)). Dan kemudian kita hanya perlu perkalian kompleks untuk mendapatkan exp (ix).

Properti bagus lainnya dari ini adalah Anda dapat melakukan vektorisasi menggunakan SSE.

Anda mungkin ingin melihat http://gruntthepeon.free.fr/ssemath/ , yang menawarkan implementasi vektorisasi SSE yang terinspirasi dari pustaka CEPHES. Ini memiliki akurasi yang baik (deviasi maksimum dari sin / cos pada urutan 5e-8) dan kecepatan (sedikit mengungguli fsincos pada basis panggilan tunggal, dan pemenang yang jelas atas beberapa nilai).

Saya telah memposting solusi yang melibatkan perakitan ARM inline yang mampu menghitung sinus dan cosinus dari dua sudut sekaligus di sini: Sinus / cosinus cepat untuk ARMv7 + NEON

Perkiraan yang akurat namun cepat dari fungsi sin dan cos secara bersamaan, dalam javascript, dapat ditemukan di sini: http://danisraelmalta.github.io/Fmath/ (diimpor dengan mudah ke c / c ++)

Pernahkah Anda berpikir untuk mendeklarasikan tabel pencarian untuk dua fungsi? Anda masih harus "menghitung" sin (x) dan cos (x), tetapi ini akan menjadi lebih cepat, jika Anda tidak membutuhkan tingkat akurasi yang tinggi.

Kompilator MSVC dapat menggunakan fungsi SSE2 (internal)

 ___libm_sse2_sincos_ (for x86)
 __libm_sse2_sincos_  (for x64)

dalam build yang dioptimalkan jika flag compiler yang sesuai ditentukan (minimal / O2 / arch: SSE2 / fp: fast). Nama-nama fungsi ini sepertinya menyiratkan bahwa mereka tidak menghitung sin dan cos yang terpisah, tetapi keduanya "dalam satu langkah".

Sebagai contoh:

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

Majelis (untuk x86) dengan / fp: fast:

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

Majelis (untuk x86) tanpa / fp: cepat tetapi dengan / fp: tepat sebagai gantinya (yang merupakan default) memanggil sin dan cos terpisah:

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 adalah wajib untuk optimasi sincos.

Tapi harap dicatat itu

___libm_sse2_sincos_

mungkin tidak seakurat

__libm_sse2_sin_precise
__libm_sse2_cos_precise

karena "tepat" yang hilang di akhir namanya.

Pada sistem saya yang "sedikit" lebih tua (Intel Core 2 Duo E6750) dengan kompiler MSVC 2019 terbaru dan pengoptimalan yang sesuai, tolok ukur saya menunjukkan bahwa panggilan sincos sekitar 2,4 kali lebih cepat daripada panggilan sin dan cos yang terpisah.