Comments 49
Довольно интересно! Еще бы умножение за O(1) работало
Можно взять простое число, не меньшее k, для которого двойка является порождающим элементом мультипликативной группы (например, для k=32 это p=37) и посчитать остаток от деления 2^n на p. Все остатки будут различны, и найти логарифм можно по табличке.
Ещё на закуску не хватает задачи «найти по числу m его максимальный делитель вида 2^n за время O(1)»
Ещё на закуску не хватает задачи «найти по числу m его максимальный делитель вида 2^n за время O(1)»
найти по числу m его максимальный делитель вида 2^n за время O(1)
Казалось бы
m ^ (m & (m-1)).
Зачем простое? Достаточно нечётное… Ну и чтоб размер мультипликативной группы >n. Но здесь же обычный бинпоиск;)
В таком графе, в каждую вершину входит два ребра и выходит два ребра, а значит существует Эйлеров цикл
Зануда во мне говорит, что граф еще должен быть связным.
А вообще спасибо за статью, интересно.
Есть карточный фокус, который основан на де Брёйне: www.math.ubc.ca/~anstee/math443/DeBruijnCardTrick.pdf
Предположение, что умножение n-битных чисел выполняется за O(1) означает, что n ограничено.
Но тогда и традиционный двоичный поиск — решение за O(1) (с коэффициентом log n).
Но тогда и традиционный двоичный поиск — решение за O(1) (с коэффициентом log n).
Если n небольшое, составляем таблицу из 2^n,
результатов, затем за O(1) выбираем в этой таблице
по входному числу как индексу.
результатов, затем за O(1) выбираем в этой таблице
по входному числу как индексу.
А количество бит лучше считать как-нибудь так:
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;
Пока кто-нибудь не изобретёт 64-битный процессор.
UFO just landed and posted this here
А потом кто-то изобретёт 128-битный процессор. На нём этот код будет продолжать компилироваться без ошибок и предупреждений, но работать не всегда правильно. Как код от Ариан-4 на Ариан-5.
А приведённый автором код из книжки Кернигана и Ричи будет продолжать работать без изменений на любом процессоре, от PDP-11 до самых современных. Вне зависимости от набора инструкций. И скорость выполнения у него та же O(1).
А приведённый автором код из книжки Кернигана и Ричи будет продолжать работать без изменений на любом процессоре, от PDP-11 до самых современных. Вне зависимости от набора инструкций. И скорость выполнения у него та же O(1).
Такая совместимость со всеми возможными процессорами нужна наверно разве что ядру линукса. Большинство программ пишется и умирает гораздо быстрее чем живёт одно поколение процессоров.
Скорее наоборот, такого рода оптимизация имеет смысл разве что в ядре операционной системы или в компиляторе (которые всё равно пишутся или по крайней мере подгоняются под конкретный процессор).
А в прикладных программах эти трюки попадают под определение premature optimization.
А в прикладных программах эти трюки попадают под определение premature optimization.
Зависит от частоты применения подобного рода функции в прикладной программе. Если я использую это, скажем, для расчёта весов нейросети из тысяч нейронов, оптимизация лишней не будет.
На таком уровне оптимизация имеет смысл на компиляторах, а не на компилируемых программах. Так, поддержка popcount есть как в GCC, так и в Clang. А вот ни один из вышеприведённых способов ни GCC, ни Clang довести до инструкции POPCNT не смогли.
А потом кто-то изобретёт 128-битный процессор.К этому есть какие-то предпосылки? Если 64 бита ещё как-то были оправданы адресацией памяти и расчётами с числами двойной точности, то применения 128-битам в ближайшие лет 20 я лично придумать не могу (даже с учётом предположения о росте требуемых объёмов памяти пропорционально росту вычислительных возможностей по закону Мура).
А всякая криптография? С какой разрядностью ей приходится работать?
64 бит не хватает даже чтобы написать «наивную» арифметику по модулю больше, чем 2^32. Или в других ситуациях, когда надо посчитать a*b/c, но не хочется уходить от целых чисел.
64 бит не хватает даже чтобы написать «наивную» арифметику по модулю больше, чем 2^32. Или в других ситуациях, когда надо посчитать a*b/c, но не хочется уходить от целых чисел.
А «всякая криптография» у нас уже либо достаточно заоптимизирована, чтобы не замечать её выполнение на текущих процессорах, либо вынесена в отдельные железные модули в случае, если требуется высокая пропускная способность при низкой нагрузке на CPU. Потому для конечных пользователей эта проблема стоит не очень остро даже с учётом запросов бизнеса.
вводить 128 бит будут маркетологи, они оправдают, без оглядки на Ваше мнение. Хотя как по мне — давно пора, есть ряд алгоритмов, которые значительно упростятся, имей они такое виртуальное адресное пространство.
UFO just landed and posted this here
Зачем, если есть popcnt? software.intel.com/en-us/node/512035
Вообще говоря, сложность какого-то алгоритма имеет смысл только при указании вычислительной модели. Вы посчитали, как я понимаю, для модели RAM, но, увы, для реальных компьютеров все немного хуже — с длиной числа нужно будет считаться (по сути, количество бит числа будет тем самым n). А за счет умножения у вас даже линейной сложности не выйдет.
Тем не менее, для n=32 или 64 этот алгоритм может работать быстрее «стандартного» на тех процессорах, которые умеют умножать быстро.
И это не совсем верно. Важно понимать, что 64-битные процессоры не смогут быстро и верно перемножить два 64-битных числа в общем случае, ведь их произведение будет занимать больше, чем 64 бита. С уверенностью мы можем говорить лишь про n <= 15 и n <= 31 соответственно.
Для таких чисел мы бинпоиском можем определить степень за, соответственно, 4 и 5 сравнений. Вы уверены, что это медленней чем все действия по алгоритму?
Для таких чисел мы бинпоиском можем определить степень за, соответственно, 4 и 5 сравнений. Вы уверены, что это медленней чем все действия по алгоритму?
Наверное, это будет для вас сюрпризом — но операция
mul/imul, примененная к 64х-разрядным операндам, дает 128и-битный результат. Тот факт, что старшая часть чаще всего отбрасывается, обусловлен системой типов языков высокого уровня, но на низком уровне такой проблемы не стоит.под разрядностью процессора как правило понимают разрядность его интерфейса — разрядность адресуемого пространства и разрядность шины. Внутри процессора может твориться все что угодно. Более того, оно там творится, и уже достаточно давно(по крайней мере для x86 семейства)
UFO just landed and posted this here
А мог бы кто-нибудь обяснить что такое «за О(1)»?
Sign up to leave a comment.
Как найти показатель степени двойки за O(1) с помощью последовательности де Брёйна