¿Una buena manera de hacer una división rápida en C++?

Question

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

// 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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 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.

Answer 5

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)

Answer 6

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.

Answer 7

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.)

Answer 8

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.

Answer 9

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.

Answer 10

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); 

Answer 11

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.