Почему умножение работает быстрее деления?

Question

[0nk0l0g]

Слышал, что операция умножения работает быстрее операции деления, поэтому лучше умножать на 0.5, чем делить на 2.
Хочу узнать для всех ли языков программирования это справедливо и почему так происходит.
Спасибо.

Answer 1

[Dimonchik]

насчет "лучше умножать на 0,5" хз, потому что плавающая точка, но, наверно да

а так все просто:
современный комп, и комп 20 лет назад, и комп 30 лет назад - это обычный транзистор
(когда изобретут фотонный проц - будет не обычный, хотя..)

а обычный транзистор имеет всего два состояния: 0 (нет напряжения) и 1 (идет ток)

и умеет транзистор этими двумя состояниями всего два действия:
первое: сложение (0+1 = 1, 0+0=0, 1+1 = 01 и т.п.)
второе: смена знака (честно - уже не помню как там куда идет ток в этом случае)

все. больше ничего комп не умеет.

потому арифметика реализуется примерно так:
сложение: первое число СЛОЖ второе число
вычитание: первое число СМЕНЗНАК второе число СЛОЖ первое число
умножение: много раз СЛОЖ и занесение в стек, что тоже СЛОЖ
деление: многораз СЛОЖ и зансение в стек + чуть меньше раз СМЕНЗНАК и снова в стек

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

отсюда же растут ноги у точности плавающей точки - СЛОЖ и СМЕНЗНАК тоже нужно сделать кучу раз в зависимости от точности

Comments

[uvelichitel]

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

[sozercanie_kosmosa]

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

[Dimonchik]

а инвертируется он сам по себе, конечно )) рождается таким

Answer 2

[nirvimel]

Во-первых, это касается только компилируемых ЯП в которых целые и действительные числа представлены нативными типами данных аппаратной платформы. То есть 8/16/32/64-целые и 32/64/80-битные действительные. Все это никаким образом не касается динамических скриптов, а также языков, в которых числа по-умолчанию с длинной арифметикой или пределы значений не указаны в спецификации языка (обычно это означает использование длинной арифметики) - во всех этих случаях вычисления будут идти в десятки/сотни/тысячи раз медленнее чем на голом железе и разницы между умножением и делением (а также другими операциями) не будет заметно вообще.
Во-вторых, даже на компилируемых языках с нативными типами данных, иногда встречаются дополнительные проверки (на переполнение, например) и особые правила применения математических действий, что влияет на производительность гораздо сильнее, чем разница между делением и умножением. Хороший пример - удивительный случай на cython.

Answer 3

[Дмитрий Беляев]

По сути процессор умеет работать только с битами
С целыми числами все выглядит давольно просто:
1й бит числа определяет знак числа - 0 для положительных и 1 для отрицательных
У нас есть операции для управления битами:

• ~ инверсия
  
• & конъюнкция
  
• | дизъюнкция
  
• >> сдвиг вправо
  
• << сдвиг влево
  

введем арифметические операции по порядку:

1. Сложение, сводится по сути к сложению битов в столбик
   
2. Отрицание или смена знака, -a выражается как ~a + 1
   
3. Вычитание a - b выражается через a + -b
   
4. Умножение, тут несколько вариантов, зависит от компилятора и его оптимизатора:
   
   1. Умножение на степени 2 можно представить сдвигом влево: a * 8 приводится к a << 3 т.к. 8 - это 3я степень 2
      
   2. Простые случаи вроде a * 3 можно заменить на a + a + a
      
   3. Случаи по сложнее a * 11 складывать a 11 раз само с собой не оптимально
      раскладываем 11 на степени 2: 11 = 8 + 2 + 1
      вычисляем (a << 3) + (a << 1) + a
      
   
   

С вещественными числами все обстоит сложнее, они тоже представлены в виде битов, но часть битов отводится под целую часть, а часть под мантиссу
По сути число хранится в экспоненциальной форме, где мантисса представляет степень 2, на которую нужно умножить целую часть
Операции над вещественными числами с ненулевой мантиссой более затратны по количеству тактов процессора
Здесь нам понадобятся такие вещи как экспонента и натуральный логарифм, которые можно вычислить в виде суммы ряда, так же через суммы ряда вычисляются многие другие математические функции
Имея экспоненту и логарифм можно выразить степенную функцию
Деление же можно представить через умножение и степени

Вот такая вот высшая математика над двоичными числами происходит "за кадром" наших с виду простых программ :)

Answer 4

[sitev_ru]

Вовсе не обязательно... Вот добился, что умножение работает медленнее, чем деление:

rextester.com/NMZ47337

#include <windows.h>
#include <iostream>
using namespace std;

int main()
{
    cout << "Test mul" << endl;
    int tick1 = GetTickCount();
    
    double a = 1000000000000;
    for (int i = 0; i < 1000000; i++) {
        a *= 0.99;
    }
    
    int tick2 = GetTickCount();
    
    cout << "time = " << tick2 - tick1 << endl;
    cout << a << endl;

    cout << "Test div" << endl;
    tick1 = GetTickCount();
    
    a = 1000000000000;
    for (int i = 0; i < 1000000; i++) {
        a /= 1.0001;
    }
    
    tick2 = GetTickCount();
    
    cout << "time = " << tick2 - tick1 << endl;
    cout << a << endl;
}

Вот такие цифры у меня получились:

Test mul
time = 47
2.42092e-322
Test div
time = 16
3.73872e-32

Умножение медления в три раза)

Comments

[nirvimel]

А вас не смущает, что при добавлении еще восьми нулей к цифре количества итераций цикла время исполнения вашего кода нисколько не меняется (вместо того чтобы зависнуть на годы) ?
rextester.com/CGEIT60937

[sitev_ru]

Нет не смущает... Я просто пытался опровергнуть вопрос "Почему умножение работает быстрее деления?"... Вроде как получилось это сделать, копаться глубже - нет времени...

Answer 5

[Михаил Усоцкий]

Потому что для деления потребуется остаточный результат в промежуточном этапе деления. Поэтому операция всегда будет последовательной. Для сложения, вычитания и умножения можно использовать схемы ускорения за счёт распараллеливания вычисления. С делением такой номер не пройдёт, либо получится громоздкая схема с очень длинным интервалом задержки, что проще делать это последовательно. Поэтому в программировании предпочтительно избегать операций деления, насколько возможно.
P.S. Об этом можно узнать из книг по схемотехнике. Там есть раздел для разбора материала с представлением обработка чисел в ЭВМ.

Answer 6

[uvelichitel]

Не для всех компиляторов, не во всех обстоятельствах, но ДА операция умножения дешевле деления. Просто попробуйте умножать и делить на бумаге в столбик и сразу убедитесь почему.

Answer 7

[Тимур Сергеевич]

Тут не от ЯП зависит, а от компилятора + процессор на котором эти операции происходят.

Answer 8

[BurovAlex88]

Затестил в Benchmark'е. Результаты идентичные

[MemoryDiagnoser]
    [RankColumn]
    public class Operation_Benchmark
    {
        private static float a = 10f, buffer;
        
        private static Random _random = new Random();
        private static Stopwatch _stopwatch = new Stopwatch();
        private static int RandomInt => _random.Next(10);
        
        [Benchmark]
        public void Estimate_Multiply()
        {
            a += RandomInt;
            buffer += a * 0.5f;
        }

        [Benchmark]
        public void Estimate_Division()
        {
            a += RandomInt;
            buffer += a / 2f;
        }
    }