빠른 1/X 제곱(카운트다운)

내가 겪은 문제의 기록

정밀도가 중요하지 않으면 속도를 높일 수 있는 역수(1을 X로 나누기)가 있습니까?
그래서 나는 1/X를 계산해야 한다. 정밀도를 잃게 하지만 더 빨리 할 수 있는 해결책이 있습니까?

다른 네트워크 기술 커뮤니티에서 찾은 솔루션

𝗛𝗲𝗿𝗲'𝘀 𝗛𝗼𝘄 𝗧𝗼 𝗔𝗽𝗽𝗿𝗼𝘅𝗶𝗺𝗮𝘁𝗲 𝗠𝗼𝗿𝗲 𝗘𝗳𝗳𝗶𝗰𝗶𝗲𝗻𝘁𝗹𝘆


나는 그가 찾은 것이 아주 부정확한 답안으로 1을 사용할 수 있는 근사한 1.0/x와 비슷한 방법이라고 믿는다.나도 이것이 이 점을 만족시켰다고 믿는다.
#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;
}
은마르코프 모형...만약 CPU 제조업체가 CPU를 설계할 때 알았다면 곱셈, 뺄셈, 위치 이동만 하면 역수와 비슷할 수 있다는 것을 알고 싶다.은마르코프 모형...
기준 테스트에 대해 하드웨어 x2 지령과 하드웨어 감법 지령의 결합 속도는 현대 컴퓨터의 하드웨어 1.0/x 지령과 마찬가지로 빠르다(나의 기준 테스트는 인텔i7에서 진행되었지만 다른 프로세서의 결과가 유사하다고 가정할 것이다).그러나 만약 이 알고리즘을 새로운 어셈블리 명령으로 하드웨어에 실현한다면 속도의 향상은 이 명령을 매우 실용적으로 만들 수 있을 것이다.
이 방법에 대한 더 많은 정보는 원더풀 "fast" inverse square root algorithm 을 기반으로 합니다.
Pharap이 알려준 바와 같이 연합체에서 비활성 속성을 읽는 것은 정의되지 않은 행위이기 때문에 나는 그의 유용한 평론에 따라 정의되지 않은 행위를 피하기 위해 두 가지 가능한 해결 방안을 설계했다.첫 번째 해결 방안은 사실상 원시 해결 방안보다 더 좋지 않은 언어적 의미를 빙빙 돌리는 얄미운 수법인 것 같다.
#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];
}
두 번째 가능한 해결 방안은 노조에서 완전히 벗어났기 때문에 더욱 환영을 받는다.그러나 컴파일러가 제대로 최적화되지 않으면 이 해결 방안은 훨씬 느릴 것이다.그러나 다음 솔루션은 바이트 순서와 관계없이 다음과 같은 이점을 제공합니다.
  • 바이트 폭 8비트
  • 바이트는 목표 기계에서 가장 작은 원자 단위다.
  • 더블은 8 바이트, 플로트는 4 바이트.
  • #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
    
    __inline__ double __attribute__((const)) reciprocal( double x ) {
        double byteIndexFloat = 1.1212798184631136e-308;//00 08 10 18 20 28 30 38 bits
        stdIntWithEightBits* byteIndexs = reinterpret_cast<stdIntWithEightBits*>(&byteIndexFloat);
        
        stdIntWithEightBits* inputBytes = reinterpret_cast<stdIntWithEightBits*>(&x);
        
        stdIntSizeOfDouble inputAsUll = (
            (inputBytes[0] << byteIndexs[0]) |
            (inputBytes[1] << byteIndexs[1]) |
            (inputBytes[2] << byteIndexs[2]) |
            (inputBytes[3] << byteIndexs[3]) |
            (inputBytes[4] << byteIndexs[4]) |
            (inputBytes[5] << byteIndexs[5]) |
            (inputBytes[6] << byteIndexs[6]) |
            (inputBytes[7] << byteIndexs[7])
        );
        inputAsUll = ( 0xbfcdd6a18f6a6f52ULL - inputAsUll ) >> 1;
        
        double outputDouble;
        
        const stdIntWithEightBits outputBytes[] = {
            inputAsUll >> byteIndexs[0],
            inputAsUll >> byteIndexs[1],
            inputAsUll >> byteIndexs[2],
            inputAsUll >> byteIndexs[3],
            inputAsUll >> byteIndexs[4],
            inputAsUll >> byteIndexs[5],
            inputAsUll >> byteIndexs[6],
            inputAsUll >> byteIndexs[7]
        };
        memcpy(&outputDouble, &outputBytes, 8);
        
        return outputDouble * outputDouble;
    }
    
    __inline__ float __attribute__((const)) reciprocal( float x ) {
        float byteIndexFloat = 7.40457e-40; // 0x00 08 10 18 bits
        stdIntWithEightBits* byteIndexs = reinterpret_cast<stdIntWithEightBits*>(&byteIndexFloat);
        
        stdIntWithEightBits* inputBytes = reinterpret_cast<stdIntWithEightBits*>(&x);
        
        stdIntSizeOfFloat inputAsInt = (
            (inputBytes[0] << byteIndexs[0]) |
            (inputBytes[1] << byteIndexs[1]) |
            (inputBytes[2] << byteIndexs[2]) |
            (inputBytes[3] << byteIndexs[3])
        );
        inputAsInt = ( 0xbe6eb3beU - inputAsInt ) >> 1;
        
        float outputFloat;
        
        const stdIntWithEightBits outputBytes[] = {
            inputAsInt >> byteIndexs[0],
            inputAsInt >> byteIndexs[1],
            inputAsInt >> byteIndexs[2],
            inputAsInt >> byteIndexs[3]
        };
        memcpy(&outputFloat, &outputBytes, 4);
        
        return outputFloat * outputFloat;
    }
    
    면책 성명: 마지막으로 주의하십시오. 저는 C++의 초보자 같습니다.그러므로 저는 모든 읽는 사람의 답안의 질을 향상시키고 미래의 세월 동안 C++ 지식을 넓히기 위해 최선의 실천, 정확한 격식, 또는 의미가 명확한 편집을 환영합니다.