@NotImplemented12 авг 2014 в 17:47

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

2 мин

30K

Алгоритмы *

Из песочницы

+43

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

@alexeykuzmin0 12 авг 2014 в 18:20

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

@Mrrl 12 авг 2014 в 18:25

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

@ripatti 12 авг 2014 в 18:38

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

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

@Mrrl 12 авг 2014 в 18:41

m&-m

@ripatti 12 авг 2014 в 18:48

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

@mayorovp 13 авг 2014 в 07:22

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

@MichaelBorisov 13 авг 2014 в 08:52

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

@mayorovp 13 авг 2014 в 09:02

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

@encyclopedist 13 авг 2014 в 10: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 в 12:09

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

@encyclopedist 13 авг 2014 в 12:24

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

@mikhaelkh 12 авг 2014 в 19:07

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

@Mrrl 12 авг 2014 в 19: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 в 08:30

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

@ripatti 12 авг 2014 в 18:37

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

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

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

@mikhaelkh 13 авг 2014 в 08:33

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

@Mrrl 13 авг 2014 в 08:43

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

@NeoNN 12 авг 2014 в 18:42

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

@jcmvbkbc 12 авг 2014 в 19:12

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

@andy_p 12 авг 2014 в 19:25

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

@mayorovp 13 авг 2014 в 07:24

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

@Mrrl 12 авг 2014 в 19: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 12 авг 2014 в 21:24

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

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

@dimview 13 авг 2014 в 00:05

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

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

@ankh1989 13 авг 2014 в 01:55

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

@dimview 13 авг 2014 в 02:36

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

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

@Sadler 13 авг 2014 в 03:56

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

@Lockal 13 авг 2014 в 04:53

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

@Sadler 13 авг 2014 в 03:55

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

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

@Mrrl 13 авг 2014 в 04:19

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

@Sadler 13 авг 2014 в 04:28

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

@gonzazoid 13 авг 2014 в 07:57

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

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

@dimview 13 авг 2014 в 15:26

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

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

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

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

@doom369 15 авг 2014 в 09:51

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

@jcmvbkbc 15 авг 2014 в 10:25

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

@Lockal 15 авг 2014 в 16:43

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

@jcmvbkbc 15 авг 2014 в 16:46

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

@supernapalm 12 авг 2014 в 20:31

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

@mayorovp 13 авг 2014 в 07:33

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

@supernapalm 13 авг 2014 в 13:59

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

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

@mayorovp 13 авг 2014 в 14:59

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

@gonzazoid 13 авг 2014 в 16:32

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

@qw1 14 авг 2014 в 10:21

Исключение — 8-битные CPU, которые чаще всего имеет физическую 16-битную шину адреса и адресуют 64KB

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

@agnostik 6 фев 2015 в 09:28

А мог бы кто-нибудь обяснить что такое «за О(1)»?

@mayorovp 6 фев 2015 в 10:19

Асимптотическая оценка времени для алгоритма. O(1) означает асимптотическую константу — т.е. время работы алгоритма ограничено сверху.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий