특별한 경우를위한 빠른 정수 로그

Question

대략적인 대수 눈금으로 매핑하려는 정수 값은 32-8191입니다. 베이스 2를 사용했다면, 선두의 제로 비트를 세어 8 슬롯으로 매핑 할 수 있습니다.하지만 이것은 너무 과격한 것입니다. 나는 32 개의 슬롯이 필요하다. (더 좋을 것이지만 32 비트 값으로 비트를 매핑해야한다.) 로그의 대수는 대략 1.18-1.20이다. 누구나이 값을 계산하거나 합리적인 근사값을 계산하기위한 트릭이 있습니까?

내 직감은 조건부로 범위를 2 ~ 3 개의 하위 범위로 나누고 각각에 대해 작은 조회 표를 사용하지만 개수가 0 인 결과를 정제 할 수있는 트릭이 있는지 궁금해합니다. 특히 결과가 정확할 필요는 없지만 대략 대수적이기 때문에 특히 그렇습니다.

Answer 1

왜 선행 비트 이외의 다음 두 비트를 사용하지 않습니까? 먼저 숫자를 8 개 용지함으로 나눌 수 있으며 다음 2 개 비트를 사용하여 각 용지함을 4 개로 더 나눌 수 있습니다. 이 경우 매우 빠른 간단한 시프트 조작을 사용할 수 있습니다.

편집 : 로그를 사용하는 것이 가능한 해결책이라고 생각한다면. 다음은 일반적인 알고리즘입니다.

a을 대수의 기준으로하고 범위는 (b_min, b_max) = (32,8191)입니다. 수식을 사용하여 자료를 찾을 수 있습니다 :

log(b_max/b_min)/log(a) = 32 bin 

a~1.1892026입니다. 이것을 a의 대수로 사용하면 (b_min, b_max)의 범위를 (log_a(b_min), log_a(b_max)) = (20.0004,52.0004)에 매핑 할 수 있습니다.

범위 (0,32)을 얻으려면 20.0004으로 모든 요소를 ​​빼면됩니다. 모든 요소가 대수적으로 균일하다는 것을 보장합니다. 완료

참고 : 숫자 오류로 인해 요소가 범위를 벗어날 수 있습니다. 정확한 값을 계산하려면 직접 계산해야합니다.

주 2 : log_a (b) = 로그 (b)/로그 (a)

Answer 2

룩업 테이블은 그 테이블은 크지 않은 한 옵션이다. 8K 테이블이 너무 크고 0을 시작하는 카운트가있는 경우 상위 몇 비트에서 테이블 조회를 사용할 수 있습니다.

nbits = 32 - count_leading_zeros(v) # number of bits in number 
highbits = v >> (nbits - 4)   # top 4 bits. Top bit is always a 1. 
log_base_2 = nbits + table[highbits & 0x7] 

당신이

table[i] = approx(log_2(1 + i/8.0)) 

당신은, 정수 연산에있어 편리한 요인에 의해 마지막 줄을 곱하려면 log_2

의 일부 근사치로 채울 테이블. 부동 소수점 IEEE 754을 기반으로

Answer 3

대답 난 그냥 와서 :

((union { float v; uint32_t r; }){ x }.r >> 21 & 127) - 16 

그것은 (hwlau의 대답과 동일) 32-8192 0-31 위에 대략 대수적으로 매핑합니다.

향상된 버전 (쓸모 비트 및 절단) : 나는 (dlmalloc가 마음에 온다) 전에 완료 뭔가를 본 적이

((union { float v; uint32_t r; }){ x }.r >> 21) - 528