Kemungkinan besar, Anda tahu rasio berikut dari sekolah:

$$

$$\ sin (\ alpha + \ beta) = \ sin \ alpha \ kali \ cos \ beta + \ cos \ alpha \ kali \ sin \ beta \\ \ cos (\ alpha + \ beta) = \ cos \ alpha \ kali \ cos \ beta - \ sin \ alpha \ kali \ sin \ beta$$

Ketika Anda pertama kali berkenalan dengan formula ini di masa kecil, kemungkinan besar, perasaan pertama Anda adalah rasa sakit karena fakta bahwa formula ini harus diingat. Ini sangat buruk, karena sebenarnya Anda tidak perlu mengingat rumus ini - rumus ini ditampilkan ketika Anda memutar segitiga di atas kertas. Bahkan, saya melakukan hal yang sama ketika saya menulis rumus ini. Penafsiran ini akan terlihat pada pertengahan artikel ini. Tapi sekarang, untuk meninggalkan semua kesenangan untuk nanti dan untuk menunda saat ketika Anda mengatakan "Eureka!", Mari kita pikirkan mengapa kita harus memikirkan formula ini.

Entri

Fungsi trigonometrik sin() dan cos() mungkin yang paling populer dalam grafik komputer, karena mereka adalah dasar untuk menggambarkan setiap bentuk bundar dengan cara parametrik. Di antara tempat-tempat aplikasi yang memungkinkan mereka adalah generasi lingkaran atau objek volumetrik revolusi, ketika menghitung transformasi Fourier, generasi prosedural gelombang di bidang air, generator untuk synthesizer suara perangkat lunak, dan sebagainya. Dalam semua kasus ini, sin() dan cos() disebut di dalam loop, seperti di sini:

 for(int n=0; n < num; n++) { const float t = 2.0f*PI*(float)n/(float)num; const float s = sinf(t); const float c = cosf(t); // do something with s and c ... } 

Kita mulai menulis ulang siklus secara bertahap (lihat kode di bawah), sehingga lebih mudah bagi kita untuk membayangkan bahwa pada iterasi n siklus ini dengan fase t , iterasi berikutnya, n+1 , akan mempertimbangkan sin() dan cos() untuk t+f . Dengan kata lain, sin(t) dan cos(t) dihitung untuk kita dan kita perlu menghitung sin(t+f) dan cos(t+f) :

 const float f = 2.0f*PI/(float)num; const float t = 0.0f; for( int n=0; n < num; n++ ) { const float s = sinf(t); const float c = cosf(t); // do something with s and c ... t += f; } 

Tidak masalah bagaimana kita mendapatkan t dan berapa kisaran nilainya (dalam contoh di atas - $$$[0; 2 \ pi]$) Satu-satunya hal yang mengganggu kita adalah bahwa ada loop yang terus-menerus memanggil sin() dan cos() dengan parameter yang meningkat pada langkah-langkah konstan (dalam hal ini, $$$\ frac {2 \ pi} {\ text {num}}$) Artikel ini adalah tentang bagaimana mengoptimalkan kode ini untuk kecepatan sedemikian rupa sehingga perhitungan yang sama dapat dilakukan sama sekali tanpa menggunakan fungsi sin() atau cos() (dalam loop batin), dan bahkan fungsi sincos() lebih cepat.

Tetapi jika Anda melihat formula pertama dalam artikel, kita akan melihat bahwa jika $$$f = \ alpha$dan $$$t = \ beta$kita dapat menulis ulang ini sebagai

 sin(t+f) = sin(f)*cos(t) + cos(f)*sin(t) cos(t+f) = cos(f)*cos(t) - sin(f)*sin(t) 

atau dengan kata lain

 new_s = sin(f)*old_c + cos(f)*old_s new_c = cos(f)*old_c - sin(f)*old_s 

Karena f adalah konstanta, sin(f) dan cos(f) juga. Sebut masing-masing a dan b :

 new_s = b*old_c + a*old_s new_c = a*old_c - b*old_s 

Ungkapan ini dapat langsung digunakan dalam kode kita, dan kemudian kita mendapatkan loop di mana fungsi trigonometri yang mahal (dan memang tidak ada) disebut!

 const float f = 2.0f*PI/(float)num; const float a = cosf(f); const float b = sinf(f); float s = 0.0f; float c = 1.0f; for( int n=0; n < num; n++ ) { // do something with s and c ... const float ns = b*c + a*s; const float nc = a*c - b*s; c = nc; s = ns; } 

Interpretasi

Sejauh ini, kami bermain buta dengan matematika, tidak memahami apa yang sebenarnya terjadi. Mari kita menulis ulang loop batin seperti ini:

$$

$$s_ {n + 1} = s_na + c_nb \\ c_ {n + 1} = c_na - s_nb$$

Beberapa dari Anda mungkin telah memperhatikan bahwa ini adalah rumus untuk memutar objek dalam ruang dua dimensi. Jika Anda masih tidak mengerti ini, mungkin bentuk matriks akan membantu Anda.

$$

$$\ left (\ begin {matrix} s_ {n + 1} \\ c_ {n + 1} \ end {matrix} \ kanan) = \ left (\ begin {matrix} a & b \\ -b & a \ end {matrix} \ kanan) \ cdot \ kiri (\ begin {matrix} s_ {n} \\ c_ {n} \ end {matrix} \ kanan)$$

Bahkan, sin(t) dan cos(t) dapat dikelompokkan menjadi vektor dengan panjang 1 dan ditarik sebagai titik di layar. Sebut vektor ini x . Lalu $$$x = \ {\ sin \ beta, \ cos \ beta \}$ . Jadi bentuk vektor ekspresi adalah $$$x_ {n + 1} = Rx_n$dimana $$$R = \ kiri (\ begin {matrix} a & b \\ - b & a \ end {matrix} \ kanan)$ . Kita melihat bahwa loop kita melakukan rotasi dua dimensi kecil setiap iterasi sehingga x berputar dalam lingkaran selama pelaksanaan siklus. Setiap iterasi x dirotasi oleh $$$\ frac {2 \ pi} {\ text {num}}$radian.
Jadi pada dasarnya

$$

$$\ sin (\ alpha + \ beta) = \ sin \ alpha \ kali \ cos \ beta + \ cos \ alpha \ kali \ sin \ beta \\ \ cos (\ alpha + \ beta) = \ cos \ alpha \ kali \ cos \ beta - \ sin \ alpha \ kali \ sin \ beta$$

ini adalah rumus titik gerak $$$x = \ {\ cos \ alpha, \ sin \ alpha \}$ keliling dalam kelipatan $$$\ beta$radian. Untuk melakukan ini, kita akan membangun satu dari dua sumbu rotasi, misalnya, $$$u = \ {\ cos \ beta, \ sin \ beta \}$ . Komponen pertama dari rotasi adalah proyeksi. $$$x$pada $$$u$. Sejak $$$x$dan $$$u$dinormalisasi (memiliki panjang 1), proyeksi adalah produk skalar mereka. Oleh karena itu $$$s = x \ cdot u = \ sin \ alpha \ cdot \ cos \ beta + \ cos \ alpha \ cdot \ sin \ beta$, dan tentu saja komponen kedua adalah anti-proyeksi, yang dapat ditemukan dengan memproyeksikan ke sumbu tegak lurus, $$$v$. Kita dapat membuat vektor ini dengan memperluas koordinat $$$u$dan ubah tanda ke kebalikan pada koordinat pertama: $$$c = x \ cdot v = \ cos \ alpha \ cdot \ cos \ beta + \ sin \ alpha \ cdot \ sin \ beta$

Catatan

Biasanya Anda harus dapat melakukan rotasi kecil ini berulang-ulang. Sebenarnya $$$| R | = \ kiri | \ mulai {matrix} a & b \\ - b & a \ end {matrix} \ kanan | = a ^ 2 + b ^ 2 = \ sin ^ 2 \ alpha + \ cos ^ 2 \ alpha = 1$ , yang artinya matriks $$$R$tidak menambah atau mengurangi ruang di mana ia diterapkan, yang berarti itu $$$x$akan bergerak dalam lingkaran yang sempurna. Namun, karena komputer tidak akurat, $$$x$akan bergerak secara spiral dan akhirnya bertepatan dengan pusat lingkaran rotasi. Saya tidak memiliki masalah seperti itu, tetapi saya pikir mereka dapat terjadi dengan jumlah yang sangat besar, yaitu sudut belok kecil.

Contoh

Dalam Kindercrasher , demo 4096-byte dari 2008 (tangkapan layar pada KDPV), sekelompok bola berdenyut ke musik. Untuk ini, saya menghitung transformasi suara Fourier. Ada algoritma yang melakukan ini secara real time, misalnya, FFT . Namun, kode saya harus muat dalam beberapa kilobyte, dan saya memutuskan untuk pergi ke arah lain. Alih-alih menerapkan FFT, saya menulis DFT dengan definisi yang sederhana. Anda dapat memeriksanya di wikipedia.

$$

$$X_k = \ sum_ {n = 0} ^ {N-1} {x_ne ^ {- \ frac {2 \ pi i} {N} kn}} \ quad k = 0,1, \ ldots, N-1$$

Fungsi saya juga mengambil buffer audio stereo 16-bit, x , dan mengembalikan 128 frekuensi pertama dari spektrum suara y . Lihat bagaimana loop dalam diatur, yang berjalan 4096 kali: bukan satu panggilan ke fungsi sin() atau cos() , meskipun dalam implementasi lain panggilan ini akan menjadi.

 #include <math.h> void iqDFT12( float *y, const short *x ) { for( int i=0; i<128; i++ ) { const float wi = (float)i*(2.0f*3.1415927f/4096.0f); const float sii = sinf( wi ); const float coi = cosf( wi ); float co = 1.0f; float si = 0.0f; float acco = 0.0f; float acsi = 0.0f; for( int j=0; j<4096; j++ ) { const float f = (float)(x[2*j+0]+x[2*j+1]); const float oco = co; acco += co*f; co = co*coi - si*sii; acsi += si*f; si = si*coi + oco*sii; } y[i] = sqrtf(acco*acco+acsi*acsi)*(1.0f/32767.0f); } }