Должен ли я использовать умножение или деление?

Здесь глупый забавный вопрос:

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

y = x / 2.0;
// or...
y = x * 0.5;

Предполагая, что мы используем стандартные операторы, снабженные языком, который имеет лучшую производительность?

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

Хотя лично я заинтересован в ответе на Python 2.4-2.5, не стесняйтесь также публиковать ответ на другие языки! И если вы хотите, не стесняйтесь публиковать другие причудливые способы (например, с помощью операторов побитового сдвига).

Ответ 1

Python:

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0'
real    0m26.676s
user    0m25.154s
sys     0m0.076s

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5'
real    0m17.932s
user    0m16.481s
sys     0m0.048s

умножение на 33% быстрее

Lua:

time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m7.956s
user    0m7.332s
sys     0m0.032s

time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m7.997s
user    0m7.516s
sys     0m0.036s

= > нет реальной разницы

LuaJIT:

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m1.921s
user    0m1.668s
sys     0m0.004s

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m1.843s
user    0m1.676s
sys     0m0.000s

= > он только на 5% быстрее

выводы: в Python он быстрее умножается, чем делить, но по мере приближения к процессору с использованием более продвинутых виртуальных машин или JIT преимущество исчезает. Вполне возможно, что будущая Python VM сделает ее неактуальной.

Ответ 2

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

Преждевременная оптимизация - это корень всего зла. Всегда помните три правила оптимизации!

Не оптимизируйте.
Если вы специалист, см. правило № 1
Если вы специалист и можете обосновать необходимость, используйте следующую процедуру:
- Код не оптимизирован
- определить, насколько быстро "достаточно быстро" - обратите внимание на то, какой пользовательский запрос/история требует этой метрики.
- Напишите тест скорости
- Проверка существующего кода. Если это достаточно быстро, вы все равно.
- Оптимизировать его перекодировку
- Тестировать оптимизированный код. ЕСЛИ он не соответствует метрике, выбросьте его и сохраните оригинал.
- Если он соответствует тесту, сохраните исходный код в виде комментариев

Кроме того, делать такие вещи, как удаление внутренних циклов, когда они не требуются, или выбор связанного списка по массиву для сортировки вставки не являются оптимизациями, просто программированием.

Ответ 3

Я думаю, что это настолько неудобно, что вам будет лучше делать то, что делает код более читаемым. Если вы не выполняете операции тысячи, если не миллионы, раз, я сомневаюсь, что кто-нибудь заметит разницу.

Если вам действительно нужно сделать выбор, бенчмаркинг - единственный способ пойти. Найдите, какие функции задают вам проблемы, а затем выясните, где в функции возникают проблемы, и исправьте эти разделы. Тем не менее, я все же сомневаюсь, что одна математическая операция (даже повторенная много раз) будет причиной любого узкого места.

Ответ 4

Умножение происходит быстрее, деление более точное. Вы потеряете некоторую точность, если ваш номер не равен 2:

y = x / 3.0;
y = x * 0.333333;  // how many 3 should there be, and how will the compiler round?

Даже если вы позволите компилятору определить инвертированную константу для достижения максимальной точности, ответ все равно может быть другим.

x = 100.0;
x / 3.0 == x * (1.0/3.0)  // is false in the test I just performed

Вопрос о скорости, скорее всего, будет иметь значение на языках C/С++ или JIT, и даже тогда, только если операция находится в цикле на узком месте.

Ответ 5

Если вы хотите оптимизировать свой код, но все равно быть понятным, попробуйте следующее:

y = x * (1.0 / 2.0);

Компилятор должен иметь возможность выполнять разделение во время компиляции, поэтому вы получаете умножение во время выполнения. Я бы ожидал, что точность будет такой же, как в случае y = x / 2.0.

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

Ответ 6

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

Я собрал сборку без оптимизаций и посмотрел на результат.
Код:

