Maths question on divide by reciprocal.

[hutch--]

With floating point the task is simple but I cannot find any reference material on doing this task with integers within a DWORD range. What I don't know how to do is find the reciprocal for a number I wish to divide by. I have a working example for divide by 3 in unsigned range and by twiddling have a rough by 4 and 5 but I have yet to find the reference material on how the matyhs work on DWORD range integers.

This is the test piece.

Code Select Expand


IF 0  ; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
                      Build this template with "CONSOLE ASSEMBLE AND LINK"
ENDIF ; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

    include \masm32\include\masm32rt.inc

    .code

start:
   
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

    call main
    inkey
    exit

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

main proc

  ; divide EAX by 3, output EDX

    mov eax, 66
    mov ecx, 0AAAAAAABh     ;  1/3
    mul ecx                 ;  multiply with inverse
    shr edx, 1              ;  shift by 33

    print str$(edx),13,10

  ; divide EAX by 4, output EDX

    mov eax, 128
    mov ecx, 80000000h      ;  1/4
    mul ecx                 ;  multiply with inverse
    shr edx, 1              ;  shift by 33

    print str$(edx),13,10

  ; divide EAX by 5, output EDX

    mov eax, 2000000000
    mov ecx, 6666666Ah      ;  1/5
    mul ecx                 ;  multiply with inverse
    shr edx, 1              ;  shift by 33

    print str$(edx),13,10

    ret

main endp

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

end start


[dedndave]

besides the magic number program, qWord also wrote a set of macros to find the reciprocal
let me see if i can find the thread...
http://www.masm32.com/board/index.php?topic=12421.0

let me add that, if your dividend is going to be in a limited range, you can simplify things a bit
if you need the multiply-to-divide code to work over the full dword dividend range, it is a little tricky
that's when the macros may come in handy

[Tedd]

The simplified version...

For divide by 11, the magic reciprocal is  2³² / 11 = 390451572 (remainder 4)
and multiplying by this number gives  12345 * 390451572 = 4820124656340
which doesn't look right, until you realize what we actually did what multiply by 2³² and then divide by 11.
So, for the result, we can just divide by 2³² again - which would be the same as just dividing by 11 in the first place.
Luckily for us, the result of a mul is naturally split into edx and eax, where edx represents the upper part multiplied by 2³², so we just take edx directly as the result.

Sure enough...

12345 / 11 = 1122.27
12345 * 390451572 = 4820124656340 = 1122 * 2³² + 1171350228  => 1122


That's the simplified version because we didn't take the 4 remainder into account, which leads to accumulated errors depending on what values you're dividing. As Dave said, it depends on the range you want to include.
To increase accuracy, you'd shift the magic value and add on a proportion of the remainder. Then shift the result back again to correct for the inherent shift in the magic value, which can effectively give you a few decimal places of accuracy (rounded, naturally.)

[dedndave]

i have a case where i want to divide by monospace cell width and height during calculations for handling WM_PAINT
i don't want to use DIV in the paint routine
and, i know the cell width and height are always relatively small (divisor)
i also know the client area pixel height and width values are relatively small (dividend)
however, i allow the user to select from a number of text sizes, so they are not constants
i don't mind using DIV when they select a new text size
i call the following routine once for cell width and once for cell height
notice that these will fail for large dividend values

to get the multiplier and shift values...

Code Select Expand

;**************************************************************

        OPTION  PROLOGUE:None
        OPTION  EPILOGUE:None

M2dCalc PROC    dwDivisor:DWORD

;calculate multiplier and shift values for multiply-to-divide
;input value not validated
;tested for divisors 4-35 and dividends less than 80000000h
;
;Call With: dwDivisor = divisor
;
;  Returns: EAX = multiplier
;           ECX = divisor
;           EDX = shift

        mov     eax,[esp+4]
        dec     eax
        bsr     ecx,eax
        push    1
        inc     eax
        pop     edx
        push    ecx
        shl     edx,cl
        xchg    eax,ecx
        xor     eax,eax
        div     ecx
        pop     edx
        inc     eax
        ret     4

M2dCalc ENDP

        OPTION  PROLOGUE:PrologueDef
        OPTION  EPILOGUE:EpilogueDef

;**************************************************************

[donkey]

This is a fairly decent article.

http://blogs.msdn.com/b/devdev/archive/2005/12/12/502980.aspx