I had a problem earlier today that required me to perform modular arithmetic, and when I though about it, I wasn't exactly certain of the best way to aproach the problem... Anyone have any ideas? As in I have to do

113 mod 10
or
462 mod 3
etc...
Posted on 2003-07-30 21:03:55 by FearHQ
mod is the remainder of a division. For example, 113 mod 10 is 3.

Using those numbers as examples,
mov  eax,113

xor edx,edx ;in 32-bit mode, the EDX:EAX register pair
;is used for the numerator
;(although the DX:AX pair or the AH:AL pair
;could also be used)
mov ecx,10
div ecx ;quotient => EAX = 11
;remainder => EDX = 3

Raymond
Posted on 2003-07-30 22:21:13 by Raymond
I'm an idiot. I knew this too... How could I forget the remainder is in EDX?
Posted on 2003-07-30 22:48:24 by FearHQ
Don't feel bad. I've seen very experienced programmers also forgetting such simple things. There's always that tendency to complicated matters without looking at the basics.

Raymond
Posted on 2003-07-31 10:33:40 by Raymond
About the thing of:

There's always that tendency to complicated matters without looking at the basics.


This not only apply to programming, can be aplied to a lot of things.. eg.. I have a very skilled ( I think) teacher of calculus (not good for teach, but good for solve problems apparently, One day the teacher put a extrange function for integrate with sin cos... a divition and suchs thing, was short, the programm "matematica" or some other make a extrange result.. and was OK, the solution of the integration aparently the teacher show if you can add a 0 and do some algebraic things the result of the program is the same than this, after, the teacher show to us is way... and that was nice.. a very diferent for of do integration... and I see that the division can be reduced to the form of (in a general way, remember sin and such things):

f(x)= dx/x

and wow.. i dont say nothing.. I see the complex methods of the programm (I dont remember what was) and the other more short of my teacher.. and I see my result and say some like ammmm... this is extrange, my friend szy me that I need show my result... and I with care that I can be uncorrect (think if you see complex solutions of a programm and a human) for what if i am a newbie in calculus can see this simple thing..... a posible answer can be this.. i have not much skill manipulating the things algebraically or sucht things and methods.. and for this I see relatevely easy the solution to this problem.


Yes some times are answer very easy.. some times we go with all the tools that we have and some times we need only a simple tool... ;), the easiest answer maybe can not be easely 'discoveret'.

Nice day.
Posted on 2003-08-01 20:44:06 by rea
This reminds me of an old rule of limits in math- "If the limit makes sense stick it in".

I remember about two months into doing difficult limit questions coming across one where the limit sense to just stick it in. How many people in the class spotted this? Zero, not even the teacher.

Sometimes you get so caught up searching for a difficult answer that you can't see the simple one. You can't see the forest for the trees.
Posted on 2003-08-01 20:53:19 by Eóin
Extention to the answer:

for FPU (IEEE)
FPREM1
-----------------------
Fast for x < 2^8 ; x in al

db 0D4, Y (byte)
then x = qy+r
out al = r ah = q

for example

db 0D4, 7

al = al mode 7
-----------------------
Fast for Y = 2^n (n natural) fast code

and X, Y - 1

x = x mod y
for clarity:
Y - 1 in binary a number where n lower bits
are set to 1, rest to 0.

Also there are some additional ways to get modulo.
Posted on 2003-08-01 23:08:08 by The Svin
You have also a wonderful trick for computing modulo with constant values.

Instead of doing a division, you can use shifts (or MMX instructions) and a small table.
Let's take an example.

Suppose I need to compute a 32 bits number modulo 17.

Let's enumerate 2^n modulo 17:

2^0 -> 1
2^1 -> 2
2^2 -> 4
2^3 -> 8
2^4 -> 16 = -1 modulo 17
2^5 -> 15
2^6 -> 13
2^7 -> 9
2^8 -> 1
etc...

With the 4th power:
You simply cut the 32 bits number in sets of 4 bits, and alternatively add and substract them.
For the 32 bits:
AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHH

You compute:
HHHH-GGGG+FFFF-EEEE+DDDD-CCCC+BBBB-AAAA

You'll get a value between -15*4 (-60) and +15*4 (+60), that you can normalize with a table of 120 entries.

With the 8th power:
AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD

You compute:
AAAAAAAA+BBBBBBBB+CCCCCCCC+DDDDDDDD

and you get a value from 0 to 255*4 that you can normalize with a table of 1020 entries.

JC
Posted on 2003-08-08 12:19:33 by MCoder