Geekly articles weekly

Fungsi Math.Sin (double) untuk GPU

Kata Pengantar


Saya perlu menghitung busur dengan peningkatan akurasi pada prosesor kartu video secara real time.

Penulis tidak menetapkan tujuan untuk melampaui fungsi standar System.Math.Sin () (C #) dan tidak mencapainya.

Hasil karya dan pilihan saya (bagi yang tidak mau membaca):

Sin_3 (rad)
using System; class Math_d { const double PI025 = Math.PI / 4; /// <summary> 2^17 = 131072 (1 ),   10000 ( ),  2^21 = 22097152 (16 )   +-1 ( ) (  ) </summary> const int length_mem = 22097152; const int length_mem_M1 = length_mem - 1; /// <summary>    sin,    . </summary> static double[] mem_sin; /// <summary>    cos,    . </summary> static double[] mem_cos; /// <summary>  ,   sin,    . </summary> public static void Initialise() { Ini_Mem_Sin(); Ini_Mem_Cos(); } /// <summary>       Cos,   . </summary> /// <param name="rad"></param> public static double Sin_3(double rad) { double rad_025; int i; //    //if (rad < 0) { rad = -rad + Math.PI; } i = (int)(rad / PI025); //   rad_025 = rad - PI025 * i; //     ( ) i = i & 7; //      8 //    switch (i) { case 0: return Sin_Lerp(rad_025); case 1: return Cos_Lerp(PI025 - rad_025); case 2: return Cos_Lerp(rad_025); case 3: return Sin_Lerp(PI025 - rad_025); case 4: return -Sin_Lerp(rad_025); case 5: return -Cos_Lerp(PI025 - rad_025); case 6: return -Cos_Lerp(rad_025); case 7: return -Sin_Lerp(PI025 - rad_025); } return 0; } /// <summary>   sin    </summary> static void Ini_Mem_Sin() { double rad; mem_sin = new double[length_mem]; for (int i = 0; i < length_mem; i++) { rad = (i * PI025) / length_mem_M1; mem_sin[i] = Math.Sin(rad); } } /// <summary>   cos    </summary> static void Ini_Mem_Cos() { double rad; mem_cos = new double[length_mem]; for (int i = 0; i < length_mem; i++) { rad = (i * PI025) / length_mem_M1; mem_cos[i] = Math.Cos(rad); } } /// <summary>      sin  0  pi/4. </summary> /// <param name="rad">     0  pi/4. </param> static double Sin_Lerp(double rad) { int i_0; int i_1; double i_0d; double percent; double a; double b; double s; percent = rad / PI025; i_0d = percent * length_mem_M1; i_0 = (int)i_0d; i_1 = i_0 + 1; a = mem_sin[i_0]; b = mem_sin[i_1]; s = i_0d - i_0; return Lerp(a, b, s); } /// <summary>      cos  0  pi/4. </summary> /// <param name="rad">     0  pi/4. </param> static double Cos_Lerp(double rad) { int i_0; int i_1; double i_0d; double percent; double a; double b; double s; percent = rad / PI025; i_0d = percent * length_mem_M1; i_0 = (int)i_0d; i_1 = i_0 + 1; a = mem_cos[i_0]; b = mem_cos[i_1]; s = i_0d - i_0; return Lerp(a, b, s); } /// <summary>      . (return a + s * (b - a)) </summary> /// <param name="a">  . </param> /// <param name="b">  . </param> /// <param name="s">  . 0 = a, 1 = b, 0.5 =   a  b. </param> public static double Lerp(double a, double b, double s) { return a + s * (b - a); } }


Alasan publikasi


  • Tidak ada fungsi Sin standar untuk ganda dalam bahasa HLSL (tapi ini tidak akurat)
  • Ada sedikit informasi yang tersedia di Internet tentang topik ini.

Pendekatan yang Dipertimbangkan



Parameter yang dianalisis


  • Akurasi dengan Matematika
  • Kecepatan dalam kaitannya dengan Math.Sin

Selain analisis, kami akan meningkatkan kinerja mereka.

Pangkat Taylor


Pro:

  • Presisi tertinggi
    Fungsi ini, yang digunakan untuk menghitung nilai Sin, dapat digunakan untuk menghitung nilai Sin yang akurat . Semakin banyak iterasi yang dialaminya, semakin akurat nilainya diperoleh pada output (dalam hipotesis). Dalam praktik pemrograman, ada baiknya mempertimbangkan kesalahan pembulatan perhitungan tergantung pada jenis parameter yang digunakan (ganda, float, desimal, dan lainnya).
  • Menghitung sudut mana pun
    Anda dapat memasukkan nilai apa pun sebagai argumen ke fungsi, sehingga tidak perlu memonitor parameter input.
  • Kemandirian
    Ini tidak memerlukan perhitungan pendahuluan (seperti fungsi yang dibahas di bawah), dan seringkali menjadi dasar untuk mengumpulkan fungsi yang lebih cepat.

Cons:

  • Kecepatan sangat rendah (4-10%)
    Dibutuhkan banyak iterasi untuk mendapatkan akurasi lebih dekat dengan keakuratan Math.Sin, sebagai akibatnya ia bekerja 25 kali lebih lambat dari fungsi standar.
  • Semakin besar sudut, semakin rendah akurasinya
    Semakin besar sudut yang dimasukkan dalam fungsi, semakin banyak iterasi yang dibutuhkan untuk mencapai akurasi yang sama dengan Math.

Tampilan asli (kecepatan: 4%):

Fungsi standar melibatkan menghitung faktorial, serta meningkatkan kekuatan setiap iterasi.

gambar

Dimodifikasi (kecepatan: 10%):

Perhitungan beberapa derajat dapat dikurangi dalam satu siklus (a * = aa;), dan faktor-faktor lain dapat dihitung sebelumnya dan dimasukkan ke dalam array, sementara mengubah tanda-tanda (+, -, +, ...) tidak dapat dinaikkan ke daya dan kalkulasinya juga dapat dikurangi menggunakan nilai sebelumnya.

Hasilnya adalah kode berikut:

Dosa (rad, langkah)
  // <summary>  ,    Fact </summary> static double[] fact; /// <summary>            . ///   rad,   . ///  ( Math): 4% (fps)  steps = 17 </summary> /// <param name="rad">   .      pi/4. </param> /// <param name="steps">  :  ,   .  pi/4   E-15  8. </param> public static double Sin(double rad, int steps) { double ret; double a; //,     double aa; // *  int i_f; //  int sign; // (  -  +,     = +) ret = 0; sign = -1; aa = rad * rad; a = rad; i_f = 1; //      for (int n = 0; n < steps; n++) { sign *= -1; ret += sign * a / Fact(i_f); a *= aa; i_f += 2; } return ret; } /// <summary>   (n!).  n > fact.Length,  -1. </summary> /// <param name="n"> ,     . </param> public static double Fact(int n) { if (n >= 0 && n < fact.Length) { return fact[n]; } else { Debug.Log("    . n = " + n + ",   = " + fact.Length); return -1; } } /// <summary>  . </summary> static void Init_Fact() { int steps; steps = 46; fact = new double[steps]; fact[0] = 1; for (int n = 1; n < steps; n++) { fact[n] = fact[n - 1] * n; } }


Tampilan superior (kecepatan: 19%):

Kita tahu bahwa semakin kecil sudutnya, semakin sedikit iterasi yang diperlukan. Sudut terkecil yang kita butuhkan adalah = 0,25 * PI, mis. 45 derajat. Mengingat Sin dan Cos di wilayah 45 derajat, kita bisa mendapatkan semua nilai dari -1 hingga 1 untuk Sin (di wilayah 2 * PI). Untuk melakukan ini, kami membagi lingkaran (2 * PI) menjadi 8 bagian dan untuk setiap bagian kami menunjukkan metode kami sendiri menghitung sinus. Selain itu, untuk mempercepat perhitungan, kami akan menolak untuk menggunakan fungsi memperoleh sisanya (%) (untuk mendapatkan posisi sudut di dalam zona 45 derajat):

Sin_2 (rad)
  // <summary>  ,    Fact </summary> static double[] fact; /// <summary>   Sin </summary> /// <param name="rad"></param> public static double Sin_2(double rad) { double rad_025; int i; //rad = rad % PI2; //% -   .  , fps   90  150 (  100 000   ) //rad_025 = rad % PI025; i = (int)(rad / PI025); rad_025 = rad - PI025 * i; i = i & 7; //     8  //    switch (i) { case 0: return Sin(rad_025, 8); case 1: return Cos(PI025 - rad_025, 8); case 2: return Cos(rad_025, 8); case 3: return Sin(PI025 - rad_025, 8); case 4: return -Sin(rad_025, 8); case 5: return -Cos(PI025 - rad_025, 8); case 6: return -Cos(rad_025, 8); case 7: return -Sin(PI025 - rad_025, 8); } return 0; } /// <summary>            . ///   rad,   . ///  ( Math): 10% (fps)  steps = 17 </summary> /// <param name="rad">   .      pi/4. </param> /// <param name="steps">  :  ,   .  pi/4   E-15  8. </param> public static double Sin(double rad, int steps) { double ret; double a; //,     double aa; // *  int i_f; //  int sign; // (  -  +,     = +) ret = 0; sign = -1; aa = rad * rad; a = rad; i_f = 1; //      for (int n = 0; n < steps; n++) { sign *= -1; ret += sign * a / Fact(i_f); a *= aa; i_f += 2; } return ret; } /// <summary>            . ///   rad,   . ///  ( Math): 10% (fps), 26% (test)  steps = 17 </summary> /// <param name="rad">   .      pi/4. </param> /// <param name="steps">  :  ,   .  pi/4   E-15  8. </param> public static double Cos(double rad, int steps) { double ret; double a; double aa; // *  int i_f; //  int sign; // (  -  +,     = +) ret = 0; sign = -1; aa = rad * rad; a = 1; i_f = 0; //      for (int n = 0; n < steps; n++) { sign *= -1; ret += sign * a / Fact(i_f); a *= aa; i_f += 2; } return ret; } /// <summary>   (n!).  n > fact.Length,  -1. </summary> /// <param name="n"> ,     . </param> public static double Fact(int n) { if (n >= 0 && n < fact.Length) { return fact[n]; } else { Debug.Log("    . n = " + n + ",   = " + fact.Length); return -1; } } /// <summary>  . </summary> static void Init_Fact() { int steps; steps = 46; fact = new double[steps]; fact[0] = 1; for (int n = 1; n < steps; n++) { fact[n] = fact[n - 1] * n; } }


Polinomial


Saya menemukan metode ini di Internet, penulis membutuhkan fungsi pencarian Sin cepat untuk akurasi ganda ganda (kesalahan <0,000 001) tanpa menggunakan perpustakaan nilai yang dihitung sebelumnya.

Pro:

  • Kecepatan tinggi (9-84%)
    Awalnya, polinomial yang dilempar tanpa perubahan menunjukkan kecepatan 9% dari Math.Sin asli, yang 10 kali lebih lambat. Berkat perubahan kecil, kecepatannya meningkat tajam menjadi 84%, yang tidak buruk jika Anda menutup mata untuk akurasi.
  • Tidak diperlukan perhitungan awal dan memori tambahan
    Jika di bagian atas dan lebih jauh di bawah ini kita perlu membuat array variabel untuk mempercepat perhitungan, maka di sini semua koefisien kunci dengan baik hati dihitung dan ditempatkan ke dalam formula oleh penulis sendiri dalam bentuk konstanta.
  • Akurasi lebih tinggi dari Mathf.Sin (float)
    Sebagai perbandingan:

    0.84147 1 - Mathf.Sin (1) (mesin Unity);
    0.841470984807897 - Math.Sin (1) (fungsi C # standar);
    0.8414709 56802368 - sin (1) (GPU, bahasa hlsl);
    0.84147 1184637935 - Sin_0 (1) .

Cons:

  • Tidak universal
    Anda tidak dapat menyesuaikan akurasi secara manual karena tidak diketahui alat apa yang digunakan penulis untuk menghitung polinomial ini.
  • Mengapa
    Mengapa penulis memerlukan fungsi yang tidak memerlukan array dan yang memiliki akurasi rendah (dibandingkan dengan ganda)?

Tampilan asli:

Sin_1 (x)
 /// <summary>  ( Math): 9% (fps)</summary> /// <param name="x">     -2*Pi  2*Pi </param> public static double Sin_1(double x) { return 0.9999997192673006 * x - 0.1666657564532464 * Math.Pow(x, 3) + 0.008332803647181511 * Math.Pow(x, 5) - 0.00019830197237204295 * Math.Pow(x, 7) + 2.7444305061093514e-6 * Math.Pow(x, 9) - 2.442176561869478e-8 * Math.Pow(x, 11) + 1.407555708887347e-10 * Math.Pow(x, 13) - 4.240664814288337e-13 * Math.Pow(x, 15); }


Tampilan superior:

Sin_0 (rad)
 /// <summary>  ( Math): 83% (fps)</summary> /// <param name="rad">     -2*Pi  2*Pi </param> public static double Sin_0(double rad) { double x; double xx; double ret; xx = rad * rad; x = rad; //1 ret = 0.9999997192673006 * x; x *= xx; //3 ret -= 0.1666657564532464 * x; x *= xx; //5 ret += 0.008332803647181511 * x; x *= xx; //7 ret -= 0.00019830197237204295 * x; x *= xx; //9 ret += 2.7444305061093514e-6 * x; x *= xx; //11 ret -= 2.442176561869478e-8 * x; x *= xx; //13 ret += 1.407555708887347e-10 * x; x *= xx; //15 ret -= 4.240664814288337e-13 * x; return ret; }


Interpolasi linier


Metode ini didasarkan pada interpolasi linier antara hasil dua catatan dalam sebuah array.
Entri dibagi menjadi mem_sin dan mem_cos, mereka berisi hasil yang dihitung sebelumnya dari fungsi standar Math.Sin dan Math.Cos pada segmen parameter input dari 0 hingga 0,25 * PI.

Prinsip manipulasi dengan sudut dari 0 hingga 45 derajat tidak berbeda dari versi yang ditingkatkan dari seri Taylor, tetapi pada saat yang sama suatu fungsi disebut yang menemukan - di mana dua catatan ada sudut - dan menemukan nilai di antara mereka.

Pro:

  • Kecepatan tinggi (65%)
    Karena kesederhanaan dari algoritma interpolasi, kecepatan mencapai 65% dari kecepatan Math.Sin. Saya pikir kecepatan> 33% memuaskan.
  • Presisi tertinggi
    Contoh penolakan yang jarang:
    0.255835595715180 - Math.Sin;
    0.2558355957151 79 - Sin_3 .
  • Kaki cepat
    Saya suka fungsi ini karena ia lahir dalam penderitaan, ditulis oleh saya dan melampaui persyaratan: kecepatan> 33%, akurasi di atas 1e-14. Saya akan memberinya nama bangga - VΔ“lōx Pes.

Cons:

  • Itu membutuhkan tempat di memori
    Untuk bekerja, Anda harus terlebih dahulu menghitung dua array: untuk dosa dan untuk cos; setiap array memiliki berat ~ 16mb (16 * 2 = 32mb)

Tampilan asli:

Sin_3 (rad)
 class Math_d { const double PI025 = Math.PI / 4; /// <summary> 2^17 = 131072 (1 ),   10000 ( ),  2^21 = 22097152 (16 )   +-1 ( ) (  ) </summary> const int length_mem = 22097152; const int length_mem_M1 = length_mem - 1; /// <summary>    sin,    . </summary> static double[] mem_sin; /// <summary>    cos,    . </summary> static double[] mem_cos; /// <summary>  ,   sin,    . </summary> public static void Initialise() { Ini_Mem_Sin(); Ini_Mem_Cos(); } /// <summary>       Cos,   . </summary> /// <param name="rad"></param> public static double Sin_3(double rad) { double rad_025; int i; //    //if (rad < 0) { rad = -rad + Math.PI; } i = (int)(rad / PI025); //   rad_025 = rad - PI025 * i; //     ( ) i = i & 7; //      8 //    switch (i) { case 0: return Sin_Lerp(rad_025); case 1: return Cos_Lerp(PI025 - rad_025); case 2: return Cos_Lerp(rad_025); case 3: return Sin_Lerp(PI025 - rad_025); case 4: return -Sin_Lerp(rad_025); case 5: return -Cos_Lerp(PI025 - rad_025); case 6: return -Cos_Lerp(rad_025); case 7: return -Sin_Lerp(PI025 - rad_025); } return 0; } /// <summary>   sin    </summary> static void Ini_Mem_Sin() { double rad; mem_sin = new double[length_mem]; for (int i = 0; i < length_mem; i++) { rad = (i * PI025) / length_mem_M1; mem_sin[i] = Math.Sin(rad); } } /// <summary>   cos    </summary> static void Ini_Mem_Cos() { double rad; mem_cos = new double[length_mem]; for (int i = 0; i < length_mem; i++) { rad = (i * PI025) / length_mem_M1; mem_cos[i] = Math.Cos(rad); } } /// <summary>      sin  0  pi/4. </summary> /// <param name="rad">     0  pi/4. </param> static double Sin_Lerp(double rad) { int i_0; int i_1; double i_0d; double percent; double a; double b; double s; percent = rad / PI025; i_0d = percent * length_mem_M1; i_0 = (int)i_0d; i_1 = i_0 + 1; a = mem_sin[i_0]; b = mem_sin[i_1]; s = i_0d - i_0; return Lerp(a, b, s); } /// <summary>      cos  0  pi/4. </summary> /// <param name="rad">     0  pi/4. </param> static double Cos_Lerp(double rad) { int i_0; int i_1; double i_0d; double percent; double a; double b; double s; percent = rad / PI025; i_0d = percent * length_mem_M1; i_0 = (int)i_0d; i_1 = i_0 + 1; a = mem_cos[i_0]; b = mem_cos[i_1]; s = i_0d - i_0; return Lerp(a, b, s); } /// <summary>      . (return a + s * (b - a)) </summary> /// <param name="a">  . </param> /// <param name="b">  . </param> /// <param name="s">  . 0 = a, 1 = b, 0.5 =   a  b. </param> public static double Lerp(double a, double b, double s) { return a + s * (b - a); } }



UPD: Memperbaiki kesalahan dalam menentukan indeks di Sin_Lerp (), Cos_Lerp (), Ini_Mem_Sin () dan Ini_Mem_Cos ().

Source: https://habr.com/ru/post/id426355/

More articles:


All Articles