34

Pergunta de escovação de bit, mas estava eu lendo um artigo sobre javascript em que diz que divisão é mais lenta que fazer multiplicações.

E por exemplo, recomendava mudar o código abaixo :

var resultado = 4/2;

por esse que seria mais rápido.

var resultado = 4 * .5;

Isso acontece em qualquer linguagem? E por que multiplicar é mais performático que dividir?

Eis o link do artigo (em inglês) que mencionei, na seção Math : http://jessefreeman.com/game-dev/intro-to-programming-for-games-with-javascript/

7
  • 2
    Fiz o teste no console e não reparei diferença alguma Commented 28/03/2014 às 12:42
  • 2
    @SilvioAndorinha Creio que seja perceptível se a execução do código precisa ser repetido inúmeras vezes. Commented 28/03/2014 às 12:47
  • 2
    Criei um teste de performance em JavaScript: jsperf.com/multiply-vs-divide-fight de vez em quando a divisão se mostra mais rápida, então se houver mesmo alguma diferença em Javascript, deve ser insignificante. Commented 28/03/2014 às 13:26
  • 5
    Agora a ironia: a divisão parece ser consistentemente mais rápida do que a multiplicação no Internet Explorer 10. Commented 28/03/2014 às 13:36
  • estou usando chrome e no teste do jsperf a divisão foi mais rápida... não creio que essa questão seja pertinente em js Commented 28/03/2014 às 17:31

5 Respostas 5

15

Até onde eu sei, isso vale para todas as linguagens, afinal a operação se dá no processador. E se o processador não possui a função de divisão, esta precisa ser emulada utilizando outras operações. Segue explicação:

Na multiplicação, para cada posição, você está multiplicando apenas por 0 ou 1, o que é realmente fácil de fazer: você quer obter todos os zeros, ou você recebe a entrada original de volta.
Como resultado, cada bit parcial do produto pode ser calculado com uma porta AND.
Depois de ter todos os produtos parciais, basta adicioná-los em conjunto. Há algumas otimizações que você pode fazer para acelerar a lógica, mas de qualquer forma você pode ver que este processo pode ser feito de forma muito rápida.

A divisão, por outro lado, é tão feia em binário quanto é em decimal.
Algoritmos mais simples são feitos da mesma forma que era na escola: O velho algoritmo de "palpitar e corrigir, se necessário" , enquanto isso, algoritmos mais rápidos tendem a usar tabelas de pesquisa (que ocupam área de chip, portanto gastam mais).


Wikipedia sobre algoritmos de divisão: Nota-se que mesmo os algoritmos rápidos ainda são interativos - enquanto a multiplicação pode ser feita de uma só vez, a divisão exige a interações repetidas.

Fonte

5
  • 1
    Isso pra mim não faz muito sentido, pois qualquer divisão é simplesmente uma multiplicação pelo inverso do quociente. Ainda assim, as fontes estão me ajudando a entender o assunto, então +1. Commented 28/03/2014 às 13:21
  • 1
    O algoritmo de divisão possui a mesma ordem do da multiplicação. Quando puder vou exemplificar os algoritmos. Commented 28/03/2014 às 13:37
  • 2
    @Renan Exato. Mas mesmo pensando dessa forma, serão dois trabalhos contra um só: 1- inverter o número; 2- multiplicar. Contra apenas multiplicar. Muitos compiladores hoje em dia são inteligentes o suficientes pra inverter constantes em compile-time, isso é, var /= 2 vai virar var *= 0.5 mais hora menos hora na compilação. Mas quando lidando com variáveis não-constantes, vale o bom senso de performance vs usabilidade. Commented 2/04/2014 às 15:47
  • Segundo a Wikipedia, existe uma forma de reduzir uma divisão para uma multiplicação e um shift: para dividir por D, em vez de multiplicar por 1/D escolha M e N bem grandes tal que M/N == 1/D. Então, substitua N por N' tal que N' é uma potência de dois (daí dividir vira somente um shift) e a diferença entre M/N e M/N' seja menor que a margem de erro nas operações em ponto flutuante (i.e. os resultados sejam iguais). Só não sei se isso é comumente aplicado na prática (e se o é, se é em geral ou só pra constantes).
    – mgibsonbr
    Commented 24/04/2014 às 4:16
  • Obs.: Iterativo (iterative) = onde é necessário iterar, isto é, fazer loop. Interativo (interactive) = onde é possível interagir, isto é, há ação entre o usuário e o computador.
    – marcus
    Commented 27/11/2014 às 12:34
