Быстрый целочисленный логарифм для специального случая

Question

У меня есть целочисленные значения в диапазоне 32-8191, которые я хочу отобразить в примерно логарифмическом масштабе.Если бы я использовал базу 2, я мог бы просто посчитать начальные нулевые биты и отобразить их в 8 слотов, но это слишком конечно;Мне нужно 32 слота (и больше было бы лучше, но мне нужно, чтобы они отображались на биты в 32-битном значении), что составляет примерно 1,18-1,20 для логарифма.У кого-нибудь есть какие-то хитрости для вычисления этого значения или разумного приближения, очень быстрого?

Моя интуиция состоит в том, чтобы разбить диапазон на 2 или 3 поддиапазона с помощью условных выражений, и использовать небольшую таблицу поиска для каждого, но яИнтересно, есть ли какой-нибудь трюк, который я мог бы сделать с нулями-ведущими, а затем уточнить результат, тем более что результаты не должны быть точными, а просто примерно логарифмическими.

Answer 1

Почему бы не использовать следующие два бита, кроме начального бита.Вы можете сначала разделить число на 8 бинов, а следующие два бита разделить каждый бин на четыре.В этом случае вы можете использовать простую операцию сдвига, которая очень быстрая.

Редактировать : Если вы считаете, что использование логарифма является жизнеспособным решением.Вот общий алгоритм:

Пусть 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).

Теперь вам нужно только вычесть все элементы на 20.0004, чтобы получить диапазон (0,32).Это гарантирует, что все элементы логарифмически однородны.Готово

Примечание : любой элемент может выйти за пределы диапазона из-за числовой ошибки.Вы должны рассчитать его для точного значения.

Примечание2 : log_a (b) = log (b) / log (a)

Answer 2

Ответ Я только что придумал, основываясь на IEEE 754 с плавающей точкой:

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

Он отображает 32-8192 на 0-31 примерно логарифмически (так же, как ответ hwlau).

Улучшенная версия (вырезано бесполезно и по битам):

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

Answer 3

Таблица поиска является одним из вариантов, эта таблица не так уж велика. Если таблица 8К слишком велика, и у вас есть инструкция подсчета ведущих нулей, вы можете использовать поиск по старшим разрядам.

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]

Таблица, которую вы заполняете с некоторым приближением log_2

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

Если вы хотите использовать целочисленную арифметику, умножьте последнюю строку на удобный коэффициент.