News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

magic numbers

Started by RuiLoureiro, May 13, 2013, 07:33:02 AM

Previous topic - Next topic

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:

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

And for 100:

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.

Well Microsoft, here's another nice mess you've gotten us into.

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:
mov eax,X
mov edx,0CCCCCCCDh
mul edx
shr edx,3
; edx = quotient


if you want the remainder, you can add a little code...
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.....
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=232/100=42949672.96=42949673
        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...
        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.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

Well Microsoft, here's another nice mess you've gotten us into.

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.
Well Microsoft, here's another nice mess you've gotten us into.

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

Fa is a musical note to play with CL

MichaelW

Well Microsoft, here's another nice mess you've gotten us into.

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.
MREAL macros - when you need floating point arithmetic while assembling!

Mikl__

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

dedndave

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