NotImplemented 12 авг 2014 в 21:47

Как найти показатель степени двойки за O(1) с помощью последовательности де Брёйна

2 мин

30K

Алгоритмы*

Из песочницы

+44

Комментарии 49

alexeykuzmin0 12 авг 2014 в 22:20

Довольно интересно! Еще бы умножение за O(1) работало

Mrrl 12 авг 2014 в 22:25

Можно взять простое число, не меньшее k, для которого двойка является порождающим элементом мультипликативной группы (например, для k=32 это p=37) и посчитать остаток от деления 2^n на p. Все остатки будут различны, и найти логарифм можно по табличке.
Ещё на закуску не хватает задачи «найти по числу m его максимальный делитель вида 2^n за время O(1)»

ripatti 12 авг 2014 в 22:38

найти по числу m его максимальный делитель вида 2^n за время O(1)

Казалось бы m ^ (m & (m-1)).

Mrrl 12 авг 2014 в 22:41

m&-m

ripatti 12 авг 2014 в 22:48

Оу, так, конечно, красивее, а мой способ работает и для unsigned.

mayorovp 13 авг 2014 в 11:22

-m тоже прекрасно работает для unsigned

MichaelBorisov 13 авг 2014 в 12:52

Не на всех компиляторах. Undefined behavior.

mayorovp 13 авг 2014 в 13:02

m-1 для m=0 тоже UB, в этом отношении способы одинаково неправильные

encyclopedist 13 авг 2014 в 14:17

Вроде вполне определенное С++11 [basic.fundamental]:

Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number
of bits in the value representation of that particular size of integer.

mayorovp 13 авг 2014 в 16:09

Но -m тоже под этот пункт попадает тогда…

encyclopedist 13 авг 2014 в 16:24

Вроде да, тоже подходит.

mikhaelkh 12 авг 2014 в 23:07

Зачем простое? Достаточно нечётное… Ну и чтоб размер мультипликативной группы >n. Но здесь же обычный бинпоиск;)

Mrrl 12 авг 2014 в 23:17

Надо, чтобы порядок двойки в группе был не меньше k. Для составного p это сразу увеличивает его минимальное значение более, чем вдвое: если p=q*r, то его мультипликативная группа — Z_{q-1} x Z_{r-1}, и порядок любого элемента не больше LCM(q-1,r-1)<=(q-1)*(r-1)/2. Так что простое лучше.

mikhaelkh 13 авг 2014 в 12:30

Кстати, в GCC есть __builtin_ffs или __builtin_ctz для решения этой задачи.

ripatti 12 авг 2014 в 22:37

В таком графе, в каждую вершину входит два ребра и выходит два ребра, а значит существует Эйлеров цикл

Зануда во мне говорит, что граф еще должен быть связным.

А вообще спасибо за статью, интересно.

mikhaelkh 13 авг 2014 в 12:33

Как из наличия эйлерова цикла следует наличие гамильтонова?

Mrrl 13 авг 2014 в 12:43

Там в качестве вершин надо брать подстроки длиной k-1. Тогда каждое ребро будет соответствовать подстроке длины k, и эйлеров цикл даст как раз нужную последовательность. Парочка рёбер окажется петлями, но это неважно.

NeoNN 12 авг 2014 в 22:42

Есть карточный фокус, который основан на де Брёйне: www.math.ubc.ca/~anstee/math443/DeBruijnCardTrick.pdf

jcmvbkbc 12 авг 2014 в 23:12

Предположение, что умножение n-битных чисел выполняется за O(1) означает, что n ограничено.
Но тогда и традиционный двоичный поиск — решение за O(1) (с коэффициентом log n).

andy_p 12 авг 2014 в 23:25

Если n небольшое, составляем таблицу из 2^n,
результатов, затем за O(1) выбираем в этой таблице
по входному числу как индексу.

mayorovp 13 авг 2014 в 11:24

Очевидно, n=32 или 64. Таблицу уже не составить.

Mrrl 12 авг 2014 в 23:48

А количество бит лучше считать как-нибудь так:

    n=(n&0x55555555)+((n>>1)&0x55555555);
    n=(n&0x33333333)+((n>>2)&0x33333333);
    n=(n+(n>>4))&0x0f0f0f0f;
    n+=n>>8;
    count=(n+(n>>16))&0xff;

dimview 13 авг 2014 в 01:24

Пока кто-нибудь не изобретёт 64-битный процессор.

НЛО прилетело и опубликовало эту надпись здесь

dimview 13 авг 2014 в 04:05

А потом кто-то изобретёт 128-битный процессор. На нём этот код будет продолжать компилироваться без ошибок и предупреждений, но работать не всегда правильно. Как код от Ариан-4 на Ариан-5.

А приведённый автором код из книжки Кернигана и Ричи будет продолжать работать без изменений на любом процессоре, от PDP-11 до самых современных. Вне зависимости от набора инструкций. И скорость выполнения у него та же O(1).

ankh1989 13 авг 2014 в 05:55

