Type-safe modular arithmetic

[pathikrit]

class ModularArithmetic(val mod: Long) {
  class Mod(val value: Long) {
    override val toString = value.toString
  }
  implicit def fromMod(mod: Mod): Long = mod.value
  implicit def toMod(x: Long): Mod = new Mod(x%mod)

  val factorial: IndexedSeq[Mod] = {
    val N = 5500
    val f = Array.ofDim[Mod](N)
    f(0) = 1L
    (1 until N).foreach(i => f(i) = f(i-1) * i)
    f
  }

  def modularInverse(n: Long): Mod = BigInt(n).modInverse(mod).toLong //If mod is prime override this with BigInt(n).modPow(mod - 2, mod).toLong

  def modDiv(a: Long, b: Long): Mod = a * modularInverse(b)

  def permutations(n: Int, k: Int): Mod = modDiv(factorial(n), factorial(n - k))

  def combinations(n: Int, k: Int): Mod = modDiv(permutations(n, k), factorial(k))
}