magic numbers

[RuiLoureiro]

Hi
    i found some examples where
    we want to divide eax by 10,
    and they do this:

    mov edx, 0CCCCCCCDh ;= 3435973837
    mul edx
    shr edx, 03h

    and we get edx = quotient and
    the magic number is 0CCCCCCCDh = 3435973837.

    What is the magic number if we want to divide by 100
    and what to do ?

[MichaelW]

I have a Magic Divider app that I downloaded somewhere and it's been so long that I don't recall where. For a divider of 10 it returns:

Code Select Expand


MagicNumber = 3435973837
mov eax,X
mov edx, MagicNumber
mul edx
SHR edx, 3

And for 100:

Code Select Expand


MagicNumber = 2748779069
mov eax,X
mov edx, MagicNumber
inc eax
mul edx
SHR edx, 6


Try searching for magic divider svin.

And IIRC Agner Fog explains the method in his optimization manuals.

[dedndave]

the app was written by qWord
he also wrote a set of macros

http://www.masmforum.com/archive2012/6717_MagicNumber64.zip

for a divisor of 10, in 32-bit mode, it gives:

Code Select Expand

mov eax,X
mov edx,0CCCCCCCDh
mul edx
shr edx,3
; edx = quotient

if you want the remainder, you can add a little code...

Code Select Expand

mov ecx,X
mov eax,0CCCCCCCDh
mul ecx
shr edx,3
; edx = quotient

imul eax,edx,10
sub ecx,eax
; ecx = remainder

about 20 clock cycles, i think

for a divisor of 100.....

Code Select Expand

mov ecx,X
mov eax,51EB851Fh
mul ecx
shr edx,5
; edx = quotient

imul eax,edx,100
sub ecx,eax
; ecx = remainder

[Mikl__]

RuiLoureiro,
I think we are talking about expscale? 0<=|expscale|<= 4932
so I use MagicNumber=2³²/100=42949672.96=42949673

Code Select Expand

        mov eax,expscale
        mov esi,eax
mov edx,42949673;2^32/100
mul edx
        imul edx,100;edx = quotient*100
        sub esi,edx;esi = remainder of the division by 100

[dedndave]

right Mikl - that won't work over the entire range, but it will work to 4932 (9999, i think)   :P

makes the code a little simpler if you put the multiplier in EAX, though...

Code Select Expand

        mov  ecx,expscale
mov  eax,42949673 ;2^32/100
mul  ecx          ;edx = quotient
        imul eax,edx,100  ;eax = quotient*100
        sub  ecx,eax      ;ecx = remainder of the division by 100
~18 cycles

[Mikl__]

all code

Code Select Expand

.data
table0 db "000102030405060708091011121314151617181920212223242526272829"
       db "303132333435363738394041424344454647484950515253545556575859"
       db "606162636465666768697071727374757677787980818283848586878889"
       db "90919293949596979899"
.code
mov word ptr [edi+21],'+E'
mov eax,iExp
mov edx,eax
sar edx,31
xor eax,edx
sub eax,edx; neg eax
and edx,2
add byte ptr [edi+22],dl; "+" or "-"
mov esi,eax
mov edx,42949673;2^32/100
mul edx
mov ax,word ptr table0[edx*2] ;edx = quotient of the division by 100
mov word ptr [edi+23],ax
lea eax,[edx*4]
shl edx,2
lea edx,[edx+edx*2]
lea edx,[eax+edx*8] ;edx = quotient*100
sub esi,edx ;esi = remainder of the division by 100
mov ax,word ptr table0[esi*2]
        mov word ptr [edi+25],ax

[MichaelW]

the app was written by qWord

In 2004?

[dedndave]

in 2008-2009
here is the original thread, with the attachment missing...
http://www.masmforum.com/board/index.php?topic=9937.0

[MichaelW]

I downloaded the one that I have not later than 2004.

[dedndave]

this is the one i use
http://www.masmforum.com/archive2012/6717_MagicNumber64.zip

but, if you look at the old archive sites, there are a few files with the word "magic"   :P

[TouEnMasm]

For 32 bits
http://win32assembly.programminghorizon.com/source.html

[MichaelW]

For 32 bits
http://win32assembly.programminghorizon.com/source.html

That's the one I have.

[qWord]

Well, this trick (I would call it some kind of fix point arithmetic) is surly not new - the source code from AMD's optimization manuals reference papers from 1988 and 1994.

[Mikl__]

 Henry S. Warren Jr. wrote in book «Hacker's delight» about this trick

[dedndave]

i think the method pre-dates the IBM PC   
i seem to recall some 6502 code to do this