Month / February 2012

by Carsten König

a correct ‘modulus’ for F#

In math we use the remainder for modular-arithmetic. That is given two numbers n and m we already saw that we can express n as

n = mq + r

where r is in the range 0 \leq r < m – and we call this the remainder of dividing n by m, so for negative numbers we have for example:

-14 = -3*5 + 1 so -14 = 1 (mod 5).

But in F# we have:

% (modulus, mod)

Returns the remainder of a division operation. The sign of the result is the same as the sign of the first operand

So

> -14 % 5;;
val it : int = -4

So we have to change this if we want correct values for negative numbers.

There are a couple of options, ranging from checking the sign and using different formulas (cases) but the simples one is just using

let modulo n m = ((n % m) + m) % m

if m > 0.

> modulo -14 5;;
val it : int = 1

This should be sufficient for most problems but

    let inline modulo n m =
        let mod' = n % m
        if sign mod' >= 0 then mod'
        else abs m + mod'

might be more efficient if you deal with big integers (or some other kind of values where the %-operator is not easily computed).

Update:

After messing up a bit with the case, when n < 0 I should make sure that all works as it should – here is the test validating the second version for those special occasions:

[<Test>]
member test.``modulo should respect the math way``() =
   let testPairs =
      [ for d in [-3..3] do
        for r in [0..5] do
        yield (d,r)
      ]

   let testOnePair (d,r) =
      let z = d*(-6)+r
      let r' = modulo z (-6)
      r |> should equal r'

   testPairs |> List.iter testOnePair</pre>