int main() {

    volatile int a;
    volatile int b;

    asm("## 5/2\n");
    a = 5;
    a = a / 2;

    asm("## 5*0.5");
    b = 5;
    b = b * 0.5;

    asm("## done");

    return a + b;

}

скомпилирован с gcc tdiv.c -O1 -o tdiv.s -S

деление на 2:

movl    $5, -4(%ebp)
movl    -4(%ebp), %eax
movl    %eax, %edx
shrl    $31, %edx
addl    %edx, %eax
sarl    %eax
movl    %eax, -4(%ebp)

и умножение на 0,5:

movl    $5, -8(%ebp)
movl    -8(%ebp), %eax
pushl   %eax
fildl   (%esp)
leal    4(%esp), %esp
fmuls   LC0
fnstcw  -10(%ebp)
movzwl  -10(%ebp), %eax
orw $3072, %ax
movw    %ax, -12(%ebp)
fldcw   -12(%ebp)
fistpl  -16(%ebp)
fldcw   -10(%ebp)
movl    -16(%ebp), %eax
movl    %eax, -8(%ebp)

Однако, когда я изменил те int на double (что, вероятно, сделает python), я получил следующее:

раздел:

flds    LC0
fstl    -8(%ebp)
fldl    -8(%ebp)
flds    LC1
fmul    %st, %st(1)
fxch    %st(1)
fstpl   -8(%ebp)
fxch    %st(1)

умножение:

fstpl   -16(%ebp)
fldl    -16(%ebp)
fmulp   %st, %st(1)
fstpl   -16(%ebp)

Я не тестировал какой-либо из этого кода, но, просто изучив код, вы можете увидеть, что с использованием целых чисел деление на 2 короче, чем умножение на 2. Используя удвоения, умножение короче, потому что компилятор использует процессорную точку с плавающей запятой opcodes, которые, вероятно, работают быстрее (но на самом деле я не знаю), чем не используют их для одной и той же операции. Поэтому в конечном итоге этот ответ показал, что производительность умножения на 0,5 против деления на 2 зависит от реализации языка и платформы, на которой он работает. В конечном счете разница незначительна и это то, о чем вы никогда не должны беспокоиться, кроме как с точки зрения удобочитаемости.

В качестве побочной заметки вы можете видеть, что в моей программе main() возвращается a + b. Когда я удаляю ключевое слово volatile, вы никогда не догадаетесь, что похоже на сборку (исключая настройку программы):

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

он выполнял как деление, умножение, так и добавление в одну инструкцию! Ясно, что вам не нужно беспокоиться об этом, если оптимизатор является каким-то респектабельным.

Извините за слишком длинный ответ.

Ответ 7

Напишите, что более четко заявляет о ваших намерениях.

После того, как ваша программа работает, выясните, что медленно, и сделайте это быстрее.

Не делайте этого наоборот.

Ответ 8

Сделайте все, что вам нужно. Сначала подумайте о своем читателе, не беспокойтесь о производительности, пока не убедитесь, что у вас проблемы с производительностью.

Пусть компилятор выполнит вашу работу.

Ответ 9

Во-первых, если вы не работаете в C или ASSEMBLY, вы, вероятно, находитесь на языке более высокого уровня, где память останавливается и общие накладные расходы на вызов будут абсолютно затмевать разницу между умножением и делением до точки неуместности. Итак, просто выберите то, что читается лучше в этом случае.

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

Если вам все еще интересно, с точки зрения оптимизации низкого уровня:

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

Как долго разница в конвейере полностью зависит от оборудования. Последнее оборудование, которое я использовал, было чем-то вроде 9 циклов для умножения FPU и 50 циклов для разделения FPU. Звучит много, но тогда вы потеряете 1000 циклов для промаха памяти, чтобы можно было перенести вещи в перспективе.

