c++ - reciprocos - qué es un número recíproco

División rápida 1/X(recíproco)

Question

¿Hay alguna manera de mejorar la reciprocidad (división 1 sobre X) con respecto a la velocidad, si la precisión no es crucial?

Por lo tanto, tengo que calcular 1 / X. ¿Hay alguna solución alternativa, así que pierdo precisión pero lo hago más rápido?

Answer 1

Creo que lo que buscaba es una forma más eficiente de aproximarse a 1.0 / x en lugar de alguna definición técnica de aproximación que establezca que se podría usar 1 como una respuesta muy impactante. También creo que esto satisface eso.

__inline__ double __attribute__((const)) reciprocal( unsigned long long x ) {
    //The type is unsigned long long, but you are restricted to a max value of 2^32-1, not
    // 2^64-1 like the unsigned long long is capable of storing
    union {
        double dbl;
        unsigned long long ull;
    } u = {.dbl=(x*=x)};        // x*x = pow( x, 2 )
    u.ull = ( 0xbfcdd6a18f6a6f52ULL - u.ull ) >> (unsigned char)1;
                                // pow( pow(x,2), -0.5 ) = pow( x, -1 ) = 1.0 / x
                                // This is done via the ''fast'' inverse square root trick
    return u.dbl;
}

__inline__ double __attribute__((const)) reciprocal( double x ) {
    union {
        double dbl;
        unsigned long long ull;
    } u;
    u.dbl = x;
    u.ull = ( 0xbfcdd6a18f6a6f52ULL - u.ull ) >> (unsigned char)1;
                                    // pow( x, -0.5 )
    u.dbl *= u.dbl;                 // pow( pow(x,-0.5), 2 ) = pow( x, -1 ) = 1.0 / x
    return u.dbl;
}

__inline__ float __attribute__((const)) reciprocal( float x ) {
    union {
        float dbl;
        unsigned uint;
    } u;
    u.dbl = x;
    u.uint = ( 0xbe6eb3beU - u.uint ) >> (unsigned char)1;
                                    // pow( x, -0.5 )
    u.dbl *= u.dbl;                 // pow( pow(x,-0.5), 2 ) = pow( x, -1 ) = 1.0 / x
    return u.dbl;
}

Hmm ....... Me sorprendería si los fabricantes de CPU supieran que podría obtener el recíproco con solo una sola multiplicación, resta y cambio de bits cuando diseñaron la CPU ... hmm ........ .

En cuanto a la marca de referencia, las instrucciones de hardware x ² combinadas con las instrucciones de sustracción de hardware son tan rápidas como las instrucciones de hardware 1.0 / x en las computadoras de hoy en día (mis puntos de referencia estaban en un Intel i7, pero asumiría resultados similares para otros procesadores) . Sin embargo, si este algoritmo se implementara en el hardware como una nueva instrucción de ensamblaje, entonces el aumento de la velocidad probablemente sería lo suficientemente bueno para que esta instrucción sea bastante práctica.

Para obtener más información sobre este método, esta implementación se basa en el maravilloso algoritmo de raíz cuadrada inversa "rápido" .

Por último, tenga en cuenta que soy más novato en C ++. Como tal, doy la bienvenida con los brazos abiertos a cualquier edición de las mejores prácticas, el formato correcto o la claridad implícita hasta el fin de mejorar la calidad de esta respuesta para todos los que la lean.

Answer 2

En primer lugar, si activa las optimizaciones del compilador, es probable que el compilador optimice el cálculo si es posible (por ejemplo, para sacarlo de un bucle). Para ver esta optimización, necesita compilar y ejecutar en modo Release.

La división puede ser más pesada que la multiplicación (pero un comentarista señaló que los recíprocos son tan rápidos como la multiplicación en las CPU modernas, en cuyo caso, esto no es correcto para su caso), así que si tiene 1/X aparece en algún lugar dentro de un bucle (y más de una vez), puede ayudar almacenando en caché el resultado dentro del bucle ( float Y = 1.0f/X; ) y luego utilizando Y (La optimización del compilador podría hacer esto en cualquier caso.)

Además, ciertas fórmulas pueden ser rediseñadas para eliminar la división u otros cálculos ineficientes. Para eso, podrías publicar el cálculo más grande que se está realizando. Incluso allí, el propio programa o algoritmo a veces se puede reestructurar para evitar que se golpee con tanta frecuencia los bucles que consumen mucho tiempo.

¿Cuánta precisión se puede sacrificar? Si en la posibilidad remota solo necesita un orden de magnitud, puede obtenerlo fácilmente utilizando el operador de módulo o las operaciones a nivel de bits.

Sin embargo, en general, no hay manera de acelerar la división. Si los hubiera, los compiladores ya lo estarían haciendo.

Answer 3

Esto debería hacerse con una serie de iteraciones de newton pre-desenrolladas evaluadas como un polinomio de Horner que utiliza operaciones de acumulación multiplicada por fusión la mayoría de las CPU de hoy en día se ejecutan en un solo ciclo Clk (cada vez):

float inv_fast(float x) {
    union { float f; int i; } v;
    float w, sx;
    int m;

    sx = (x < 0) ? -1:1;
    x = sx * x;

    v.i = (int)(0x7EF127EA - *(uint32_t *)&x);
    w = x * v.f;

    // Efficient Iterative Approximation Improvement in horner polynomial form.
    v.f = v.f * (2 - w);     // Single iteration, Err = -3.36e-3 * 2^(-flr(log2(x)))
    // v.f = v.f * ( 4 + w * (-6 + w * (4 - w)));  // Second iteration, Err = -1.13e-5 * 2^(-flr(log2(x)))
    // v.f = v.f * (8 + w * (-28 + w * (56 + w * (-70 + w *(56 + w * (-28 + w * (8 - w)))))));  // Third Iteration, Err = +-6.8e-8 *  2^(-flr(log2(x)))

    return v.f * sx;
}

Impresión fina: más cerca de 0, la aproximación no lo hace tan bien, por lo que el programador necesita probar el rendimiento o restringir la entrada a un nivel bajo antes de recurrir a la división de hardware. es decir, ser responsable!

Answer 4

La forma más rápida que conozco es usar las operaciones SIMD. http://msdn.microsoft.com/en-us/library/796k1tty(v=vs.90).aspx

Answer 5

Primero, asegúrese de que esto no sea un caso de optimización prematura. ¿Sabes que este es tu cuello de botella?

Como dice Mystical, 1 / x se puede calcular muy rápidamente. Asegúrese de que no está utilizando el tipo de datos double para el 1 o el divisor. Los flotadores son mucho más rápidos.

Dicho esto, punto de referencia, punto de referencia, punto de referencia. No pierda su tiempo dedicando horas a la teoría numérica para descubrir que la fuente del bajo rendimiento es el acceso a IO.