Devo usar multiplicação ou divisão?

Aqui está uma pergunta boba e divertida:

Digamos que tenhamos que realizar uma operação simples em que precisamos da metade do valor de uma variável. Normalmente, existem duas maneiras de fazer isso:

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

Supondo que estejamos usando os operadores padrão fornecidos com a linguagem, qual deles tem melhor desempenho?

Suponho que a multiplicação normalmente é melhor, então tento mantê-la ao codificar, mas gostaria de confirmar isso.

Embora pessoalmente eu esteja interessado na resposta para Python 2.4-2.5, fique à vontade para postar uma resposta para outras linguagens! E se desejar, sinta-se à vontade para postar outras maneiras mais elaboradas (como usar operadores de mudança bit a bit) também.

Pitão:

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

multiplicação é 33% mais rápida

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

=> nenhuma diferença real

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

=> é apenas 5% mais rápido

Conclusões: em Python é mais rápido multiplicar do que dividir, mas à medida que você se aproxima da CPU usando VMs ou JITs mais avançados, a vantagem desaparece. É bem possível que uma futura VM Python a torne irrelevante

Sempre use o que for mais claro. Qualquer outra coisa que você faça é tentar ser mais esperto que o compilador. Se o compilador for inteligente, fará o melhor para otimizar o resultado, mas nada pode fazer o próximo cara não odiar você por sua solução de deslocamento de bits de baixa qualidade (eu adoro manipulação de bits, a propósito, é divertido. Mas divertido! = Legível )

Otimização prematura é a raiz de todo o mal. Lembre-se sempre das três regras de otimização!

1. Não otimize.
2. Se você for um especialista, consulte a regra nº 1

3. Se você for um especialista e puder justificar a necessidade, use o seguinte procedimento:

   • Codifique não otimizado
   • determinar quão rápido é "Rápido o suficiente" - Observe qual requisito / história do usuário requer essa métrica.
   • Escreva um teste de velocidade
   • Teste o código existente - se for rápido o suficiente, está feito.
   • Recodifique-o otimizado
   • Teste o código otimizado. SE não atender à métrica, jogue fora e guarde o original.
   • Se passar no teste, mantenha o código original como comentários

Além disso, fazer coisas como remover loops internos quando não são necessários ou escolher uma lista vinculada em um array para uma classificação por inserção não são otimizações, apenas programação.

Acho que isso está ficando tão minucioso que seria melhor você fazer o que quer que torne o código mais legível. A menos que você execute as operações milhares, senão milhões, de vezes, duvido que alguém notará a diferença.

Se você realmente precisa fazer uma escolha, o benchmarking é o único caminho a percorrer. Descubra quais funções estão causando problemas e, em seguida, descubra onde os problemas ocorrem na função e corrija essas seções. No entanto, ainda duvido que uma única operação matemática (mesmo uma repetida muitas e muitas vezes) seria a causa de qualquer gargalo.

A multiplicação é mais rápida, a divisão é mais precisa. Você perderá alguma precisão se seu número não for uma potência de 2:

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

Mesmo se você deixar o compilador descobrir a constante invertida com precisão perfeita, a resposta ainda pode ser diferente.

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

O problema de velocidade provavelmente só importa nas linguagens C / C ++ ou JIT e, mesmo assim, apenas se a operação estiver em um loop em um gargalo.

Se você deseja otimizar seu código, mas ainda é claro, tente isto:

y = x * (1.0 / 2.0);

O compilador deve ser capaz de fazer a divisão em tempo de compilação, para que você obtenha uma multiplicação em tempo de execução. Eu esperaria que a precisão fosse a mesma doy = x / 2.0 case.

Onde isso pode importar, MUITO é em processadores embutidos onde a emulação de ponto flutuante é necessária para calcular a aritmética de ponto flutuante.

Só vou adicionar algo para a opção "outros idiomas".
C: Uma vez que este é apenas um exercício acadêmico que realmente não faz diferença, pensei em contribuir com algo diferente.