14

Testes realizados

Segundo os resultados do jsperf apresentado pelo Renan, outros testes que criei diferenciando inteiros e ponto flutuante e os testes recentemente criados pelo Marcelo a afirmação "multiplicação é mais rápido que divisão em Javascript" não é sempre verdadeira.

Resultados obtidos

Por exemplo, acabei de executar o novo teste do Marcelo no IE e no Chrome. Veja o gráfico resultante no momento que que escrevo:

Velocidade do teste nos diferentes navegadores

O item referente ao IE 10.0 fui eu quem acabei de rodar. O navegador parece abstrair os cálculos de forma que o resultado é uniforme em todos os testes. Chega a ser estranho.

Já os resultados no Chrome mostraram que a multiplicação de inteiros foi excepcionalmente mais rápida. Porém, a multiplicação por ponto flutuante foi pior que a divisão simples.

Os demais navegadores não mostraram diferenças significativas.

Com exceção do Safari versão 4, na maioria dos testes, a premissa do artigo citado na pergunta foi provada ser falsa, isto é, a operação 4 * .5 não foi executada mais rapidamente que 4 / 2.

Análise

Quanto às diferenças entre os navegadores, isso certamente depende da forma como a divisão é implementada em cada engine. Teríamos que analisar o tipo usado na linguagem original e as conversões realizadas internamente nessa linguagem, para então analisar o consumo de CPU.

Em linguagens de mais baixo nível, a divisão pode ser uma operação mais cara, porém em uma execução linear provavelmente não veríamos diferença, já que os processadores matemáticos podem finalizar a operação em apenas um ciclo. Talvez haja uma diferença em processadores com Hyper-threading, que acumulam mais de uma operação por ciclo quando há operações mais "leves" como multiplicação de inteiros, mas não conseguiriam fazê-lo com operações mais "complexas". Note que não tenho conhecimento profundo sobre processadores para afirmar com absoluta certeza, além do mais isso depende da própria estrutura da CPU e pode ser verdade apenas em casos específicos.

Conclusão

A afirmação de que "multiplicação é mais rápido que divisão" mostrou-se ser falsa em muitos casos. Ela foi verdadeira para multiplicação de inteiros em alguns navegadores, mas não para ponto flutuante como forma de substituir a divisão.

A não ser que você esteja trabalhando em um dispositivo embarcado com memória e processamento extremamente limitados, não perca tempo com esse tipo de micro otimização, ainda mais em uma linguagem como Javascript que roda em diferentes engines, sistemas operacionais e processadores.

6
  • 3
    Tenta realizar de novo com números feios, como números primos de 5 algarismos. (Só pra ver) Commented 2/04/2014 às 15:50
  • @GustavoMaciel Refiz usando o número 65537 e não houve diferença. Na verdade, numa das execuções no FF, a divisão com ponto flutuante foi ligeiramente mais lenta, mas nada muito discrepante das demais, o que me sugere que foi uma desvantagem circunstancial. A divisão usando números inteiros obteve resultado igual ao das multiplicações.
    – utluiz
    Commented 2/04/2014 às 18:09
  • 2
    Eu pedi só por motivos científicos hehe, além do mais, divisão por dois por inteiro seria otimizado como um shift right, que poderia causar diferenças nos resultados. Commented 6/04/2014 às 13:25
  • 3
    Eu refiz os testes usando uma gama maior de valores, mais umas coisinhas para evitar "confounding" (para referência, sugiro esse artigo do Zed Shawn [em inglês] sobre programação e estatística), e tive resultados... bem, nada consistentes (entre diferentes browsers). Mas a multiplicação inteira de fato apresentou uma performance mais elevada que as demais, sobretudo no Chrome. Se possível, gostaria que mais pessoas testassem em diferentes ambientes, para agregar mais dados.
    – mgibsonbr
    Commented 24/04/2014 às 3:27
  • @GustavoMaciel Concordo, e creio que se refere a um divisor diferente de dois, certo? Os testes existentes só variavam o dividendo... :P
    – mgibsonbr
    Commented 24/04/2014 às 3:29
8