Аналогия ставит пирог в микроволновую печь, когда вы смотрите телешоу. Общее время, которое потребовалось вам от телешоу, это то, как долго это было, чтобы положить его в микроволновку и вытащить из микроволновой печи. Остальное время вы все еще смотрели телешоу. Так что если пирог потратил 10 минут на то, чтобы приготовить вместо 1 минуты, он больше не использовал ваше время для просмотра телевизора.

На практике, если вы достигнете уровня заботы о различии между Multiply и Divide, вам нужно понять конвейеры, кеш, ветки ветвей, предсказания вне порядка и зависимости конвейера. Если это не похоже на то, где вы намеревались пойти с этим вопросом, тогда правильный ответ - игнорировать разницу между ними.

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

Ответ 10

Если вы работаете с целыми числами или типами без плавающей запятой, не забывайте о ваших операторах с битрейтом: < < →

    int y = 10;
    y = y >> 1;
    Console.WriteLine("value halved: " + y);
    y = y << 1;
    Console.WriteLine("now value doubled: " + y);

Ответ 11

Умножение обычно быстрее - конечно, никогда не медленнее. Однако, если это не критическая скорость, напишите, что лучше всего.

Ответ 12

Деление с плавающей запятой (обычно) особенно медленное, поэтому, хотя умножение с плавающей запятой также относительно медленное, оно, вероятно, быстрее, чем деление с плавающей запятой.

Но я больше склонен отвечать "на самом деле это не имеет значения", если профилирование не показало, что разделение является небольшим узким местом против умножения. Я предполагаю, однако, что выбор умножения или деления не будет иметь большого эффекта производительности в вашем приложении.

Ответ 13

На самом деле есть веская причина, что, поскольку общее правило умножения будет быстрее, чем деление. Разделение с плавающей запятой на аппаратное обеспечение выполняется либо с алгоритмами сдвига и условного вычитания ( "длинное деление" с двоичными числами), либо, скорее, в эти дни - с итерациями типа Goldschmidt's. Для сдвига и вычитания требуется, по меньшей мере, один цикл на бит точности (итерации почти невозможно распараллеливать, как и сдвиг и добавление умножения), а итеративные алгоритмы выполняют по крайней мере одно умножение на итерацию. В любом случае очень вероятно, что в подразделении будет больше циклов. Конечно, это не учитывает причуды в компиляторах, перемещение данных или точность. В общем, если вы кодируете внутренний цикл во временной области программы, писать 0.5 * x или 1.0/2.0 * x, а не x / 2.0, это разумная вещь. Педантизм "кода, который ясен" абсолютно прав, но все три из них настолько близки по читаемости, что педантизм в этом случае просто педантичен.

Ответ 14

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

Ответ 15

Будьте осторожны с "угадыванием умножения, как правило, лучше, поэтому я стараюсь придерживаться этого при кодировании",

В контексте этого конкретного вопроса лучше здесь означает "быстрее". Это не очень полезно.

Мышление о скорости может быть серьезной ошибкой. В конкретной алгебраической форме расчета имеются глубокие ошибки.

См. Арифметика с плавающей точкой с анализом ошибок. См. Основные проблемы в арифметике с плавающей точкой и анализ ошибок.

Хотя некоторые значения с плавающей запятой являются точными, большинство значений с плавающей запятой являются приблизительными; они являются некоторым идеальным значением плюс некоторая ошибка. Каждая операция применяется к идеальному значению и значению ошибки.

Самые большие проблемы связаны с попыткой манипулировать двумя почти равными числами. Наименьшие биты (биты ошибок) становятся доминирующими в результатах.

>>> for i in range(7):
...     a=1/(10.0**i)
...     b=(1/10.0)**i
...     print i, a, b, a-b
... 
0 1.0 1.0 0.0
1 0.1 0.1 0.0
2 0.01 0.01 -1.73472347598e-18
3 0.001 0.001 -2.16840434497e-19
4 0.0001 0.0001 -1.35525271561e-20
5 1e-05 1e-05 -1.69406589451e-21
6 1e-06 1e-06 -4.23516473627e-22

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

