Modulo algorithm

[realcr]

What is the fastest algorithm currently known to calculate: a%b (a modulo b)?
Does anyone have information about this topic or links to read about it?

realcr.

[pbrennick]

realcr,
Is this a general question or does it suit a specific need?  I say this because you are not giving any value for 'n' which would be the base for modulo or should I assume base 10?

Paul

[MichaelW]

AFAIK, for the general case, DIV is the fastest method. If the base (correct term?) is a power of two, then the AND method is the fastest. This program tests three methods to determine under what conditions the faster methods will duplicate the results for the DIV method:

Code Select Expand


; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
; This simple program was used to investigate alternative
; (and faster) methods of performing a MOD operation.
;
; The final determination: For calculating n mod m, the
; shift and multiply method, and the faster AND method,
; duplicate the results of the DIV method only when m is
; a power of two.
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    .486                       ; create 32 bit code
    .model flat, stdcall       ; 32 bit memory model
    option casemap :none       ; case sensitive

    include \masm32\include\windows.inc
    include \masm32\include\masm32.inc
    include \masm32\include\user32.inc
    include \masm32\include\kernel32.inc
    includelib \masm32\lib\masm32.lib
    includelib \masm32\lib\user32.lib
    includelib \masm32\lib\kernel32.lib
    include \masm32\macros\macros.asm

    mod_div MACRO n, m
        xor   edx, edx
        mov   eax, n
        mov   ecx, m
        div   ecx
        EXITM <edx>
    ENDM

    mod_mul MACRO n,m
        xor   ecx, ecx      ;;
        mov   eax, m        ;; Determine the shift count
      @@:                   ;; that would be required to
        inc   ecx           ;; shift the most significant
        shl   eax, 1        ;; bit of m into bit 32...
        jnc   @B            ;;
        mov   eax, n        ;; and shift n left by that
        shl   eax, cl       ;; shift count...
        mov   ecx, m        ;;
        mul   ecx           ;; before multiplying by m.
        EXITM <edx>
    ENDM

    mod_and MACRO n, m
        mov   eax, n
        mov   edx, m
        dec   edx           ;; Must AND with m-1
        and   eax, edx
        EXITM <eax>
    ENDM

    ; -------------------------------------------------
    ; This is a copy of the MASM32 input macro, placed
    ; here so I could conveniently add the missing null
    ; terminator on txt.
    ; -------------------------------------------------
    _input MACRO prompt:VARARG
        LOCAL txt
        LOCAL buffer
      IFNB <prompt>
        .data
          txt db prompt, 0       ;; <===
          buffer db 128 dup (0)
          align 4
        .code
        invoke StdOut,ADDR txt
        invoke StdIn,ADDR buffer,LENGTHOF buffer
        invoke StripLF,ADDR buffer
        mov eax, offset buffer
        EXITM <eax>
      ELSE
        .data
          buffer db 128 dup (0)
          align 4
        .code
        invoke StdIn,ADDR buffer,LENGTHOF buffer
        invoke StripLF,ADDR buffer
        mov eax, offset buffer
        EXITM <eax>
      ENDIF
    ENDM

; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
        n       dd 0
        m       dd 0
    .code
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    mov eax, uval(_input(13,10,"Enter n : "))
    test  eax, eax
    jz    fini
    mov   n, eax

    mov eax, uval(_input(13,10,"Enter m : "))
    test  eax, eax
    jz    fini
    mov   m, eax

    print chr$(13,10,"n mod_div m = ")
    print ustr$(mod_div(n, m))
    print chr$(13,10,"n mod_mul m = ")
    print ustr$(mod_mul(n, m))
    print chr$(13,10,"n mod_and m = ")
    print ustr$(mod_and(n, m))
    print chr$(13,10)

    jmp   start
  fini:
    mov   eax, input(13,10,"Press enter to exit...")
    exit

; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start


During the time I was working on this, Mark Larson suggested a method of adjusting the result so the faster methods could be made to work for the general case, but I was not able to produce anything that worked correctly.

[liquidsilver]

I would think that the DIV method is the easiest to implement and the simplest to understand, but if you know what one of the variables  will be or have a idea, then the other methods could be much faster. Personally I just use the DIV method, but then again, why should you listen to me? I suggest you learn to use all three methods and try them, then decide that to do.

What do you mean with base?

[pbrennick]

Hi Michael,
I don't remember if it is called base. either, but it does a good job of describing what it is for.  It is the rollover point which is what a base is so for lack of a better word...

Paul

[AeroASM]

Isn't what you are calling the "base" the modulus?

[MichaelW]

Isn't what you are calling the "base" the modulus?

Yes, thanks.

From Concrete Mathematics, Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Addison-Wesley, 1989:
"The number after 'mod' is called the modulus; nobody has yet decided what to call the number before 'mod'."

[realcr]

tnx for your answers.
By modulo I mean for example:

9%5=4 beacause 9=1*5+4
8%4=0 because 8=2*4+0

The purpose I need to know the algorithm for is to calculate the number of basic instruction it does.
(usually written like O(n) , O(n*lnn) or similar things).
MichaelW ,great thanks for your time and the program you wrote.
Where can I find how is the div instruction implemented?

realcr.

[sluggy]

Just check it out in Randy Hyde's "Art of Assembly" here.

Or download Volume 2 of the Intel Architecture Software Developers Manual (here is a link to the PIII version).

[thomasantony]

Hi,
   Sorry for the late reply. Hope I am not butting in. But can't you use cdq instead of xor edx,edx?

Thomas Antony

[roticv]

xor edx, edx is faster than cdq. Therefore use the xor method if you do not care abt the signness.

[dsouza123]

There is also calculate a modular inverse using the modulus and a power of 2
with the numbers stored a binary format then AND and use the result to convert back to the modulus.

Another is convert the first number to the base of the modulus then just use the low base modulus digit.