Big-O дивизии

Что такое большое деление на большинстве современных ISA? Есть ли какая-то оптимизация или это наивный O (числитель/знаменатель)? Я пишу код, который сильно зависит от работы модуля.

Например, какое относительное время требуется для выполнения 10/5, 20/5 и 40/5? Имеют ли современные процессоры от Intel, nVidia, Qualcomm и т.д. одинаковую Big-O для деления?

ПРИМЕЧАНИЕ. Я могу ошибаться, полагая, что деление равно O (размер числителя), и этот вопрос может вообще не иметь смысла. Пожалуйста, поправьте меня, если это так.


architecture algorithm big-o division integer-division
person user1210233    schedule 18.01.2013    source источник
comment
Для целочисленного деления оно обычно является постоянным, но имеет высокую стоимость задержки.   -  person Paul R    schedule 18.01.2013
comment
Я думаю, что все математические операции имеют большой О, равный 1.   -  person mamdouh alramadan    schedule 18.01.2013
comment
Не зависит ли это также от используемого алгоритма деления? en.wikipedia.org/wiki/Division_%28electronics%29   -  person sr01853    schedule 18.01.2013
comment
@mamdouhalramadan только потому, что ввод имеет фиксированный размер, но это обман. Вы могли бы также сказать, что указатели имеют фиксированный размер, поэтому итерация по связанному списку (без циклов) - это O (1), потому что существует постоянное максимальное количество узлов, которые он может адресовать. Количество шагов деления также может зависеть от значения входных данных, в зависимости от используемого алгоритма.   -  person harold    schedule 18.01.2013
comment
Просто для ясности: вы спрашиваете о делении одного целого числа фиксированной ширины на другое?   -  person NPE    schedule 18.01.2013
comment
@Sibi: Если рассматривать это как функцию битового размера: да. Но поскольку процессор всегда работает с определенным размером слова, обычно всегда O (1), независимо от того, какой алгоритм вы используете. Это связано с тем, что время выполнения различных алгоритмов зависит от размера данных в битах. Просто введите константу 32- или 64 в формулы времени выполнения, и вы получите постоянное время выполнения для алгоритмов (но внимание: они могут сильно различаться - но это относится только к реальной производительности/времени выполнения, а не к большому O!).   -  person flolo    schedule 18.01.2013
comment
@harold - примечательный момент.   -  person mamdouh alramadan    schedule 18.01.2013
comment
По крайней мере, в процессорах Intel время деления зависит как от значения результата, так и от размера операнда (т. е. небольшие результаты вычисляются быстрее, но 64-битное деление медленнее, чем 32-битное, даже для одного и того же результата).   -  person harold    schedule 18.01.2013
comment
Если вы используете тип с неограниченной шириной, Big-O — лучший подход к суммированию влияния увеличения размера операнда на операции. Если вы имеете дело с фиксированным типом with, таким как 32- или 64-битные встроенные типы, обрабатывайте их как O(1), но константа имеет значение для разумных размеров задач и может зависеть от типа.   -  person Patricia Shanahan    schedule 18.01.2013

Ответы (1)


arrow_upward
2
arrow_downward

Этот вопрос не так хорош. Но это тоже не так уж и "глупо", поэтому попробую ответить/уточнить некоторые моменты:

Почти все современные CPU/GPU имеют инструкцию деления. Поскольку он работает с размером слова по умолчанию, не имеет значения, насколько быстро он работает, с точки зрения Big-O он постоянен, поэтому всегда O (1). Это верно даже для встроенных процессоров, микроконтроллеров и т.п., в которых нет команды деления, поскольку она эмулируется в программном обеспечении, а программная эмуляция связана с размером слова, поэтому всегда требуется постоянное время для выполнения операции. операция (это означает, что это также O (1)).

Исключение составляют операции, выполняемые с данными, отличными от слова. Это происходит, например. когда речь идет о библиотеках BigInt. Но в этом случае ВСЕ операции (сложение, умножение,...) больше не O(1), а зависят от размера чисел.

Но внимание: Big-O ничего не говорит о реальном времени вычислений. Это просто асимптотическое поведение без учета постоянного фактора. Это означает, что даже если у вас есть два алгоритма, которые принимают O(n), разница во времени может быть в 1000 раз (или в миллион, или сколько угодно). Лучший пример деления: это, например. сложение - оба O (1), но обычно деление занимает гораздо больше циклов/времени для выполнения, чем сложение.

person flolo    schedule 18.01.2013
comment
как насчет долго в java? На 32-битной машине размер слова будет вдвое больше. У него все еще есть время выполнения O (1)? - person user1210233; 18.01.2013
comment
Даже если на машине нет 64-битной инструкции div, это будет O (1), так как всегда будет постоянное количество операций для выполнения/эмуляции 64-битной div с 32-битными инструкциями. Но опять же: O-класс тот же, но разница в реальном времени выполнения составляет примерно 3-6 раз (просто предположение, может быть больше или меньше, сильно зависит от используемой платформы/системы). - person flolo; 18.01.2013
comment
Также следует упомянуть об амортизированной сложности. Я не знаю о других операциях, но сложение амортизируется O (1). - person Paul Manta; 19.01.2013