2009-05-22 21 views
10

A veces veo y he usado la siguiente variación para una división rápida en C++ con números de coma flotante.¿Una buena manera de hacer una división rápida en C++?

// orig loop 
double y = 44100.0; 
for(int i=0; i<10000; ++i) { 
double z = x/y; 
} 

// alternative 
double y = 44100; 
double y_div = 1.0/y; 

for(int i=0; i<10000; ++i) { 
double z = x * y_div; 
} 

Pero alguien insinuó recientemente que esta podría no ser la manera más precisa.

¿Alguna idea?

+0

¿eh? Esto no tiene sentido como está escrito. – mwigdahl

+0

¿Se puede borrar un poco este ejemplo de código? – BobbyShaftoe

+0

dado que el cuerpo del bucle no usa "i", ¿por qué no eliminar el bucle por completo? – lothar

Respuesta

17

En casi todas las CPU, una división de punto flotante es varias veces más costosa que una flotante multiplique el punto, por lo que multiplicar por el inverso de su divisor es una buena optimización. La desventaja es que existe la posibilidad de perder muy pequeña porción de precisión en ciertos procesadores; por ejemplo, en los procesadores x86 modernos, las operaciones de flotación de 64 bits se calculan internamente utilizando 80 bits cuando se usa el modo FPU predeterminado. y almacenarlo en una variable hará que esos bits de precisión extra se trunquen de acuerdo con su modo de redondeo FPU (que por defecto es el más cercano). Esto solo importa si concatenas muchas operaciones de flotación y tienes que preocuparte por la acumulación de errores.

+0

"almacenarlo en una variable causará" - ¿está garantizado que causa eso, o se permite que los compiladores lleven valores dobles como se representa en la FPU cuando sea posible? También es probable que puedas utilizar el doble largo si te preocupa el redondeo. –

+0

No estoy 100% seguro, pero depende del código exacto.La pila de registro de FPU x87 contiene los 80 bits completos por valor, por lo que si el compilador puede mantener el valor del divisor inverso intermedio en la pila de registros de FPU, entonces no se debe perder ninguna precisión. Sin embargo, el compilador puede no ser capaz de mantener ese valor en una pila de registros FPU y tendrá que almacenarlo en la pila de programas, en cuyo punto la precisión se truncará a 64 bits. Sin embargo, si eso es una preocupación, el ensamblaje debería estar codificado a mano, en lugar de dejarlo en manos del compilador. –

+0

FWIW: los procesadores de la serie m68k tenían códigos de operación para almacenar, recuperar y manipular flotadores de 80 bits. Cuesta algo de velocidad. – dmckee

1

la multiplicación es más rápida que la división, por lo que el segundo método es más rápido. Puede ser un poco menos preciso, pero a menos que esté haciendo hard core numerics, el nivel de precisión debería ser más que suficiente.

+0

Gracias, estoy haciendo un procesamiento de audio de alta calidad donde la precisión es importante. –

7

Wikipedia acepta que esto puede ser más rápido. El artículo vinculado también contiene varios otros algoritmos de división rápida que pueden ser de interés.

Supongo que cualquier compilador moderno de fortaleza industrial hará esa optimización para usted si le va a sacar provecho en absoluto.

+3

Los compiladores de potencia industrial no harán optimizaciones como esa, si pueden cambiar la salida del programa; después de todo, una optimización que da la respuesta incorrecta es una optimización deficiente. Debido a que no tenemos un mecanismo de nivel de idioma para especificar la precisión que * nos importa *, el compilador solo puede asumir que nos preocupamos por todo. – Tom

4

El original

// original loop: 
double y = 44100.0; 

for(int i=0; i<10000; ++i) { 
    double z = x/y; 
} 

fácilmente se pueden optimizar para

// haha: 
double y = 44100.0; 
double z = x/y; 

y el rendimiento es bastante agradable. ;-)

EDIT: La gente sigue votando esto abajo, así que aquí está la versión no tan divertida:

Si hubiera una manera general para que la división más rápido para todos los casos, ¿no crees que los autores de compiladores podría haber sucedido sobre esto ahora? Por supuesto que lo habrían hecho. Además, algunas de las personas que hacen circuitos de FPU tampoco son exactamente estúpidas.

Por lo tanto, la única manera de obtener un mejor rendimiento es conocer la situación específica que tiene a mano y utilizar un código óptimo para eso. Lo más probable es que esto sea una pérdida total de tiempo, porque su programa es lento por alguna otra razón, como realizar operaciones matemáticas en invariantes de bucle. Ve a buscar un mejor algoritmo en su lugar.

+0

guau que es una optimización increíble. entonces, obviamente, estaba haciendo pseudo código y x variaría con el tiempo. –

+1

Eso no está bien, 'z' no se puede ver fuera del alcance del bucle ... :-P –

+0

el humor es bueno y todo, pero estoy seguro de que obtendrás algunas excelentes respuestas aquí además de mi respuesta de broma. – dwc

0

Estoy girando 10.000 veces simplemente para hacer que el código tarde lo suficiente para medir el tiempo fácilmente? ¿O tienes 10000 números para dividir por el mismo número? Si el primero, pon el "y_div = 1.0/y;" dentro de el ciclo, porque es parte de la operación.

Si la última, sí, la multiplicación de punto flotante es generalmente más rápida que la división. Sin embargo, no cambie su código de lo obvio a lo arcano en base a suposiciones. El punto de referencia primero para encontrar puntos lentos y luego optimizarlos (y tomar medidas antes y después para asegurarse de que su idea realmente causa una mejora)

+0

El objetivo de hacerlo fuera del bucle es que solo tiene que hacerlo una vez: la multiplicación por el recíproco es (aparte de los errores de coma flotante) equivalente a la división. –