Existem diversos algoritmos eficientes para realizar - em binário - a multiplicação (ex.: Dadda multiplier, Wallace tree) e a divisão (ex.: Newton-Raphson, Goldschmidt). Frequentemente elas [a multiplicação pelo menos] são efetuadas diretamente na CPU, o que traz resultados bastante rápidos.

Fonte: essa pergunta no Yahoo! Respostas (de 4 anos atrás)

Quanto à divisão, tenho dificuldade de encontrar dados concretos e atualizados, mas posso afirmar com segurança que:

  1. É possível sim implementar a divisão em hardware - e isso é feito já há bastante tempo;
  2. Entretanto, ela é mais cara (i.e. exigindo uma lógica mais complexa).

Digo isso baseado no Bug do Pentium, onde uma tentativa de otimização na divisão de pontos flutuantes (FDIV) provocou um erro em várias operações que - embora incomuns para usos do dia-a-dia - afetou de forma significativa usos mais especializados (como Astronomia, que lida rotineiramente com números muito grandes). A causa raiz do erro foi a tentativa de simplificar uma lookup table destinada a acelerar o processo de divisão - que de outra forma seria de fato mais lento.

(Nota: ao contrário do que diz o artigo da Wikipedia em português, o erro não foi na multiplicação, e sim na divisão. Para mais detalhes, ver o artigo em inglês)

Muito tempo se passou desde o Pentium pra cá, e a Lei de Moore tornou as operações matemáticas em hardware mais rápidas e baratas. Ou seja, não posso afirmar se uma é ou não mais rápida que a outra hoje sem fazer benchmarks - em diferentes linguagens e circunstâncias. Quanto a JavaScript, esse teste no jsPerf (adaptado da resposta do Luiz Ricardo) mostrou resultados inconclusivos - variando de browser pra browser. Entretanto, a multiplicação entre números inteiros parece ser um pouco mais rápida que as demais operações (ou muito mais rápida, no Chrome): divisão inteira, multiplicação em ponto flutuante e divisão em ponto flutuante.

P.S. Esse teste se refere a divisão por números arbitrários. Quando se tenta dividir por uma constante, é comum o compilador (ou interpretador, ou compilador JIT) substituir a divisão por uma operação mais simples (shift, multiplicação pelo inverso, ou algo mais sofisticado - ver esse comentário). Desse modo, não creio que os dois códigos de exemplo apresentados tenham diferença significativa de performance... mas para dizer com certeza somente verificando via experimentação.

6

A seguir segue uma tabela com a latência em ciclos de clock das operações de multiplicação e divisão para comparação.

Note que, se o seu programa chegar de fato a realizar tais operações, é isto que vai ocorrer no nível do hardware e não há como escapar disto.

| Intel Core i7                     |
|-----------------------------------|
| Instruction | Operand   | Latency |
|-------------|-----------|---------|
| MUL/IMUL    | r8        | 3       |
| MUL/IMUL    | r16       | 5       |
| MUL/IMUL    | r32       | 5       |
| MUL/IMUL    | r64       | 3       |
| IMUL        | r16,r16   | 3       |
| IMUL        | r32,r32   | 3       |
| IMUL        | r64,r64   | 3       |
| IMUL        | r16,r16,i | 3       |
| IMUL        | r32,r32,i | 3       |
| IMUL        | r64,r64,i | 3       |
| MUL/IMUL    | m8        | 3       |
| MUL/IMUL    | m16       | 5       |
| MUL/IMUL    | m32       | 5       |
| MUL/IMUL    | m64       | 3       |
| IMUL        | r16,m16   | 3       |
| IMUL        | r32,m32   | 3       |
| IMUL        | r64,m64   | 3       |
| IMUL        | r16,m16,i |         |
| IMUL        | r32,m32,i |         |
| IMUL        | r64,m64,i |         |
| DIV         | r8        | 11-21   |
| DIV         | r16       | 17-22   |
| DIV         | r32       | 17-28   |
| DIV         | r64       | 28-90   |
| IDIV        | r8        | 10-22   |
| IDIV        | r16       | 18-23   |
| IDIV        | r32       | 17-28   |
| IDIV        | r64       | 37-100  |
| FMUL        | r         | 5       |
| FMUL        | m         |         |
| FDIV        | r         | 7-27    |
| FDIV        | m         | 7-27    |
| FIMUL       | m         | 5       |
| FIDIV       | m         | 7-27    |

