Почему оператор модуля медленный?

Question

Перефразируя из в «Программирование Pearls» книги (о языке С на старых машинах, так как книга с конца 90-х годов):

Integer арифметические операции (+, -, *) может занять около 10 наносекунд в то время как % оператор занимает до 100 наносекундов.

• Почему существует такая разница?
• Как оператор модуля работает внутри?
• Это то же самое, что и деление (/) с точки зрения времени?

Answer 1

Операция модуля/модуля обычно понимается как целочисленный эквивалент операции остатка - побочный эффект или аналог деления.

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

Итак, вопрос в самом деле, почему целое деление так дорого?

У меня нет времени или опыта, чтобы проанализировать это математически, поэтому я собираюсь обратиться к начальной школе по математике:

Рассмотрим число линий работы в записной книжке (не включая входы) требуется для:

• равенства: (булевы операции), по существу нет - в компьютерных «большой O» терминах это известна O (1)
• прибавление: два, не работающие слева направо, по одной строке для выход и одну линию для переноса. Это операция O (N)
• длинное умножение: n * (n + 1) + 2: две строки для каждого из цифровых продуктов (одна общая, одна для переноски) плюс окончательная сумма и перенос. Таким образом, O (N^2), но с фиксированным N (32 или 64), и он может быть конвейеризован в кремнии менее чем
• длинное деление: неизвестно, зависит от размера аргумента - это рекурсивный спуск и некоторые случаи (1,000,000/500,000 требуется меньше линий, чем 1000/7). Также каждый шаг представляет собой, по существу, ряд умножений для изоляции ближайших факторов. (Хотя существуют несколько алгоритмов). Ощущается как O (N^3) с переменным N

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

Если это не имеет никакого отношения к вам; возможно, вы были воспитаны в школьной математике немного более современной, чем моя (30 лет назад).

---

Обозначение заказа/Big O используется выше как O (что-то) выражает сложность вычислений с точки зрения размера его входов и выражает факт о своем времени выполнения. http://en.m.wikipedia.org/wiki/Big_O_notation

O (1) выполняет постоянное (но возможно большое) время.O (N) занимает столько же времени, сколько и размер его данных, поэтому, если данные 32 бита, для вычисления одной из своих N шагов требуется 32 раза времени O (1), а O (N^2) принимает N раз N (N квадратов) время его N шагов (или, возможно, N раз MN для некоторой константы M). И т.д.

---

В приведенной выше работе я использовал O (N), а не O (N^2) для того, так как 32 или 64 бит первого входа вычисляется параллельно центральным процессором. В гипотетической 1-битовой машине операция сложения 32 бит будет равна O (32^2) и изменится. Такое же уменьшение порядка относится и к другим операциям.