[rust] Rust에서 Quake의 빠른 InvSqrt () 함수를 작성할 수 있습니까?

Program / 글쓴이

이것은 단지 내 자신의 호기심을 만족시키기위한 것입니다.

이것의 구현이 있습니까?

float InvSqrt (float x)
{
   float xhalf = 0.5f*x;
   int i = *(int*)&x;
   i = 0x5f3759df - (i>>1);
   x = *(float*)&i;
   x = x*(1.5f - xhalf*x*x);
   return x;
}

녹에? 존재하는 경우 코드를 게시하십시오.

나는 그것을 시도하고 실패했다. 정수 형식을 사용하여 부동 숫자를 인코딩하는 방법을 모르겠습니다. 내 시도는 다음과 같습니다.

fn main() {
    println!("Hello, world!");
    println!("sqrt1: {}, ",sqrt2(100f64));
}

fn sqrt1(x: f64) -> f64 {
    x.sqrt()
}

fn sqrt2(x: f64) -> f64 {
    let mut x = x;
    let xhalf = 0.5*x;
    let mut i = x as i64;
    println!("sqrt1: {}, ", i);

    i = 0x5f375a86 as i64 - (i>>1);

    x = i as f64;
    x = x*(1.5f64 - xhalf*x*x);
    1.0/x
}

참조 :
1. Quake3의 빠른 InvSqrt ()의 기원-1 페이지
2. Quake의 빠른 역 제곱근 이해
3. FAST INVERSE SQUARE ROOT.pdf
4. 소스 코드 : q_math.c # L552-L572

답변

정수 형식을 사용하여 부동 숫자를 인코딩하는 방법을 모르겠습니다.

이를위한 함수가 있습니다 : f32::to_bits를 반환합니다 u32. : 다른 방향의 기능도있다 f32::from_bits소요 u32인자로는. 이러한 기능은 mem::transmute후자가 unsafe사용하기 까다롭기 때문에 선호 됩니다 .

이를 통해 다음이 구현됩니다 InvSqrt.

fn inv_sqrt(x: f32) -> f32 {
    let i = x.to_bits();
    let i = 0x5f3759df - (i >> 1);
    let y = f32::from_bits(i);

    y * (1.5 - 0.5 * x * y * y)
}

( 운동장 )

이 함수는 x86-64에서 다음 어셈블리로 컴파일됩니다.

.LCPI0_0:
        .long   3204448256        ; f32 -0.5
.LCPI0_1:
        .long   1069547520        ; f32  1.5
example::inv_sqrt:
        movd    eax, xmm0
        shr     eax                   ; i << 1
        mov     ecx, 1597463007       ; 0x5f3759df
        sub     ecx, eax              ; 0x5f3759df - ...
        movd    xmm1, ecx
        mulss   xmm0, dword ptr [rip + .LCPI0_0]    ; x *= 0.5
        mulss   xmm0, xmm1                          ; x *= y
        mulss   xmm0, xmm1                          ; x *= y
        addss   xmm0, dword ptr [rip + .LCPI0_1]    ; x += 1.5
        mulss   xmm0, xmm1                          ; x *= y
        ret

참조 어셈블리를 찾지 못했습니다 (있는 경우 알려주세요!). 왜 부동 소수점이 eax시프트 및 정수 뺄셈을하기 위해 이동했는지 잘 모르겠습니다 . SSE 레지스터가 이러한 작업을 지원하지 않을 수 있습니까?

clang 9.0 with -O3C 코드는 기본적으로 동일한 어셈블리로 C 코드를 컴파일합니다 . 좋은 징조입니다.

실제로 이것을 실제로 사용하려면 다음을 수행하지 마십시오. benrg 이 의견에서 지적했듯이 최신 x86 CPU에는이 기능에 대한 특수 명령 이이 해킹보다 빠르고 정확합니다. 불행히도 1.0 / x.sqrt() 그 명령에 최적화되지 않는 것 같습니다 . 따라서 속도가 정말로 필요하다면 내장 함수를 사용 하는_mm_rsqrt_ps 것이 좋습니다. 그러나 이것은 다시 unsafe코드를 요구 합니다. 소수의 프로그래머가 실제로 필요하기 때문에이 답변에 대해서는 자세히 설명하지 않습니다.

답변

이것은 unionRust에서 덜 알려진 것으로 구현되었습니다 .

union FI {
    f: f32,
    i: i32,
}

fn inv_sqrt(x: f32) -> f32 {
    let mut u = FI { f: x };
    unsafe {
        u.i = 0x5f3759df - (u.i >> 1);
        u.f * (1.5 - 0.5 * x * u.f * u.f)
    }
}

criterionx86-64 Linux 상자에서 크레이트를 사용하는 일부 마이크로 벤치 마크를 수행했습니다 . 놀랍게도 녹 자체 sqrt().recip()가 가장 빠릅니다. 그러나 물론 마이크로 벤치 마크 결과는 소금 한 알갱이로 가져와야합니다.

inv sqrt with transmute time:   [1.6605 ns 1.6638 ns 1.6679 ns]
inv sqrt with union     time:   [1.6543 ns 1.6583 ns 1.6633 ns]
inv sqrt with to and from bits
                        time:   [1.7659 ns 1.7677 ns 1.7697 ns]
inv sqrt with powf      time:   [7.1037 ns 7.1125 ns 7.1223 ns]
inv sqrt with sqrt then recip
                        time:   [1.5466 ns 1.5488 ns 1.5513 ns]

답변

std::mem::transmute필요한 변환을하기 위해 사용할 수 있습니다 :

fn inv_sqrt(x: f32) -> f32 {
    let xhalf = 0.5f32 * x;
    let mut i: i32 = unsafe { std::mem::transmute(x) };
    i = 0x5f3759df - (i >> 1);
    let mut res: f32 = unsafe { std::mem::transmute(i) };
    res = res * (1.5f32 - xhalf * res * res);
    res
}

여기에서 실제 예를 찾을 수 있습니다. 여기

답변