Нахождение показателя при n = 2 **x с использованием побитовых операций [логарифм по основанию 2 из n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли простой способ извлечь показатель степени из степени 2, используя только побитовые операции?
Редактировать: Хотя изначально вопрос был о побитовых операциях, этот поток также пригодится для чтения, если вам интересно "Какой самый быстрый способ найти X при Y = 2X в Python?"**
В настоящее время я пытаюсь оптимизировать рутину (Тест на простоту Рабина-Миллера) , что уменьшает четное число N в формах 2**s * d.Я могу получить 2**s часть по:
two_power_s = N & -N
но я не могу найти способ извлечь просто "s" с помощью побитовой операции.Обходными путями, которые я в настоящее время тестирую без особого удовлетворения (все они довольно медленные), являются:
- использование функции логарифмирования
- манипулирование двоичным представлением 2 **s (т.е.подсчет конечных нулей)
- повторяем деление на 2 до тех пор, пока результат не будет равен 1
Я использую python, но ответ на этот вопрос, я полагаю, не зависит от языка.
Решение 2
Короткий ответ
Что касается python, то:
- В самый быстрый метод из всех чтобы найти показатель степени 2 * * x, нужно заглянуть в словарь, хэши которого равны степеням 2 (см. "поиск хэша" в коде)
- В самый быстрый побитовый метод это тот , кто называется "развернутый_битвенно".
- Оба предыдущих метода имеют четко определенные (но расширяемые) верхние пределы.В самый быстрый метод без жестко заданных верхних пределов (который масштабируется настолько, насколько python может обрабатывать числа) является "log_e".
Предварительные замечания
- Все приведенные ниже измерения скорости были получены с помощью
timeit.Timer.repeat(testn, cycles)гдеtestnбыло установлено значение 3 иcyclesбыл автоматически настроен скриптом для получения времени в диапазоне секунд (примечание: в этом механизме автоматической настройки была ошибка, которая была исправлена 18.02.2010). - Не все методы могут масштабироваться, вот почему я не тестировал все функции для различных степеней 2
- Мне не удалось заставить некоторые из предложенных методов работать (функция возвращает неверный результат).У меня еще не было возможности выполнить пошаговый сеанс отладки:Я включил код (прокомментировал) на случай, если кто-то обнаружит ошибку при проверке (или захочет выполнить отладку самостоятельно)
Результаты
функция (25)**
hashlookup: 0.13s 100%
lookup: 0.15s 109%
stringcount: 0.29s 220%
unrolled_bitwise: 0.36s 272%
log_e: 0.60s 450%
bitcounter: 0.64s 479%
log_2: 0.69s 515%
ilog: 0.81s 609%
bitwise: 1.10s 821%
olgn: 1.42s 1065%
функция (231)**
hashlookup: 0.11s 100%
unrolled_bitwise: 0.26s 229%
log_e: 0.30s 268%
stringcount: 0.30s 270%
log_2: 0.34s 301%
ilog: 0.41s 363%
bitwise: 0.87s 778%
olgn: 1.02s 912%
bitcounter: 1.42s 1264%
функция (2128)**
hashlookup: 0.01s 100%
stringcount: 0.03s 264%
log_e: 0.04s 315%
log_2: 0.04s 383%
olgn: 0.18s 1585%
bitcounter: 1.41s 12393%
функция (21024)**
log_e: 0.00s 100%
log_2: 0.01s 118%
stringcount: 0.02s 354%
olgn: 0.03s 707%
bitcounter: 1.73s 37695%
Код
import math, sys
def stringcount(v):
"""mac"""
return len(bin(v)) - 3
def log_2(v):
"""mac"""
return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999
def log_e(v):
"""bp on mac"""
return int(round(math.log(v)/0.69314718055994529, 0)) # 0.69 == log(2)
def bitcounter(v):
"""John Y on mac"""
r = 0
while v > 1 :
v >>= 1
r += 1
return r
def olgn(n) :
"""outis"""
if n < 1:
return -1
low = 0
high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
def hashlookup(v):
"""mac on brone -- limit: v < 2**131"""
# def prepareTable(max_log2=130) :
# hash_table = {}
# for p in range(1, max_log2) :
# hash_table[2**p] = p
# return hash_table
global hash_table
return hash_table[v]
def lookup(v):
"""brone -- limit: v < 2**11"""
# def prepareTable(max_log2=10) :
# log2s_table=[0]*((1<<max_log2)+1)
# for i in range(max_log2+1):
# log2s_table[1<<i]=i
# return tuple(log2s_table)
global log2s_table
return log2s_table[v]
def bitwise(v):
"""Mark Byers -- limit: v < 2**32"""
b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000)
S = (1, 2, 4, 8, 16)
r = 0
for i in range(4, -1, -1) :
if (v & b[i]) :
v >>= S[i];
r |= S[i];
return r
def unrolled_bitwise(v):
"""x4u on Mark Byers -- limit: v < 2**33"""
r = 0;
if v > 0xffff :
v >>= 16
r = 16;
if v > 0x00ff :
v >>= 8
r += 8;
if v > 0x000f :
v >>= 4
r += 4;
if v > 0x0003 :
v >>= 2
r += 2;
return r + (v >> 1)
def ilog(v):
"""Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32"""
ret = 1
m = (not not v & 0xFFFF0000) << 4;
v >>= m;
ret |= m;
m = (not not v & 0xFF00) << 3;
v >>= m;
ret |= m;
m = (not not v & 0xF0) << 2;
v >>= m;
ret |= m;
m = (not not v & 0xC) << 1;
v >>= m;
ret |= m;
ret += (not not v & 0x2);
return ret - 1;
# following table is equal to "return hashlookup.prepareTable()"
hash_table = {...} # numbers have been cut out to avoid cluttering the post
# following table is equal to "return lookup.prepareTable()" - cached for speed
log2s_table = (...) # numbers have been cut out to avoid cluttering the post
Другие советы
"языковой агностик" и беспокойство о производительности - понятия в значительной степени несовместимые.
Большинство современных процессоров имеют инструкцию CLZ "подсчитывать начальные нули".В GCC вы можете получить к нему доступ с помощью __builtin_clz(x) (который также создает разумный, если не самый быстрый, код для целей, которым не хватает clz).Обратите внимание, что этот CLZ не определен для нуля, поэтому вам понадобится дополнительная ветвь, чтобы перехватить этот случай, если это имеет значение в вашем приложении.
В кельтском ( http://celt-codec.org ) CLZ без ветвей , который мы используем для компиляторов , не имеющих CLZ , был написан Тимоти Б.Терриберри:
int ilog(uint32 _v){
int ret;
int m;
ret=!!_v;
m=!!(_v&0xFFFF0000)<<4;
_v>>=m;
ret|=m;
m=!!(_v&0xFF00)<<3;
_v>>=m;
ret|=m;
m=!!(_v&0xF0)<<2;
_v>>=m;
ret|=m;
m=!!(_v&0xC)<<1;
_v>>=m;
ret|=m;
ret+=!!(_v&0x2);
return ret;
}
(Комментарии указывают, что это оказалось быстрее, чем версия с ветвлением и версия на основе таблицы подстановки)
Но если производительность настолько критична, вам, вероятно, не следует реализовывать эту часть вашего кода на python.
Существует страница с множеством подобных трюков и хаков.Он написан для C, но многие из них должны работать и на Python (хотя производительность, очевидно, будет отличаться).То, что вы хотите, это здесь и так далее.
Вы могли бы попробовать это например:
register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
if (v & b[i])
{
v >>= S[i];
r |= S[i];
}
}
Похоже, что его можно было бы довольно легко преобразовать в Python.
Вы можете сделать это за O (lg s) времени для целых чисел произвольной длины, используя binsearch.
import sys
def floorlg(n):
if n < 1:
return -1
low=0
high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
Для целых чисел фиксированного размера таблица подстановки должна быть самым быстрым решением и, вероятно, лучшим в целом.
Похоже, что диапазон известен.Давайте предположим, что оно достигает 1<<20, просто чтобы сделать это более интересным:
max_log2=20
Итак, составьте список, который (по сути) сопоставляет целое число с его логарифмом по основанию 2.Для достижения цели потребуется следующее:
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(Это не делает ничего полезного для чисел, которые не являются степенями двойки;формулировка проблемы предполагает, что с ними не нужно обращаться.Хотя это было бы достаточно легко исправить.)
Функция для получения логарифма очень проста и может быть легко встроена:
def table(v):
return log2s_table[v]
Я не могу гарантировать, что тестовый код, который я написал, точно такой же, как тот, который используется для получения таймингов примера, но это довольно быстрее, чем stringcount код:
stringcount: 0.43 s.
table: 0.16 s.
Поскольку все значения в таблице меньше 256, я подумал, будет ли быстрее использовать строку вместо списка, или, может быть, array.array из байтов, но без кубиков:
string: 0.25 s.
arr: 0.21 s.
Используя dict выполнить поиск - это еще одна возможность, использующая в своих интересах способ проверки только степеней двойки:
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
Однако результаты для этого были не такими хорошими:
map: 0.20 s.
И просто для развлечения можно было бы также использовать hex метод для объектов с плавающей точкой для получения строки, которая включает (в качестве своей последней части) базовый 2-й показатель числа.В целом это немного медленно извлекается, но если показатель степени будет состоять только из одной цифры, это можно было бы сделать достаточно просто:
def floathex(v):
return ord(float(v).hex()[-1])-48
Это исключительно для развлечения, хотя и было неконкурентоспособным - хотя, что удивительно, все еще быстрее, чем побитовый подход.
Таким образом, похоже, что использование списка - это правильный путь.
(Этот подход не будет масштабироваться бесконечно из-за ограниченной памяти, но чтобы компенсировать это, скорость выполнения не будет зависеть от max_log2, или входные значения, любым способом, который вы заметите при запуске кода python.Что касается потребления памяти, если я правильно помню свои внутренние компоненты python, таблица займет около (1<<max_log2)*4 байты, потому что все содержимое представляет собой небольшие целые числа, которые интерпретатор будет интернировать автоматически.ИТАК, когда max_log2 равно 20, это примерно 4 МБ.)
На самом деле это комментарий к тесту производительности, опубликованному mac.Я публикую это как ответ, чтобы обеспечить правильное форматирование кода и отступы
мак, не мог бы ты попробовать развернутую реализацию bitseach, предложенную Марком Байерсом?Возможно, это просто доступ к массиву, который замедляет его.Теоретически этот подход должен быть быстрее, чем другие.
Это выглядело бы примерно так, хотя я не уверен, подходит ли форматирование для python, но я думаю, вы можете видеть, что оно должно делать.
def bitwise(v):
r = 0;
if( v > 0xffff ) : v >>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
Если python разделяет отсутствие в java неписаных целых чисел, это должно быть что-то вроде этого:
def bitwise(v):
r = 0;
if( v & 0xffff0000 ) : v >>>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
Опаздываю на вечеринку, но как насчет int.bit_length(n) - 1?Вы просили прямолинейности, и это кажется мне самым простым.Реализация CPython выглядит достаточно производительной.
