La estimación de la raíz cuadrada
https://stackoverflow.com/questions/3722975
-
03-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy escribiendo una aplicación de iPhone que las necesidades para el cálculo de la raíz cuadrada de un número aproximadamente 2000 veces cada 1/30 de un segundo. sqrt () funciona bien en un equipo, pero la velocidad de fotogramas se reduce a alrededor de 10 FPS en un iPhone o iPad, y ya he optimizado el resto del código. He oído que esto se puede acelerar drásticamente mediante la estimación de la raíz cuadrada, pero no puedo encontrar ningún código para hacer esto. Sólo necesito uno o dos decimales de precisión. ¿Alguna sugerencia sobre cómo hacer esto, u otras formas de acelerar las cosas serían apreciadas.
Gracias!
Solución
¿Qué tan preciso desea que su estimación sea? Si usted sabe lo cerca que quiere que su estimación se hará a la raíz cuadrada real de la de Newton Método es su amigo.
¿Conoce el rango de valores que se pasan a la raíz cuadrada? Si es así usted puede hacer una tabla de consulta que se precalculados en el arranque (o incluso leer desde el disco en el arranque en función de lo que resulta ser más rápido). Encontrar el más cercano en la tabla a su entrada y obtener su estimación.
Otros consejos
A menos que realmente necesidad la raíz cuadrada, comparar los valores al cuadrado en lugar de los valores brutos y la raíz cuadrada.
La cuadratura es mucho más rápido (y más precisa) de tomar una raíz cuadrada, si sólo necesita comparaciones. Esta es la forma en la mayoría de los juegos lo hacen.
¿Conoce el rango de valores que usted está tratando de encontrar la raíz cuadrada de? Digamos que tiene valores que van de 0 a 10. A continuación, puede precalcular una matriz:
sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10
A continuación, durante el tiempo de ejecución se toma el número que desea que la raíz cuadrada de, converso que a un entero (así por ejemplo 3.123 convierte 3) y usar eso como un índice (3) para buscar el valor previamente calculado.
Por supuesto, si desea una resolución más fina que puede simplemente aumentar el número de elementos en la matriz.
En primer lugar, ¿está seguro de que la raíz cuadrada es en realidad el cuello de botella? ¿Ha perfilado? 2000 raíces cuadradas cada 1/30 de una segunda realidad no es todo lo que muchos, incluso en un teléfono celular. La documentación ARM cita a 33 ciclos para una raíz cuadrada de precisión simple y 60 ciclos para de doble precisión; un procesador de 600 MHz puede hacer 10 millones raíces cuadradas por segundo (más si la instrucción está segmentado en absoluto).
Si ha perfilado, y la raíz cuadrada de verdad es el cuello de botella, tendrá que utilizar la instrucción NEON vrsqrte.f32. Esta instrucción es bastante rápido y le da las raíces cuadradas recíprocos aproximados de cuatro números de punto flotante de forma simultánea. A continuación, puede utilizar la instrucción vmul.f32 para obtener raíces cuadradas aproximadas (aunque para muchos usos el recíproco es más útil que la raíz cuadrada en sí).
Tal vez esto es para ti:
rápida inversa raíz cuadrada
Si este método no proporciona la precisión que necesita también hay un montón de otros métodos iterativos donde se puede elegir más o menos precisa entre la velocidad y la precisión:
cálculo de la raíz cuadrada
El cambio más fácil que usted puede hacer en un iPhone es utilizar sqrtf () en lugar de sqrt (). Matemáticas de precisión única flotante es mucho más rápido que el de doble precisión, especialmente en los dispositivos de la vendimia 3GS y más nuevo.
Si necesita la raíz cuadrada para calcular un triángulo de Pitágoras (sqrt (x * x + y * y)), y ambos X e Y son no negativos, entonces una forma muy rápida aproximación a esto es
max(x,y) + min(x,y)*0.333
Esto tiene un error máximo de 5,7%. Cuidado con predicción errónea rama en min () y max () sin embargo.
Una rápida búsqueda de Google vueltas todo tipo de enlaces.
Si usted tiene un flotador positiva "normal" o doble, no un int, y desea utilizar un método de consulta de tabla, puede hacer dos planos mirada tabla separados, uno para el exponente (re-sesgada), y una para unos pocos bits de la mantisa (desplazamiento y la máscara de extracción campo de bits), y luego se multiplica el aspecto de dos mesa hasta resultados juntos.
