Prefácio
Eu precisava calcular o arco com maior precisão no processador da placa de vídeo em tempo real.
O autor não estabeleceu uma meta para superar a função padrão System.Math.Sin () (C #) e não a alcançou.
O resultado do trabalho e minha escolha (para quem não quer ler):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); } }
Razões para publicação
- Não há função Sin padrão para duplicar na linguagem HLSL (mas isso não é exato)
- Há pouca informação disponível na Internet sobre esse tópico.
Abordagens Consideradas
Os parâmetros analisados
- Precisão com Math.Sin
- Velocidade em relação ao Math.Sin
Além da análise, melhoraremos seu desempenho.Taylor classifica
Prós:
Maior precisãoEsta função, usada para calcular o valor do pecado, pode ser usada para calcular o valor do pecado infinitamente preciso . Quanto mais iterações forem realizadas, mais precisamente o valor será obtido na saída (em uma hipótese). Na prática de programação, vale a pena considerar erros de arredondamento dos cálculos, dependendo dos tipos de parâmetros usados (duplo, flutuante, decimal e outros).
Calcula qualquer ânguloVocê pode inserir qualquer valor como argumento para a função, portanto, não há necessidade de monitorar os parâmetros de entrada.
IndependênciaEle não requer cálculos preliminares (como as funções discutidas abaixo) e é frequentemente a base na qual as funções mais rápidas são montadas.
Contras:
Velocidade muito baixa (4-10%)São necessárias muitas iterações para obter a precisão mais próxima da precisão do Math.Sin e, como resultado, funciona 25 vezes mais lento que a função padrão.
Quanto maior o ângulo, menor a precisãoQuanto maior o ângulo inserido na função, mais iterações são necessárias para obter a mesma precisão do Math.Sin.
Aparência original (velocidade: 4%):A função padrão envolve o cálculo de fatoriais, além de aumentar a potência a cada iteração.
Modificado (velocidade: 10%):O cálculo de alguns graus pode ser reduzido em um ciclo (a * = aa;), e outros fatoriais podem ser pré-calculados e colocados em uma matriz, enquanto a alteração dos sinais (+, -, +, ...) não pode ser aumentada para uma potência e seu cálculo também pode ser reduzido usando os valores anteriores.
O resultado é o seguinte código:
Sin (rad, passos) // <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; } }
Vista superior (velocidade: 19%):Sabemos que quanto menor o ângulo, menos iterações são necessárias. O menor ângulo que precisamos é = 0,25 * PI, ou seja, 45 graus. Considerando Sin e Cos na região de 45 graus, podemos obter todos os valores de -1 a 1 para Sin (na região de 2 * PI). Para fazer isso, dividimos o círculo (2 * PI) em 8 partes e, para cada parte, indicamos nosso próprio método de cálculo do seno. Além disso, para acelerar o cálculo, recusaremos usar a função de obter o restante (%) (para obter a posição do ângulo dentro da zona de 45 graus):
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; } }
Polinômios
Me deparei com esse método na Internet, o autor precisava de uma função de pesquisa rápida do Sin para o dobro de baixa precisão (erro <0,000 001) sem usar bibliotecas de valores pré-calculados.
Prós:
Alta velocidade (9-84%)Inicialmente, o polinômio lançado sem alterações mostrou uma velocidade de 9% do Math.Sin original, que é 10 vezes mais lento. Graças a pequenas alterações, a velocidade aumenta acentuadamente para 84%, o que não é ruim se você fechar os olhos com precisão.
Não são necessários cálculos preliminares adicionais nem memóriaSe, no topo e mais abaixo, precisamos compor matrizes de variáveis para acelerar os cálculos, então todos os coeficientes-chave foram gentilmente calculados e colocados na fórmula pelo próprio autor na forma de constantes.
Precisão maior que Mathf.Sin (flutuante)Para comparação:
0,84147 1 - Mathf.Sin (1) (mecanismo Unity);
0,841470984807897 - Math.Sin (1) (função C # padrão);
0,8414709 56802368 - sin (1) (GPU, idioma hlsl);
0,84147 1184637935 - Sin_0 (1) .
Contras:
Não universalVocê não pode ajustar a precisão manualmente, porque não se sabe quais ferramentas o autor usou para calcular esse polinômio.
PorquePor que o autor precisava de uma função que não requer matrizes e que tenha uma precisão tão baixa (comparada à dupla)?
Visualização original: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); }
Vista 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; }
Interpolação linear
Este método é baseado na interpolação linear entre os resultados de dois registros em uma matriz.
As entradas são divididas em mem_sin e mem_cos, elas contêm os resultados pré-calculados da função padrão Math.Sin e Math.Cos em um segmento de parâmetros de entrada de 0 a 0,25 * PI.
O princípio das manipulações com um ângulo de 0 a 45 graus não difere da versão aprimorada da série Taylor, mas ao mesmo tempo é chamada uma função que encontra - entre os quais dois registros existe um ângulo - e encontra um valor entre eles.
Prós:
Alta velocidade (65%)Devido à simplicidade do algoritmo de interpolação, a velocidade atinge 65% da velocidade do Math.Sin. Eu acho que a velocidade> 33% é satisfatória.
Maior precisãoUm exemplo de um caso raro de rejeição:
0,255835595715180 - Math.Sin;
0.2558355957151 79 - Sin_3 .
Pé rápidoAdoro essa função porque nasceu em agonia, escrita por mim e excedeu os requisitos: velocidade> 33%, precisão acima de 1e-14. Vou dar a ela um nome orgulhoso - Vēlōx Pes.
Contras:
Requer um lugar na memóriaPara trabalhar, você deve primeiro calcular duas matrizes: para sin e para cos; cada matriz pesa ~ 16mb (16 * 2 = 32mb)
Visualização original: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: Corrigido erro na determinação do índice em Sin_Lerp (), Cos_Lerp (), Ini_Mem_Sin () e Ini_Mem_Cos ().