Compilei para a montagem sem otimizações e olhei o resultado.
O código:

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;

}

compilado com gcc tdiv.c -O1 -o tdiv.s -S

a divisão por 2:

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

e a multiplicação por 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)

No entanto, quando eu mudei aqueles int s paradouble s (que é o que provavelmente o python faria), obtive o seguinte:

divisão:

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

multiplicação:

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

Não fiz benchmark de nenhum deste código, mas apenas examinando o código, você pode ver que usando inteiros, a divisão por 2 é mais curta do que a multiplicação por 2. Usando duplas, a multiplicação é mais curta porque o compilador usa os opcodes de ponto flutuante do processador, que provavelmente correr mais rápido (mas na verdade eu não sei) do que não usá-los para a mesma operação. Portanto, em última análise, essa resposta mostrou que o desempenho da multiplicação por 0,5 vs. divisão por 2 depende da implementação da linguagem e da plataforma em que ela é executada. Em última análise, a diferença é insignificante e é algo com que você nunca deve se preocupar, exceto em termos de legibilidade.

Como observação lateral, você pode ver que no meu programa main()retorna a + b. Quando eu remover a palavra-chave volatile, você nunca adivinhará a aparência do assembly (excluindo a configuração do programa):

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

ele fez a divisão, multiplicação e adição em uma única instrução! Obviamente, você não precisa se preocupar com isso se o otimizador for respeitável.

Desculpe pela resposta excessivamente longa.

Em primeiro lugar, a menos que você esteja trabalhando em C ou ASSEMBLY, você provavelmente está em uma linguagem de nível superior, onde a memória travada e sobrecargas de chamadas gerais irão absolutamente diminuir a diferença entre multiplicar e dividir ao ponto da irrelevância. Portanto, basta escolher o que é melhor nesse caso.

Se você estiver falando de um nível muito alto, não será mensuravelmente mais lento para qualquer coisa para a qual você possa usá-lo. Você verá em outras respostas, as pessoas precisam multiplicar / dividir um milhão apenas para medir alguma diferença de submilissegundo entre os dois.

Se você ainda estiver curioso, do ponto de vista de otimização de baixo nível:

O Divide tende a ter um pipeline significativamente mais longo do que o Multiply. Isso significa que leva mais tempo para obter o resultado, mas se você puder manter o processador ocupado com tarefas não dependentes, isso não custará mais do que uma multiplicação.

O tamanho da diferença de pipeline depende totalmente do hardware. O último hardware que usei foi algo como 9 ciclos para uma multiplicação de FPU e 50 ciclos para uma divisão de FPU. Parece muito, mas você perderia 1000 ciclos por uma perda de memória, então isso pode colocar as coisas em perspectiva.

Uma analogia é colocar uma torta no microondas enquanto você assiste a um programa de TV. O tempo total que você levou para longe do programa de TV é quanto tempo foi para colocá-lo no micro-ondas e tirá-lo do micro-ondas. O resto do tempo você ainda assistia ao programa de TV. Portanto, se a torta levasse 10 minutos para cozinhar em vez de 1 minuto, ela não consumia mais o tempo de exibição da TV.

Na prática, se você chegar ao nível de se preocupar com a diferença entre Multiply e Divide, precisará entender pipelines, cache, paralisações de ramificação, predição fora de ordem e dependências de pipeline. Se isso não soa como você pretendia chegar com essa pergunta, a resposta correta é ignorar a diferença entre as duas.

Muitos (muitos) anos atrás, era absolutamente crítico evitar divisões e sempre usar multiplicações, mas naquela época os acertos de memória eram menos relevantes e as divisões eram muito piores. Hoje em dia eu dou um valor mais alto à legibilidade, mas se não houver diferença na legibilidade, acho um bom hábito optar por multiplicar.

Escreva o que declarar mais claramente sua intenção.

Depois que seu programa funcionar, descubra o que é lento e torne-o mais rápido.

Não faça o contrário.

