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.
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
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:
; ««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
; 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.
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?
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
Isn't what you are calling the "base" the modulus?
Quote from: AeroASM on March 19, 2005, 03:59:50 PM
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'."
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.
Just check it out in Randy Hyde's "Art of Assembly" here (http://webster.cs.ucr.edu/).
Or download Volume 2 of the Intel Architecture Software Developers Manual (here (http://developer.intel.com/design/pentium4/manuals/index_new.htm) is a link to the PIII version).
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
xor edx, edx is faster than cdq. Therefore use the xor method if you do not care abt the signness.
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.