Такая совместимость со всеми возможными процессорами нужна наверно разве что ядру линукса. Большинство программ пишется и умирает гораздо быстрее чем живёт одно поколение процессоров.

dimview 13 авг 2014 в 06:36

Скорее наоборот, такого рода оптимизация имеет смысл разве что в ядре операционной системы или в компиляторе (которые всё равно пишутся или по крайней мере подгоняются под конкретный процессор).

А в прикладных программах эти трюки попадают под определение premature optimization.

Sadler 13 авг 2014 в 07:56

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

Lockal 13 авг 2014 в 08:53

На таком уровне оптимизация имеет смысл на компиляторах, а не на компилируемых программах. Так, поддержка popcount есть как в GCC, так и в Clang. А вот ни один из вышеприведённых способов ни GCC, ни Clang довести до инструкции POPCNT не смогли.

Sadler 13 авг 2014 в 07:55

А потом кто-то изобретёт 128-битный процессор.

К этому есть какие-то предпосылки? Если 64 бита ещё как-то были оправданы адресацией памяти и расчётами с числами двойной точности, то применения 128-битам в ближайшие лет 20 я лично придумать не могу (даже с учётом предположения о росте требуемых объёмов памяти пропорционально росту вычислительных возможностей по закону Мура).

Mrrl 13 авг 2014 в 08:19

А всякая криптография? С какой разрядностью ей приходится работать?
64 бит не хватает даже чтобы написать «наивную» арифметику по модулю больше, чем 2^32. Или в других ситуациях, когда надо посчитать a*b/c, но не хочется уходить от целых чисел.

Sadler 13 авг 2014 в 08:28

А «всякая криптография» у нас уже либо достаточно заоптимизирована, чтобы не замечать её выполнение на текущих процессорах, либо вынесена в отдельные железные модули в случае, если требуется высокая пропускная способность при низкой нагрузке на CPU. Потому для конечных пользователей эта проблема стоит не очень остро даже с учётом запросов бизнеса.

gonzazoid 13 авг 2014 в 11:57

вводить 128 бит будут маркетологи, они оправдают, без оглядки на Ваше мнение. Хотя как по мне — давно пора, есть ряд алгоритмов, которые значительно упростятся, имей они такое виртуальное адресное пространство.

НЛО прилетело и опубликовало эту надпись здесь

dimview 13 авг 2014 в 19:26

Как же не привёл? Вот он:

while (n) {
++count;
n &= (n-1);
}

Прямо из Кернигана и Ричи. Процессоров с переменной разрядностью я пока не встречал, так что это константа.

НЛО прилетело и опубликовало эту надпись здесь

doom369 15 авг 2014 в 13:51

Зачем, если есть popcnt? software.intel.com/en-us/node/512035

jcmvbkbc 15 авг 2014 в 14:25

Для процессоров без popcnt. За пределами intel тоже есть жизнь.

Lockal 15 авг 2014 в 20:43

А для арма есть _popcountsi2. Вот поэтому я и писал выше, что это задача компилятора, а не программиста. В GCC и Clang для этого есть __builtin_popcount. Пусть компилятор соберёт оптимальный набор инструкций.

jcmvbkbc 15 авг 2014 в 20:46

Это может быть и кодом для библиотеки поддержки компилятора в том числе. Хотя таблично population count считается несколько быстрее.

supernapalm 13 авг 2014 в 00:31

Вообще говоря, сложность какого-то алгоритма имеет смысл только при указании вычислительной модели. Вы посчитали, как я понимаю, для модели RAM, но, увы, для реальных компьютеров все немного хуже — с длиной числа нужно будет считаться (по сути, количество бит числа будет тем самым n). А за счет умножения у вас даже линейной сложности не выйдет.

mayorovp 13 авг 2014 в 11:33

Тем не менее, для n=32 или 64 этот алгоритм может работать быстрее «стандартного» на тех процессорах, которые умеют умножать быстро.

supernapalm 13 авг 2014 в 17:59

И это не совсем верно. Важно понимать, что 64-битные процессоры не смогут быстро и верно перемножить два 64-битных числа в общем случае, ведь их произведение будет занимать больше, чем 64 бита. С уверенностью мы можем говорить лишь про n <= 15 и n <= 31 соответственно.

Для таких чисел мы бинпоиском можем определить степень за, соответственно, 4 и 5 сравнений. Вы уверены, что это медленней чем все действия по алгоритму?

mayorovp 13 авг 2014 в 18:59

Наверное, это будет для вас сюрпризом — но операция mul/imul, примененная к 64х-разрядным операндам, дает 128и-битный результат. Тот факт, что старшая часть чаще всего отбрасывается, обусловлен системой типов языков высокого уровня, но на низком уровне такой проблемы не стоит.

gonzazoid 13 авг 2014 в 20:32

под разрядностью процессора как правило понимают разрядность его интерфейса — разрядность адресуемого пространства и разрядность шины. Внутри процессора может твориться все что угодно. Более того, оно там творится, и уже достаточно давно(по крайней мере для x86 семейства)