Algoritmo matemático más rápido sacrificando la precisión

Question

Estoy desarrollando un juego que requiere tantas funciones matemáticas para la física y el renderizado. "Fast inverse sqrt" utilizado en Quake3 es conocido por ser más rápido que sqrt() y su fondo es hermoso.

¿Conoces algún otro algoritmo que sea más rápido de lo normal con una pérdida de precisión aceptable?

Answer 1

Estos algoritmos se denominan "algoritmos de aproximación" en la literatura. El libro estándar con muchos ejemplos es Approximation Algorithms by Vijay V. Vazirani.

El caso de sin x ~~ x es un caso especial de algo un poco más general: mira el Taylor series (o serie de Fourier en el caso de funciones periódicas) de tu función y calcula solo los primeros términos.

Otra técnica (algo brutal) es ensamblar aleatoriamente algunos puntos de su función y luego ejecutar una regresión lineal en su contra. De esta forma, también puedes obtener un buen polinomio que describa tu función :).

Answer 2

para las pequeñas x: sin (x) = x ~ es uno que se utiliza a menudo en la física

Answer 3

Cualquier cosa probabilístico suele ser así. Ejecutar una simulación 10 veces será más rápido, pero dará resultados menos precisos que ejecutar una simulación 1000 veces.

Answer 4

Niko tiene algunas buenas sugerencias a las que añadiría la tabla de búsqueda antigua.

He utilizado una tabla de búsqueda para funciones circulares (sin/cos/tan) con éxito muchas veces en systesm de alto rendimiento en tiempo real. El sqrt() es más difícil de esta manera, pero si su rango de entrada está restringido (por ejemplo, los píxeles de la pantalla) es difícil de superar la velocidad, y puede ajustar el intercambio de espacio/exactitud exactamente. También puede utilizar la búsqueda de un rango común, y luego tener una repercusión en una función framework sqrt() para el caso raro.

Paul

Answer 5

Cualquier función continua (que incluye las operaciones matemáticas más comunes) puede ser bien aproximada durante un intervalo acotado por un polinomio. Esto, junto con identidades relativamente simples que generalmente satisfacen las funciones matemáticas comunes (como leyes de adición) y tablas, proporciona la base de las técnicas estándar para construir algoritmos de aproximación rápida (y también la base de métodos de alta precisión como los utilizados en el sistema matemático biblioteca).

Las series de Taylor son generalmente una opción pobre, sin embargo; Los polinomios Chebyshev o Minimax tienen características de error mucho mejores para la mayoría de los usos computacionales. La técnica estándar para el ajuste de polinomios minimax es usar el algoritmo de Remes, que se implementa en una gran cantidad de software matemático comercial, o puede implementar su propia implementación con un día de trabajo si sabe lo que está haciendo.

Para el registro, la "rápida inversa de la raíz cuadrada" se debe evitar en los procesadores modernos, ya que es sustancialmente más rápido usar una instrucción de cálculo de la raíz cuadrada recíproca de punto flotante (rsqrtss/rsqrtps en SSE, vrsqrte de neón, vrsqrtefp en AltiVec). Incluso la raíz cuadrada de hardware (no aproximada) es bastante rápida en los procesadores Intel actuales.

Answer 6

A partir del código fuente de Doom, para la distancia aproximada entre dos puntos 2D sin tener que utilizar sqrt() o funciones trigonométricas:

fixed_t P_AproxDistance(fixed_t dx, fixed_t dy) 
{ 
    dx = abs(dx); 
    dy = abs(dy); 
    if (dx < dy) 
     return dx+dy-(dx>>1); 
    else 
     return dx+dy-(dy>>1); 
} 

Tenga en cuenta que x >> 1 es la misma que x/2 pero ligeramente más rápido - buenos compiladores modernos hacer esto automáticamente hoy en día, pero en aquel entonces no eran tan buenos.