Mais um blog inútil.

Janeiro 12, 2008

Código estranho II

Filed under: Assembly — dongs @ 3:23

mov ecx, eax
mov eax, 0CCCCCCCDh
mul ecx
shr edx, 3

Em 1994, o Torbjorn Granlund e o Peter Montgomery (o mesmo gajo que inventou a multiplicação de Montgomery do outro post) publicaram um artigo que descrevia como dividir um inteiro N por uma constante d, sem utilizar divisões. A partir daí todos os compiladores que se prezem passaram a usar este tipo de técnicas, e podemos ver no artigo como e' feito.

a) Calcular a recíproca da divisão (arredondada) - f = 2^r / d => r = W+floor(log2(d) )

b) Multiplicar por f

c) dividir por 2^log2(d)

Assim, no caso acima, temos uma divisão por 10. f = Round(2^32+3/10) = 0xCCCCCCCD

Floor(Log2(10)) = 3;

Infelizmente, devido à perda de precisão não podemos recuperar facilmente as constantes a serem usadas como divisor. No entanto, é fácil criar uma tabela com a maioria das recíprocas e dos factores de escala usados e assim poupar tempo a olhar para contas.

Quem estiver interessado veja isto.

Um comentário a “Código estranho II”

  1. lol diz:

    n li, mas so comentei pq sim :)

Comentar

widgeon
widgeon
widgeon
widgeon