Friday, 6 June 2008

real modulus and fake

there are a lot of different meanings to the word modulus with respect to computers and maths. The mathematical definition is virtually worthless in C, as the C modulus operator is a lie, it is not modulus, it is remainder.

True modulus can be explained as the remainder of a divide, but it's best to think of it as a small space in which numbers go round the corner back to the bottom every time they get to the end.

the small spaces are name Nx where x is the modulus.

for example, 4 mod 5 is 4 because the field N5 consists of { 0,1,2,3,4 }.
6 mod 5 is not 6 however because it doesn't fit in the list of available numbers. When a number doesn't fit in the list, you take the x value away until it fits. so, 6 becomes 1, which fits, and therefore 6 mod 5 is 1.
Even very very very large numbers can be modded thus.

126785913649525 mod 2 is 1.
126785913649525 mod 10 is 5.

interesting though is the case of negative numbers. 6 mod 5 is 1 because we took away 5 to get 1. -4 mod 5 is also not in the field, even though it looks like it might be because we see a 4. This is a lie. Computers will return the value -4 as a valid result of a mod operation, but modulus does not have negative numbers because it is based in N (not Z for integers).
the correct way of arriving at a proper modulus of N5 is to add until you fit. in this case, -4 becomes 1. Just like 6. You can even see simply that this is true by taking 6-4 = 2 as a exemplary proof that (6)N5 + (-4)N5 == (2)N5

computer modulus is a remainder.

BUT:

bit masking gives us a limited set of real modulus capability.

if you want to mod (2^x), then you're in luck.

9 mod 8 is 1.
-7 mod 8 is 1.
9 % 8 = 1
-7 % 8 = -7

but, using the bitwise AND (&), and the mask of the modulus we're after (x-1):
9 & (8-1) = 1
-7 & (8-1) = 1

this is useful in other ways too.

multiplication in fields is strange and enjoyable, especially if the multiplier is co-prime with the number space.

e.g.
1N5 = 1
1*3 N5 = 3
3*3 N5 = 4
4*3 N5 = 2
2*3 N5 = 1

so... multiplication takes you around a number space in a predictable, but odd pattern...

this is the basis of many pseudo random number generators.
this is also the basis of some sweet hacks...

example
x = 0x40000000;
loop:
x *= 3; // note implicit modulus due to size of int ( same as mod 0x100000000 )
if( x > 0 ) // will to false if highest bit is true
{
// is true every other time
}

happy hacking.
Post a Comment