Logarytm Quick integer dla specjalnego przypadku

Question

Mam wartości całkowite od 32-8191, które chcę odwzorować na zgrubnie skalę logarytmiczną. Gdybym używał bazy 2, mógłbym policzyć wiodące bity zerowe i zamapować je na 8 slotów, ale jest to zbyt jasne; Potrzebuję 32 slotów (i więcej byłoby lepiej, ale potrzebuję ich odwzorować na bity w 32-bitowej wartości), która wychodzi na bazę z grubsza 1,18-1,20 dla logarytmu. Czy ktoś ma jakieś sztuczki do obliczenia tej wartości lub rozsądnego przybliżenia, bardzo szybko?

Moją intuicją jest przełamanie zakresu na 2 lub 3 podzakresy za pomocą warunków warunkowych i użycie małego tabelki odnośników dla każdego, ale zastanawiam się, czy jest jakaś sztuczka, którą mógłbym zrobić z zerami czołowymi, a następnie udoskonalić wynik, zwłaszcza, że ​​wyniki nie muszą być dokładne, ale z grubsza logarytmiczne.

Answer 1

Dlaczego nie użyć dwóch następnych bitów poza bitem wiodącym. Możesz najpierw podzielić liczbę na pojemnik 8, a następne dwa na dalsze dzielenie każdego pojemnika na cztery. W takim przypadku można użyć prostej operacji zmiany, która jest bardzo szybka.

Edytuj: Jeśli uważasz, że użycie logarytmu jest wykonalnym rozwiązaniem. Oto ogólny algorytm:

Niech a będzie podstawą logarytmu, a zakres to (b_min, b_max) = (32,8191). Podstawę można znaleźć za pomocą następującego wzoru:

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

, które dają a~1.1892026. Jeśli użyjesz tego jako podstawy logarytmu, możesz odwzorować zakres (b_min, b_max) na (log_a(b_min), log_a(b_max)) = (20.0004,52.0004).

Teraz wystarczy odjąć cały element od 20.0004, aby uzyskać zakres (0,32). Gwarantuje, że wszystkie elementy są logarytmicznie jednolite. Wykonano:

Uwaga: Każdy element może wypaść z zakresu z powodu błędu numerycznego. Powinieneś sam obliczyć dokładną wartość.

Uwaga 2: log_a (B) = log (B)/log (a)

Answer 2

tabeli przeglądowej jest opcją, że tabela nie jest duża. Jeśli stół 8K jest zbyt duży i masz instrukcję zliczania zer wiodących, możesz użyć wyszukiwania tabeli na kilku pierwszych bitach.

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] 

tabela zapełnić z jakiegoś zbliżenia log_2

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

Jeśli chcesz pozostać w arytmetyce liczb całkowitych, należy pomnożyć przez ostatnią linię wygodnej czynnika.

Answer 3

Odpowiedź Właśnie wpadł oparte na standardzie IEEE 754 zmiennoprzecinkowych:

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

To odwzorowuje 32-8192 na 0-31 przybliżeniu logarytmicznie (tak samo jak hwlau za odpowiedź).

Ulepszona wersja (wyciąć bezużyteczną i bitowe):

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