효율적으로 플로어 로그베이스를 계산하는 방법 2^(1/4)

Question

컴퓨팅 floor(log_2(x))many 빠른 알고리즘이있는 0의 수를 계산하여 계산할 수 있습니다.

x이 가능한 모든 값에 이르기까지 64 비트 부호없는 int 일 때 floor(log_{2^(1/4)}(x))에 대해 비슷한 기법이 있습니까?

log_{2^(1/4)}(x)=4*log_2(x)=log_2(x^4)부터 floor(4*log_2(x)) 또는 floor(log(x^4))에 대한 효율적인 알고리즘을 찾는 것과 같습니다.

Answer 1

우리가 floor(log_2(x))을 계산 한 후, 우리는 z = x/2^floor(log_2(x))를 나눌 수 z이 floor(log_{2^(1/4)}(x)) = 4 floor(log_2(x)) + floor(log_{2^(1/4)}(z)) 때문에, 범위 [1, 2)에 속하는 곳 컴퓨팅 floor(log_{2^(1/4)}(z))의 문제를 고려한다. floor(log_{2^(1/4)}(z)) 네 가지 가능성 때문에

(2^(1/4))^1, (2^(1/4))^2, (2^(1/4))^3 

이 충분 상수와 z의 두 비교 (무점포을위한 세)에만있다. 부동 소수점 산술을 완전히 피하기 위해 "나누기"는 마찬가지로 표현 된 상수와 비교할 (2^63) z 인 왼쪽 시프트로 구현할 수 있습니다.

#include <assert.h> 
#include <stdio.h> 

static int mylog(unsigned long long x) { 
    assert(x > 0ULL); 
    /* compute n = floor(log2(x)) */ 
    unsigned long long y = x | (x >> 1); 
    y |= y >> 2; 
    y |= y >> 4; 
    y |= y >> 8; 
    y |= y >> 16; 
    y |= y >> 32; 
    y -= (y >> 1) & 0x5555555555555555ULL; 
    y = (y & 0x3333333333333333ULL) + ((y >> 2) & 0x3333333333333333ULL); 
    y = (y + (y >> 4)) & 0x0f0f0f0f0f0f0f0fULL; 
    y = (y + (y >> 8)) & 0x00ff00ff00ff00ffULL; 
    y = (y + (y >> 16)) & 0x0000ffff0000ffffULL; 
    y = (y + (y >> 32)) & 0x00000000ffffffffULL; 
    int n = (int)y - 1; 
    /* normalize x and use binary search to find the last two bits of the log */ 
    x <<= 63 - n; 
    n <<= 2; 
    if (x < 0xb504f333f9de6485ULL) { 
    return x < 0x9837f0518db8a970ULL ? n  : n + 1; 
    } else { 
    return x < 0xd744fccad69d6af5ULL ? n + 2 : n + 3; 
    } 
} 

int main(void) { 
    unsigned long long x; 
    while (scanf("%llu", &x) == 1) { 
    printf("%d\n", mylog(x)); 
    } 
} 

상수를 계산하는 매쓰/볼프람 알파 쿼리

BaseForm[Table[Ceiling[2^(63+i/4)],{i,1,3}],16] .