Faça o que você precisar. Pense no seu leitor primeiro, não se preocupe com o desempenho até ter certeza de que há um problema de desempenho.

Deixe o compilador fazer o desempenho para você.

Se você estiver trabalhando com inteiros ou tipos de ponto não flutuante, não se esqueça dos operadores de bitshifting: << >>

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

Na verdade, há uma boa razão para que, como regra geral, a multiplicação seja mais rápida do que a divisão. A divisão de ponto flutuante no hardware é feita com algoritmos de mudança e subtração condicional ("divisão longa" com números binários) ou - mais provavelmente hoje em dia - com iterações como a de Goldschmidt algoritmo . Shift e subtract precisam de pelo menos um ciclo por bit de precisão (as iterações são quase impossíveis de paralelizar, assim como o shift-and-add da multiplicação), e algoritmos iterativos fazem pelo menos uma multiplicação por iteração. Em ambos os casos, é altamente provável que a divisão leve mais ciclos. É claro que isso não leva em consideração peculiaridades em compiladores, movimentação de dados ou precisão. De modo geral, entretanto, se você estiver codificando um loop interno em uma parte sensível ao tempo de um programa, escrever 0.5 * xou, 1.0/2.0 * xao invés disso, x / 2.0é uma coisa razoável a se fazer. O pedantismo de "codificar o que é mais claro" é absolutamente verdadeiro, mas todos os três são tão próximos em legibilidade que o pedantismo, neste caso, é apenas pedante.

Sempre aprendi que a multiplicação é mais eficiente.

A multiplicação geralmente é mais rápida - certamente nunca mais lenta. No entanto, se não for crítico para a velocidade, escreva o que estiver mais claro.

A divisão de ponto flutuante é (geralmente) especialmente lenta, portanto, embora a multiplicação de ponto flutuante também seja relativamente lenta, é provavelmente mais rápida do que a divisão de ponto flutuante.

Mas estou mais inclinado a responder "isso realmente não importa", a menos que a criação de perfil tenha mostrado que a divisão é um pequeno gargalo em relação à multiplicação. Estou supondo, porém, que a escolha de multiplicação versus divisão não terá um grande impacto no desempenho de seu aplicativo.

Isso se torna mais problemático quando você está programando em assembly ou talvez em C. Acho que, com a maioria das linguagens modernas, essa otimização está sendo feita para mim.

Desconfie de "adivinhar que a multiplicação é normalmente melhor, então tento segui-la quando codifico",

No contexto desta questão específica, melhor aqui significa "mais rápido". O que não é muito útil.

Pensar em velocidade pode ser um erro sério. Existem profundas implicações de erro na forma algébrica específica do cálculo.

Consulte aritmética de ponto flutuante com análise de erro . Consulte Problemas básicos em aritmética de ponto flutuante e análise de erros .

Embora alguns valores de ponto flutuante sejam exatos, a maioria dos valores de ponto flutuante é uma aproximação; eles são algum valor ideal mais algum erro. Cada operação se aplica ao valor ideal e ao valor de erro.

Os maiores problemas vêm de tentar manipular dois números quase iguais. Os bits mais à direita (os bits de erro) passam a dominar os resultados.

>>> 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

Neste exemplo, você pode ver que, à medida que os valores ficam menores, a diferença entre números quase iguais cria resultados diferentes de zero em que a resposta correta é zero.

Eu li em algum lugar que a multiplicação é mais eficiente em C / C ++; Nenhuma ideia sobre idiomas interpretados - a diferença é provavelmente insignificante devido a todas as outras despesas gerais.

A menos que se torne um problema, fique com o que é mais fácil de manter / legível - eu odeio quando as pessoas me dizem isso, mas é tão verdade.

Eu sugeriria a multiplicação em geral, porque você não precisa gastar os ciclos garantindo que seu divisor não seja 0. Isso não se aplica, é claro, se seu divisor for uma constante.

Android Java, perfilado em 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;
    }
}

Resultados?

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

