Multiply to divide

[ToutEnMasm]

There is an interesting paper on the subject here
http://www.asmcommunity.net/board/index.php?topic=21308.msg161744#msg161744

Who can solve for me this sample and give me an explain ?

                 ;--------------- normal divide
   mov edx,0
   mov ecx,20
   mov eax,400
   div ecx
;and now try to multiply
   mov edx,0
   mov ecx,???????????????            ;(0FFFFFFFFh/30)+1 don't work with 30 or 20
   mov eax,400
   mul ecx

[dedndave]

Code Select Expand

        mov     eax,400
        mov     edx,0CCCCCCCDh       ;2^36 / 20
        mul     edx
        shr     edx,4
; edx = quotient
; to get the remainder...
        mov     eax,edx
        imul    eax,eax,20
        neg     eax
        add     eax,edx
; edx = quotient
; eax = remainder

i got the division part by using qWord's Magic Number 64 program
http://www.masm32.com/board/index.php?topic=9937.msg72815#msg72815

there are a few variations on retrieving the remainder
the one i show above may not be the fastest

[ToutEnMasm]

I have tested this one who works :

                400/20 = 14h  (20) 
   ;----- with the windows calculatrice-----------
   ;FFFFFFFF/20=214748364,75  delet all after the , and add 1
   ;Magic = 214748365
                mov edx,0
   mov ecx,214748365
   mov eax,400
   mul ecx
   ------- result in edx 14h correct ---------------

[dedndave]

it may not work over a full range of dividends
what is the range of values - or are you just dividing 400 only   :lol

[ToutEnMasm]

The author of this method say it's works with any size of registers.
The FFFFFFFFh is just a dword with all bits set to 1
with a qword this begin  FFFFFFFFFFFFFFFFh,a qword with all bits set to 1
..... and so on
I have not verify this but made further tests succesfuls on 32 bits.
He give the full explain of this but i am not to mutch read it

[ToutEnMasm]

I think i have got a simple explain who demonstrate he work all the time.I took the problem by the end.

We have the result of a divide * 2p16    (p = puissance)
result = (N/D) ;N=various integer
We are not interested by N because he change all the time.So we divide this expression by N.
So we got 2p16/D = FFFFh/D + 1 = magic number
End of the demonstration forr 16 bits values

N is any integer and is range can be D to (2p32-1)/(2p16/D) ;0 could work need test
really simple
That all

[dedndave]

Yves,
generally, when i am going to use multiply-to-divide, i write a little test program
it runs through the entire range of dividends that i intend to use and reports errors
in the loop, i call the m2d function, then compare the quotient with that of DIV
(no need to compare remainders - if the quotient is correct, the remainder will be)

here is an example....

Code Select Expand

;eax = dividend (0 to 4294967295)

        xor     eax,eax

test01: push    eax
        mov     edx,mult
        push    eax                  ;save the dividend
        mov     ecx,shft
        mul     edx                  ;multiply to divide
        shr     edx,cl               ;adjust the quotient
        pop     eax
        push    edx
        mov     ecx,divisor
        xor     edx,edx
        div     ecx
        pop     ecx
        cmp     eax,ecx
        pop     edx
        jnz     report

        xchg    eax,edx
        add     eax,1
        jnz     test01

        jmp short exit_loop

report: push    eax
        push    ecx
        push    edx
        print   chr$('Divisor: ')
        mov     eax,divisor
        print   ustr$(eax),32
        print   chr$('Dividend: ')
        pop     eax
        print   uhex$(eax),32
        print   chr$('Quotient Was: ')
        pop     eax
        print   uhex$(eax),32
        print   chr$('Should Be: ')
        pop     eax
        print   uhex$(eax),13,10

exit_loop:

[ToutEnMasm]

Here is  little test
Take  a number divide it by 1 to 1000 comparing the result.
One failed on 1000 , its the divide by 1.
FFFFFFFFFh +1= -1+1=0
0*N=0

Magic_Number PROC
    Local diviseur:DWORD
    Local dividende:DWORD
    local  result:DWORD
    Local  magic:DWORD
   Local  retour:DWORD
         mov retour,0       ;counter of good operation
      mov diviseur,1
      mov dividende,325847
      continue:
   ;as explain  in the post ,i took the problem by the end
   ;begin by  normal division
   mov edx,0
   mov ecx,diviseur
   mov eax,dividende
   div ecx
   mov result,eax
   ;we keep the result for comparison.
   ;calcul of magic number,FFFFFFFF/D
   ;I made it with a div
   mov edx,0       
   mov eax,-1
   mov ecx,diviseur
   div ecx
   inc eax
   mov magic,eax
   ;knowing the magic we can proceed to the multiply
   mov edx,0
   mov ecx,magic
   mov eax,dividende
   mul ecx
   .if edx == result
      inc retour
   .endif
   inc diviseur
   .if diviseur != 1001
         jmp continue
   .endif

FindeMagic_Number:
         mov eax,retour
         ret
Magic_Number endp

[RuiLoureiro]

Why «mov edx,0» before mul ecx ?
We dont need, the result is in EDX:EAX
   

;knowing the magic we can proceed to the multiply
   ;mov edx,0                   ; <<<<<<<<<<<<<<<<<<<<<<<<<<<
   mov ecx,magic
   mov eax,dividende
   mul ecx