| AMD Steamroller                     |
|-------------------------------------|
| Instruction | Operand     | Latency |
|-------------|-------------|---------|
| MUL/IMUL    | r8/m8       | 4       |
| MUL/IMUL    | r16/m16     | 4       |
| MUL/IMUL    | r32/m32     | 4       |
| MUL/IMUL    | r64/m64     | 6       |
| IMUL        | r16,r16/m16 | 4       |
| IMUL        | r32,r32/m32 | 4       |
| IMUL        | r64,r64/m64 | 6       |
| IMUL        | r16,(r16),i | 5       |
| IMUL        | r32,(r32),i | 4       |
| IMUL        | r64,(r64),i | 6       |
| IMUL        | r16,m16,i   |         |
| IMUL        | r32,m32,i   |         |
| IMUL        | r64,m64,i   |         |
| DIV         | r8/m8       | 17-22   |
| DIV         | r16/m16     | 15-25   |
| DIV         | r32/m32     | 13-39   |
| DIV         | r64/m64     | 13-70   |
| IDIV        | r8/m8       | 17-22   |
| IDIV        | r16/m16     | 14-25   |
| IDIV        | r32/m32     | 13-39   |
| IDIV        | r64/m64     | 13-70   |
| FMUL        | r/m         | 5       |
| FIMUL       | m           |         |
| FDIV        | r           | 9-37    |
| FDIV        | m           |         |
| FIDIV       | m           |         |

| VIA Nano L3050                    |
|-----------------------------------|
| Instruction | Operand   | Latency |
|-------------|-----------|---------|
| MUL/IMUL    | r8        | 2       |
| MUL/IMUL    | r16       | 3       |
| MUL/IMUL    | r32       | 3       |
| MUL/IMUL    | r64       | 8       |
| IMUL        | r16,r16   | 2       |
| IMUL        | r32,r32   | 2       |
| IMUL        | r64,r64   | 5       |
| IMUL        | r16,r16,i | 2       |
| IMUL        | r32,r32,i | 2       |
| IMUL        | r64,r64,i | 5       |
| DIV         | r8        | 22-24   |
| DIV         | r16       | 24-28   |
| DIV         | r32       | 22-30   |
| DIV         | r64       | 145-162 |
| IDIV        | r8        | 21-24   |
| IDIV        | r16       | 24-28   |
| IDIV        | r32       | 18-26   |
| IDIV        | r64       | 182-200 |
| FMUL        | r/m       | 4       |
| FDIV        | r/m       | 14-23   |

Fonte: Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs

Isto mostra que de fato o seu processador vai realizar divisões de forma mais lenta que multiplicações. Isso se deve à implementação em hardware destas operações sofrer das mesmas questões de complexidade algorítmica já discutidas em outras respostas. Independente disso, o seu programa de uma forma ou de outra, irá fazer uso destas instruções para realizar tais operações de forma eficiente, e estará limitado à performance que elas oferecem.

Quanto aos benchmarks e dicas duvidosas que supostamente se baseiam nisto, cuidado. Cada linguagem vai tratar as expressões da forma como ela define, a expressão 1/2 no fonte em C e C++ vai acabar virando uma constante 0 no executável, e não vai ser realizada nenhuma divisão durante a execução do programa, em uma linguagem dinâmica como javascript por exemplo, o custo da interpretação das duas operações pode tornar o custo das instruções aritméticas discutidas irrelevante para a análise. Isto é só um exemplo, e o programador sábio vai saber quando multiplicação vs divisão faz sentido ou não, há casos que realmente faz, algoritmos (me vem a mente Bresenham agora...) e linguagens onde isto faz a diferença. Quando o programador não tem noção disto, e pratica hábitos de forma religiosa, cai no caso da micro otimização que é a raiz de todo o mal.

3

Bom galera, o motivo de a divisão ser mais lenta, não ta na linguagem e sim no processador. Visto que uma operação de multiplicação o processador irá realizar uma soma binária, como exemplo no sistema decimal onde 5 x 5 = 25 sendo 5 + 5 + 5 + 5 + 5 = 25. Já na divisão teremos 2 operações diferentes, que é a multiplicação e a subtração, No exemplo 25 : 5, primeiro você ira realizar uma multiplicação, para depois realizar a subtração. Resumindo o processador terá que fazer mais processos envolvendo aritmética binária.

1
  • 2
    Subtração? Podes elaborar sobre esse ponto? Commented 2/04/2014 às 17:40

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .