modular arithmetic

[Nicolas Desmoulins]

Hello,

I would like to implement some operations with modular arithmetic, either over Int or BigInt, where all operations are done over Zq, i.e all operation are reduced by modulus q (so % q (+ q if result < 0 ) in case of Int, and mod(q) in case of BigInt).
These 'modular' numbers will then be used hopefully within polynomials and matrix.

Spire seems to be a good solution to develop something generic while maintaining good performances.

But I don't see how to create a new Integer type where all operations are reduced by a modulus.

I thought that I could achieve that by extending the class spire.math.Natural and override the +,-, *, ... methods. But as Natural is a sealed class, it cannot work.

What would be the good way to do that?

Thanks

Nicolas

[Erik Osheim]

Hi Nicolas,

We don't have something that does this in Spire already (yet). There
are two basic ways I can think of to do this.

The first is the simplest: we would store the modulus as a field in
the number. Then during operations like addition or multiplication, we
would check to ensure that the operands have the same modulus. This
could look something like this:

case class Mod(residue: Long, modulus: Long) { lhs =>
def +(rhs: Mod): Mod = {
require(lhs.modulus == rhs.modulus)
val r = lhs.residue + rhs.residue
if (r >= 0) Mod(r, modulus) else Mod(r + modulus, modulus)
}
// and so on for multiplication, etc.
}

This would work pretty well, and I've considered adding it to
Spire. But what I'd *really* like is for the modulus to be checked at
compile time. You could imagine something like this:

case class Mod[N <: Nat](residue: Long) {
def modulus: N = ???
def +(rhs: Mod[N]): Mod[N] = {
val r = lhs.residue + rhs.residue
if (r >= 0) Mod[N](r) else Mod[N](r + modulus)
}
// and so on...
}

Often in these situations I know the base I am working against (or
it's a fixed parameter). In these cases it would be really nice to
ensure that Mod[3](x) + Mod[5](y) fails at compile-time. Or more
generally, if you have Mod[M](x) + Mod[N](y) then you have to prove
(at compile-time) that M and N are the same literal value.

I've been waiting on SIP-23 [1] to work on this, since without that I
think the syntax and machinery will be a bit too painful to use in
Spire. But I'm definitely open to the first variant (especially since
in some cases it will be difficult or impossible to know what the base
will be at compile-time).

-- Erik

[1] http://docs.scala-lang.org/sips/pending/42.type.html

[Erik Osheim]

Of course I managed to leave the modular part out! Imagine that I
wrote val r = (...) % residue instead. Sorry!

-- Erik

[ndesmoul]

Hi Erik,

Thanks for your answer.

Yes the most simple way seems indeed to store the modulus as a field,
with a class
of the type Mod[A](resi:A, mod:A), where A is any type of positive
Integer (i.e. any element in Z): (int, long, BigInt, etc.).

But what I would like is for this Mod class to be seens as a type of
integer, to be able to develop generic methods that can take as input
either Int, Long, BigInt, or Mod. For example, I think I saw a
Polynomial class in Spire. So typically I would like to be able to
create a Polynomial[Mod[BigInt]], or a Polynomial[Mod[Int]].

As for the last point I'm not knowledgeable enough in Scala arcana, so I
will be able to give a pertinent opinion. But indeed in a lot of cases,
the modulus will not be known in advance.

Nicolas

[Erik Osheim]

Ah, OK, I see what you mean.

In order to plug into Spire's generic machinery you'll need to define
type class instances. In general the residues will always form a ring,
so you can extned spire.algebra.Ring for that.

I figured you might be interested in finite fields, so I cooked up
this example Mod class along with a Field implementation (which
assumes that the modulus is prime). Hopefully this will get you an
idea of how to get started -- it includes an example polynomial:

https://gist.github.com/non/8ac4d82787883dbf136ef13e8d9887ee

Good luck! Feel free to ask more questions here or on our Gitter
channel.

-- Erik

[Nicolas Desmoulins]

Ok. Thanks again for your answer.

I will look into that.

Nicolas

[Nicolas Desmoulins]

Hello Erik,

Sorry to disturb you again, but I just stepped upon a strange behaviour using 'Integral' when using Int and trying to convert it to a BigInt.

Here is a test code:

  import spire.math._
  import spire.implicits._

  def testInt[A: Integral](nb:A) = {
      val n2 = nb * 2  // OK
      val nbBig = n2.toBigInt  // ok with Long, but stack overflow with Int
      // ...
      nbBig
    }


    println(testInt(125L)) // works
    println(testInt(SafeLong(125))) // works
    println(testInt(BigInt(125))) // works
    println(testInt(125)) // fail! -> StackOverflowError

So it works with a Long value. But strangely using Int as input the 'toBigInt' call fails with a StackOverflowError :

Exception in thread "main" java.lang.StackOverflowError
    at spire.std.IntIsReal$class.toBigInt(int.scala:65)
    at spire.math.IntIsIntegral.toBigInt$mcI$sp(Integral.scala:43)
    at spire.std.IntIsReal$class.toBigInt(int.scala:65)
    at spire.math.IntIsIntegral.toBigInt$mcI$sp(Integral.scala:43)
    at spire.std.IntIsReal$class.toBigInt(int.scala:65)

... and so on...

I'm using spire 0.11 with scala 2.11.8.

Another minor problem is that I can't make it work with Short or Byte as it doesn't compile:
println(testInt(125.toByte)) // doesn't compile
println(testInt(125.toShort)) // doesn't compile

I have the following: "could not find implicit value for evidence parameter of type spire.math.Integral[Byte]"

I though that with Integral all integer types could be used (Byte, Short,  Int, ...). Did I understand it wrong, or is there a specific import to do?

Thanks for your help.

Nicolas