快速1/X除法(倒数)

Question

如果精度不是至关重要的话,有没有办法在速度方面改善倒数(在X上除1)？

所以,我需要计算1/X. 是否有一些解决方法,所以我失去了精度,但做得更快？

Answer 1

我相信他所寻找的是一种更有效的近似1.0/x的方法,而不是近似的一些技术定义,表明你可以使用1作为一个非常强烈的答案.我也相信这满足了这一点.

#ifdef __cplusplus
    #include <cstdint>
#else
    #include <stdint.h>
#endif

__inline__ double __attribute__((const)) reciprocal( double x ) {
    union {
        double dbl;
        #ifdef __cplusplus
            std::uint_least64_t ull;
        #else
            uint_least64_t ull;
        #endif
    } u;
    u.dbl = x;
    u.ull = ( 0xbfcdd6a18f6a6f52ULL - u.ull ) >> 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 single;
        #ifdef __cplusplus
            std::uint_least32_t uint;
        #else
            uint_least32_t uint;
        #endif
    } u;
    u.single = x;
    u.uint = ( 0xbe6eb3beU - u.uint ) >> 1;
                                // pow( x, -0.5 )
    u.single *= u.single;       // pow( pow(x,-0.5), 2 ) = pow( x, -1 ) = 1.0 / x
    return u.single;
}

#ifdef __cplusplus
    #include <cstdint>
#else
    #include <stdint.h>
#endif
__inline__ double __attribute__((const)) reciprocal( double x ) {
    union {
        double dbl[2];
        #ifdef __cplusplus
            std::uint_least64_t ull[2];
        #else
            uint_least64_t ull[2];
        #endif
    } u;
    u.dbl[0] = x; // dbl is now the active property, so only dbl can be read now
    u.ull[1] = 0;//trick to set ull to the active property so that ull can be read
    u.ull][0] = ( 0xbfcdd6a18f6a6f52ULL - u.ull[0] ) >> 1;
    u.dbl[1] = 0; // now set dbl to the active property so that it can be read
    u.dbl[0] *= u.dbl[0];
    return u.dbl[0];
}
__inline__ float __attribute__((const)) reciprocal( float x ) {
    union {
        float flt[2];
        #ifdef __cplusplus
            std::uint_least32_t ull[2];
        #else
            uint_least32_t ull[2];
        #endif
    } u;
    u.flt[0] = x; // now flt is active
    u.uint[1] = 0; // set uint to be active for reading and writing
    u.uint[0] = ( 0xbe6eb3beU - u.uint[0] ) >> 1;
    u.flt[1] = 0; // set flt to be active for reading and writing
    u.flt[0] *= u.flt[0];
    return u.flt[0];
}

#ifdef __cplusplus
    #include <cstdint>
    #include <cstring>
    #define stdIntWithEightBits std::uint8_t
    #define stdIntSizeOfFloat std::uint32_t
    #define stdIntSizeOfDouble std::uint64_t
#else
    #include <stdint.h>
    #include <string.h>
    #define stdIntWithEightBits uint8_t
    #define stdIntSizeOfFloat uint32_t
    #define stdIntSizeOfDouble uint64_t
#endif

嗯.......如果CPU制造商知道你可以在设计CPU时只用一次乘法,减法和位移来获得倒数,那我就更聪明......嗯........ .

至于基准测试,硬件x ²指令与硬件减法指令相结合,与现代计算机上的硬件1.0/x指令一样快(我的基准测试是在Intel i7上,但我会假设其他处理器的结果相似) .但是,如果将此算法作为新的汇编指令实现到硬件中,那么速度的提高可能足以使该指令非常实用.

有关此方法的更多信息,此实现基于精彩的"快速"逆平方根算法.

最后,请注意我在C++中更像是一个新手.因此,我欢迎任何最佳实践,正确格式化或暗示清晰度的编辑,以便为所有阅读它的人提高答案的质量.

Answer 2

首先,确保这不是过早优化的情况.你知道这是你的瓶颈吗？

正如神秘所说,1/x可以很快计算出来.确保您没有使用double1或除数的数据类型.浮动速度要快得多.

也就是说,基准,基准,基准.不要浪费你的时间花在数值理论上,只是为了发现性能不佳的来源是IO访问.