Ответ 16

Я всегда узнал, что умножение более эффективно.

Ответ 17

Я где-то читал, что умножение более эффективно в C/С++; Не знаю, что касается интерпретируемых языков - разница, вероятно, незначительна из-за всех других накладных расходов.

Если это не проблема с тем, что более удобно или удобочитаемо, я ненавижу, когда люди говорят мне об этом, но это так.

Ответ 18

Я бы предложил умножение в целом, потому что вам не нужно тратить циклы, гарантируя, что ваш делитель не равен 0. Это, конечно, не применяется, если ваш делитель является константой.

Ответ 19

Как и в сообщениях # 24 (умножение выполняется быстрее) и # 30, но иногда они так же легко понятны:

1*1e-6F;

1/1e6F;

~ Я нахожу их и такими же легко читаемыми, и их нужно повторять в миллиарды раз. Поэтому полезно знать, что умножение обычно выполняется быстрее.

Ответ 20

Java-андроид, профилированный на Samsung GT-S5830

public void Mutiplication()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a *= 0.5f;
    }
}
public void Division()
{
    float a = 1.0f;

    for(int i=0; i<1000000; i++)
    {
        a /= 2.0f;
    }
}

Результаты?

Multiplications():   time/call: 1524.375 ms
Division():          time/call: 1220.003 ms

Разделение на 20% быстрее, чем умножение (!)

Ответ 21

Есть разница, но зависит от компилятора. Сначала на vs2003 (С++) я не получил существенной разницы для двойных типов (64-битная с плавающей запятой). Однако, повторив тесты на vs2010, я обнаружил огромную разницу, до коэффициента 4 быстрее для умножения. Отслеживая это, кажется, что vs2003 и vs2010 генерируют разные коды fpu.

На Pentium 4, 2.8 ГГц, vs2003:

Умножение: 8.09
Отдел: 7.97

На Xeon W3530, vs2003:

Умножение: 4.68
Отдел: 4.64

На Xeon W3530, vs2010:

Умножение: 5.33
Отдел: 21.05

Кажется, что на vs2003 деление в цикле (так что делитель использовалось несколько раз) было переведено на умножение с помощью обратного. На vs2010 эта оптимизация больше не применяется (я полагаю, потому что между этими двумя методами есть несколько иной результат). Также обратите внимание, что процессор быстрее выполняет деления, как только ваш числитель равен 0.0. Я не знаю, какой именно алгоритм установлен в чипе, но, возможно, он зависит от числа.

Редактировать 18-03-2013: наблюдение за vs2010

Ответ 22

Хорошо, если предположить, что операция add/subtrack стоит 1, затем умножает затраты 5 и делит затраты примерно на 20.

Ответ 23

После такой длинной и интересной дискуссии здесь я беру на себя следующее: окончательного ответа на этот вопрос нет. Как указывали некоторые люди, это зависит от обоих: аппаратного обеспечения (cf piotrk и gast128) и компилятор (cf @Javier). Если скорость не является критичной, если вашему приложению не нужно обрабатывать огромные объемы данных в режиме реального времени, вы можете выбрать ясность с помощью деления, тогда как если скорость обработки или загрузка процессора будут проблемой, умножение может быть самым безопасным. Наконец, если вы точно не знаете, на какой платформе будет развернуто ваше приложение, то эталонность не имеет смысла. И для ясности кода один комментарий будет выполнять эту работу!

Ответ 24

Технически нет такой вещи, как деление, есть просто умножение на обратные элементы. Например, вы никогда не делите на 2, вы на самом деле умножаетесь на 0,5.

"Разделение" - пусть насчет того, что он существует на секунду - всегда сложнее умножение, потому что для "деления" x на y сначала нужно вычислить значение y^{-1} такое, что y*y^{-1} = 1 и то сделайте умножение x*y^{-1}. Если вы уже знаете y^{-1}, то не вычислять его из y должна быть оптимизация.