A divisão é cerca de 20% mais rápida do que a multiplicação (!)

Tal como acontece com os posts # 24 (a multiplicação é mais rápida) e # 30 - mas às vezes ambos são igualmente fáceis de entender:

1*1e-6F;

1/1e6F;

Acho que ambos são fáceis de ler e tenho que repeti-los bilhões de vezes. Portanto, é útil saber que a multiplicação geralmente é mais rápida.

Há uma diferença, mas depende do compilador. No início, no vs2003 (c ++), não obtive diferença significativa para os tipos duplos (ponto flutuante de 64 bits). No entanto, executando os testes novamente no vs2010, detectei uma grande diferença, até fator 4 mais rápido para multiplicações. Rastreando isso, parece que o vs2003 e o vs2010 geram um código fpu diferente.

Em um Pentium 4, 2,8 GHz, vs2003:

• Multiplicação: 8,09
• Divisão: 7,97

Em um Xeon W3530, vs2003:

• Multiplicação: 4,68
• Divisão: 4,64

Em um Xeon W3530, vs2010:

• Multiplicação: 5,33
• Divisão: 21,05

Parece que no vs2003 uma divisão em um loop (então o divisor foi usado várias vezes) foi convertida em uma multiplicação com o inverso. No vs2010, essa otimização não é mais aplicada (suponho que seja porque há um resultado ligeiramente diferente entre os dois métodos). Observe também que a CPU realiza divisões mais rápido assim que o numerador for 0,0. Não sei o algoritmo preciso conectado ao chip, mas talvez dependa do número.

Editar 18-03-2013: a observação para vs2010

Aqui está uma resposta boba e divertida:

x / 2.0 não é equivalente a x * 0,5

Digamos que você escreveu esse método em 22 de outubro de 2008.

double half(double x) => x / 2.0;

Agora, 10 anos depois, você aprende que pode otimizar esse trecho de código. O método é referenciado em centenas de fórmulas em todo o seu aplicativo. Então, você o altera e experimenta uma notável melhoria de desempenho de 5%.

double half(double x) => x * 0.5;

Foi a decisão certa alterar o código? Em matemática, as duas expressões são realmente equivalentes. Na ciência da computação, isso nem sempre é verdade. Leia Minimizando o efeito dos problemas de precisão para obter mais detalhes. Se seus valores calculados forem - em algum ponto - comparados com outros valores, você mudará o resultado dos casos extremos. Por exemplo:

double quantize(double x)
{
    if (half(x) > threshold))
        return 1;
    else
        return -1;
}

Resumindo; uma vez que você se contentar com qualquer um dos dois, mantenha-o!

Bem, se assumirmos que uma operação adicionar / subtrair custa 1, então multiplique os custos 5 e divida os custos por cerca de 20.

Depois de uma discussão tão longa e interessante, aqui está minha opinião sobre isso: Não há uma resposta final para essa pergunta. Como algumas pessoas apontaram, isso depende de ambos, do hardware (cf piotrk e gast128 ) e do compilador (cf @Javier 's tests). Se a velocidade não for crítica, se seu aplicativo não precisar processar em tempo real uma grande quantidade de dados, você pode optar pela clareza usando uma divisão, enquanto se a velocidade de processamento ou a carga do processador forem um problema, a multiplicação pode ser a mais segura. Finalmente, a menos que você saiba exatamente em qual plataforma seu aplicativo será implementado, o benchmark não tem sentido. E para maior clareza do código, um único comentário faria o trabalho!

Tecnicamente, não existe divisão, existe apenas multiplicação por elementos inversos. Por exemplo, você nunca divide por 2, na verdade você multiplica por 0,5.

'Divisão' - vamos nos enganar que existe por um segundo - é sempre mais difícil que a multiplicação porque para 'dividir' xpor yum primeiro é necessário calcular o valor y^{-1}tal que y*y^{-1} = 1e depois fazer a multiplicação x*y^{-1}. Se você já sabe y^{-1}, não calculá-lo ydeve ser uma otimização.