F#: integer (%) integer - Is Calculated How?

Question

So in my text book there is this example of a recursive function using f#

let rec gcd = function
| (0,n) -> n
| (m,n) -> gcd(n % m,m);;

with this function my text book gives the example by executing:

gcd(36,116);;

and since the m = 36 and not 0 then it ofcourse goes for the second clause like this:

gcd(116 % 36,36)
gcd(8,36)
gcd(36 % 8,8)
gcd(4,8)
gcd(8 % 4,4)
gcd(0,4) 
and now hits the first clause stating this entire thing is = 4.

What i don't get is this (%)percentage sign/operator or whatever it is called in this connection. for an instance i don't get how

116 % 36 = 8

I have turned this so many times in my head now and I can't figure how this can turn into 8?

I know this is probably a silly question for those of you who knows this but I would very much appreciate your help the same.

Answer 1

% is a questionable version of modulo, which is the remainder of an integer division.

In the positive, you can think of % as the remainder of the division. See for example Wikipedia on Euclidean Divison. Consider 9 % 4: 4 fits into 9 twice. But two times four is only eight. Thus, there is a remainder of one.

If there are negative operands, % effectively ignores the signs to calculate the remainder and then uses the sign of the dividend as the sign of the result. This corresponds to the remainder of an integer division that rounds to zero, i.e. -2 / 3 = 0.

This is a mathematically unusual definition of division and remainder that has some bad properties. Normally, when calculating modulo n, adding or subtracting n on the input has no effect. Not so for this operator: 2 % 3 is not equal to (2 - 3) % 3.

I usually have the following defined to get useful remainders when there are negative operands:

/// Euclidean remainder, the proper modulo operation
let inline (%!) a b = (a % b + b) % b

So far, this operator was valid for all cases I have encountered where a modulo was needed, while the raw % repeatedly wasn't. For example:

• When filling rows and columns from a single index, you could calculate rowNumber = index / nCols and colNumber = index % nCols. But if index and colNumber can be negative, this mapping becomes invalid, while Euclidean division and remainder remain valid.

• If you want to normalize an angle to (0, 2pi), angle %! (2. * System.Math.PI) does the job, while the "normal" % might give you a headache.