-1

En viejos CPUs como el 80286, matemáticas de punto flotante era abismalmente lentos y se empleó mucha astucia para acelerar las cosas.

En modernas matemáticas de punto flotante CPU es tan rápidos y compiladores de optimización puede hacer maravillas en general, con las cosas de ajuste.

Es casi nunca vale la pena el esfuerzo para emplear pequeñas micro-optimizaciones por el estilo.

tratar de hacer su código y sencilla a prueba de idiotas. Solo ustedes encontrarán un cuello de botella real (usando un generador de perfiles), pensarían en optimizaciones en sus cálculos de coma flotante.

+0

En las CPU modernas como Core2 Duo, las matemáticas de coma flotante aún requieren un tiempo no nulo y, por lo tanto, aún vale la pena optimizarlas para problemas vinculados a la CPU. – Tom

+0

La pregunta era sobre la pérdida de precisión. OP funciona obviamente en un software de audio (44100 Hz), y cuando hace que cualquier software de procesamiento de señal digital, como el que solía trabajar, sea de 2 a 10 veces más rápido, entonces todas las llamadas micro optimizaciones no solo valen la pena, pero son críticos – Jem

+2

A menos que hayas perfilado el código que no sabes si tienes un cuello de botella. Si está haciendo millones de cálculos, debe considerar cómo accede a sus datos. Al optimizar esto, a menudo puede evitar fallas de página que son probablemente mucho más lentas que los cálculos. Aún mejor es si puede mejorar su algoritmo para reducir el número de cálculos. Probablemente pueda encontrar casos donde cambiar "divide" a "multiplicar" mejora el rendimiento, pero serán bastante raros. Su principal preocupación es escribir un código de mantenimiento, y los pequeños trucos no son su amigo cuando lo hace. –

2

Audio, hunh? No son solo 44.100 divisiones por segundo cuando tiene, por ejemplo, cinco pistas de audio ejecutándose a la vez. Incluso un fader simple consume ciclos, después de todo. Y eso es solo para un ejemplo bastante básico, mínimo: ¿y si quieres tener, digamos, una ecuación y un compresor? Tal vez un poco de reverberación? Su presupuesto total de matemáticas, por así decirlo, se consume rápidamente. Es tiene tener sentido para escurrir un poco de rendimiento extra en esos casos.

Los perfiladores son buenos. Los perfiladores son tus amigos. Los perfiladores merecen mamadas y pudin. Pero ya sabes dónde está el cuello de la botella principal en el trabajo de audio: está en el ciclo que procesa muestras, y cuanto más rápido puedas hacer eso, más felices serán tus usuarios. Usa todo lo que puedas! Multiplicar recíprocas, desplazar bits siempre que sea posible (exp (x * y) = exp (x) * exp (y), después de todo), usar tablas de búsqueda, referirse a variables por referencia en lugar de valores (menos empujar/hacer estallar en la pila), términos de refactorización, etc. (Si eres bueno, te reirás de estas optimizaciones elementales.)

0

Supongo desde la publicación original que x no es una constante que se muestra allí, pero probablemente datos de una matriz así que x [i] es probable que sea la fuente de los datos y de manera similar para la salida, se almacenará en algún lugar de la memoria.

Sugiero que si el recuento de bucles es realmente 10.000 como en la publicación original, no tendrá mucha importancia utilizarlo, ya que el bucle entero no tomará una fracción de milisegundo en una CPU moderna. Si el recuento de bucles es realmente mucho mayor, tal vez 1,000,000 o más, entonces esperaría que el costo del acceso a la memoria probablemente haga que la operación más rápida sea completamente irrelevante, ya que siempre estará esperando los datos de todos modos.

Sugiero probar ambos con su código y probar si realmente hace una diferencia significativa en el tiempo de ejecución y si no lo hace, simplemente escriba la división directa si eso es lo que el algoritmo necesita.

2

En su ejemplo usando gcc la división con las opciones -O3 -ffast-math produce el mismo código que la multiplicación sin -ffast-math. (En un entorno de prueba con elementos volátiles suficientes, el ciclo sigue allí).

Por lo tanto, si realmente desea optimizar esas divisiones y no le importan las consecuencias, ese es el camino a seguir. La multiplicación parece ser aproximadamente 15 veces más rápida, por cierto.

1

Al procesar el audio, yo prefiero usar las matemáticas de punto fijo en su lugar. Supongo que esto depende del nivel de precisión que necesita. Pero, supongamos que 16.16 enteros de punto fijo lo harán (lo que significa 16 bits altos es número entero, 16 bajo es la fracción).Ahora, todos los cálculos se puede hacer tan simple matemáticas número entero:

unsigned int y = 44100 << 16; 
unsigned int z = x/(y >> 16); // divisor must be the whole number portion 

O con macros para ayudar:

#define FP_INT(x) (x << 16) 
#define FP_MUL(x, y) (x * (y >> 16)) 
#define FP_DIV(x, y) (x/(y >> 16)) 

unsigned int y = FP_INT(44100); 
unsigned int z = FP_MUL(x, y); 
0

aquí es el problema de hacerlo con un recíproco, que todavía tiene que hacer la división antes en realidad puedes dividir por Y. a menos que solo dividas por Y entonces supongo que esto puede ser útil. esto no es muy práctico ya que la división se realiza en binario con algoritmos similares.

+0

No del todo. Una operación de división es 20-44 ciclos de reloj en mi CPU de puente arenoso. Un multiplicar es 5 ciclos de reloj, y recíproco es 5 ciclos de reloj, pero es menos preciso que la división verdadera. Por lo tanto, x * (1/y) puede ser 2-5 veces más rápido que la división verdadera a la pérdida de algunos decimales. – Stefan

Cuestiones relacionadas