Otimizando cálculos matemáticos com Potencias de 2

   Programadores da área de informatica geralmente não se preocupam muito com isso, mas quem vem da área da eletrônica e da automação (como eu), já deve ter esbarrado algumas vezes em problemas gerados por gargalos de desempenho, principalmente em aplicações de tempo crítico.

  Particularmente eu aprendi a programar na família 8051 de microcontroladores (sim eu sei, isso é uma velharia, mas foi o que me ensinaram na escola), pra quem nunca ouviu falar disso vou dar uma resumida:  A família do 8051 são microcontroladores de 8 bits fabricados pela atmel, foram lançados lá em meados da década de 80!

  Inclusive meu primeiro projetinho foi baseado num 89s52 que tinha incríveis 256 BYTES de Memoria RAM.  

  Já usei muito também série 12F de Pics da Microchip, especialmente o PIC 12F675 (microcontrolador que eu gosto muito), ele possui 64 Bytes de RAM, inclusive me lembro de usar um desses em um projeto em que eu precisava fazer um calculo de divisão para determinar a porcentagem do Duty Cicle de uma onda quadrada gerada por software e a Biblioteca "math" que o compilador importou pra fazer esse calculo exigia mais memoria do que o microcontrolador tinha disponível, alem disso o código não seria executado rápido o suficiente para atualizar o valor antes da interrupção acontecer, um completo desastre. rsrs

  Bom, quando trabalhamos com esse tipo de plataforma é interessante otimizar nosso código ao máximo e especificamente algumas instruções devem ser evitadas a todo custo, isso varia muito de um microprocessador para o outro, mas no geral a multiplicação e principalmente a divisão devem ser evitadas.

  Se você estiver trabalhando com uma plataforma que não possuam suporte nativo a ponto flutuante o ideal é utilizar apenas inteiros mesmo.

  Otimizar os cálculos com números inteiros não é difícil, o ideal é usar sempre números que sejam potencia de 2, isso facilita bastante as coisas, pois como estamos trabalhando com um sistema binário podemos multiplicar e dividir adicionando ou removendo casas. Por exemplo:

  Considere o numero 15 em binário: 00001111b

  Se deslocarmos ele uma casa para a esquerda (15 << 1)  obteremos 00011110b que é equivalente a 30, ou seja, na pratica nós estamos multiplicando por 2

  Se deslocarmos ele uma casa para a direita  (15 >> 1) obteremos 00000111b que é equivalente a 7, então é como se estivéssemos dividindo ele por 2.

  Se deslocarmos duas casa seria equivalente a dividir/multiplicar por 4, deslocar 3 casas por 8 e assim suscetivamente. 

  Sendo que praticamente todos os processadores podem realizar esse tipo de calculo pelas instruções de shift que são muito mais rápidas do que uma divisão ou multiplicação.

(Essa tabela é referente ao MC68000, >>Link<<, note o numero de ciclos de clock para cada instrução)

 

 Só lembrando que estamos lidando com logica de inteiros, por isso 15 / 2 = 7 e sobra 1!

  É possível encontrar o resto de divisão (chamado de Reminder ou Modulus em algumas linguagens) usando álgebra booleana.

 Por exemplo, se quisermos saber quanto é o resto de divisão de 15 por 2 podemos realizar a operação AND entre o 15 e (2-1).

Reminder = 00001111b AND 00000001b

  O resultado disso será 1 (exatamente o resto de divisão que estamos procurando), isso é possível por que a operação AND vai "limpar" (zerar) a parte da palavra que é maior ou igual a 15 ( que é o nosso dividendo) sobrando apenas o resto da divisão.

  Em processadores como o MC68000 realizar a operação AND é dezenas de vezes mais rápido do que calcular o resto de divisão usando a instrução DIV (no caso do MC68000 quando usamos a instrução DIVU ou DIVS a resposta é um valor de 32 bits contendo o resultado na low Word e o reminder na Up Word).

  Lembrando que tudo isso é valido para cálculos usando potencias de 2, em muitos casos vale apena estender os valores para potencias de 2, como o tamanho de matrizes multidimensionais por exemplo, por que podemos ganhar muito em desempenho com isso. Então calcular um índice de uma matriz de (4,64) é muito mais rápido do que calcular um índice em uma matriz de (3,60).

  Eu coloquei as regrinhas de otimização numa tabela pra facilitar:

  Caso você precise trabalhar com valores menores do que 1 em plataformas sem suporte a ponto flutuante talvez seja interessante (quando possível) usar notação de ponto fixo! É mais limitado de um ponto de vista matemático, porem é muito mais eficaz em termos de desempenho, sendo o ideal para tarefas que não requerem um alto nível de precisão.

  Podemos falar da notação de ponto fixo num próximo post, quem sabe...