fork download
copy 
  1. import scala.collection.mutable.{HashMap => HMap}
  2.  
  3. case class Rational(n: Int, d: Int) extends Ordered[Rational] {
  4.   def gcd(a:Int, b:Int):Int = {
  5.     if (a == 0) b
  6.     else if (b == 0) a
  7.     else if (a < 0) gcd(-a,b)
  8.     else if (b < 0) gcd(a,-b)
  9.     else if (a<b) gcd(b,a)
  10.     else gcd(b, a%b)
  11.   }
  12.   def sgn(a:Int) = if (a < 0) -1 else if (a > 0) 1 else 0
  13.   val numer: Int = n/gcd(n,d)*sgn(d)
  14.   val denom: Int = d/gcd(n,d)*sgn(d)
  15.   def isZero: Boolean = (n==0)
  16.   def compare(that:Rational):Int = numer*that.denom - denom*that.numer
  17.   def equals(that:Rational) = numer*that.denom == denom*that.numer
  18.   def +(rhs:Rational):Rational = Rational(numer*rhs.denom + denom*rhs.numer, denom*rhs.denom)
  19.   def -(rhs:Rational):Rational = Rational(numer*rhs.denom - denom*rhs.numer, denom*rhs.denom)
  20.   def *(rhs:Rational):Rational = Rational(numer*rhs.numer, denom*rhs.denom)
  21.   def /(rhs:Rational):Rational = Rational(numer*rhs.denom, denom*rhs.numer)
  22.   override def toString = if (denom==1) numer.toString else s"${numer}/${denom}"
  23.   def unary_- : Rational = Rational(-numer,denom)
  24. }
  25. case class Mono2(val c: Rational, val degX: Int, val degY: Int) extends Ordered[Mono2]{
  26.   def apply(n: Int, nx: Int, ny:Int) = Mono2(Rational(n,1), nx, ny)
  27.   def *(rhs:Mono2):Mono2 = Mono2(c*rhs.c, degX+rhs.degX, degY+rhs.degY)
  28.   def isZero: Boolean = c.isZero
  29.   def totalDeg: Int = degX+degY
  30.   def compare(that: Mono2):Int = grlex(that)
  31.   def lex(that: Mono2): Int = if (degX==that.degX) degY-that.degY else degX-that.degX
  32.   def grlex(that:Mono2): Int = if (totalDeg==that.totalDeg) degX-that.degX else totalDeg-that.totalDeg
  33.   def grevlex(that:Mono2): Int = if (totalDeg==that.totalDeg) -(degY-that.degY) else totalDeg-that.totalDeg
  34.   override def toString =(c.toString) +
  35.     (if (degX==0) "" else if (degX==1) "x" else "x^"+degX.toString) +
  36.     (if (degY==0) "" else if (degY==1) "y" else "y^"+degY.toString)
  37.   def /(rhs:Mono2): Option[Mono2] = if (rhs.degX <= degX && rhs.degY <= degY) Some(Mono2(c/rhs.c, degX-rhs.degX, degY-rhs.degY)) else None
  38. }
  39. case class Poly2(xs: List[Mono2]) extends Ordered[Poly2] {
  40.   val monos: List[Mono2] = normalize(xs)
  41.   def compare(that:Poly2): Int = (monos, that.monos) match {
  42.     case (Nil,Nil) => 0
  43.     case (Nil,_) => -1
  44.     case (_,Nil) => 1
  45.     case _ => monos.head.compare(that.monos.head)
  46.   }
  47.   override def toString = monos.mkString("+")
  48.   def isZero:Boolean = monos.length == 0
  49.   def multideg:(Int,Int) = monos.head match {case Mono2(_,nx,ny) => (nx,ny)}
  50.   def lc: Rational = monos.head match {case Mono2(c,_,_) => c}
  51.   def lm: Mono2 = monos.head match {case Mono2(c,nx,ny) => Mono2(Rational(1,1),nx,ny)}
  52.   def lt: Mono2 = monos.head
  53.   def normalize(xs: List[Mono2]): List[Mono2] = {
  54.     val m: HMap[(Int,Int),Rational] = HMap.empty
  55.     xs.foreach {case Mono2(c,nx,ny) => {
  56.       m.get((nx,ny)) match {
  57.         case None => m((nx,ny)) = c
  58.         case Some(c1) => m((nx,ny)) = c + c1
  59.       }
  60.     }}
  61.     m.toList.map{case ((nx,ny),c) => Mono2(c,nx,ny)}.filter{m => !(m.isZero)}.sorted.reverse
  62.   }
  63.   def +(rhs:Poly2):Poly2 = {
  64.     Poly2(normalize(monos++rhs.monos))
  65.   }
  66.   def -(rhs:Poly2):Poly2 = {
  67.     Poly2(normalize(monos++ rhs.monos.map{case Mono2(c,nx,ny) => Mono2(-c,nx,ny)}))
  68.   }
  69.   def *(rhs:Poly2):Poly2 = {
  70.     Poly2(normalize(
  71.       for(Mono2(c1,nx1,ny1) <- monos; Mono2(c2,nx2,ny2) <- rhs.monos)
  72.       yield Mono2(c1*c2, nx1+nx2, ny1+ny2)
  73.     ))
  74.   }
  75.   def *(rhs:Mono2):Poly2 = if (rhs.isZero) Poly2(List(Mono2(Rational(0,1),0,0))) else {
  76.     Poly2(monos.map{case Mono2(c,nx,ny) => Mono2(c*rhs.c, nx+rhs.degX, ny+rhs.degY)})
  77.   }
  78.   def divMod(rhs:Poly2): (Poly2,Poly2) = {
  79.     if (isZero) (this, rhs)
  80.     else if (rhs.isZero) throw new Exception("div by zero")
  81.     else {
  82.       (lt / rhs.lt) match {
  83.         case None => (Poly2(Nil), this)
  84.         case Some(p) => {
  85.           val (p1,q1) = (this-rhs*p).divMod(rhs)
  86.           (Poly2(p::Nil)+p1,q1)
  87.         }
  88.       }
  89.     }
  90.   }
  91.   def divMod(fs: List[Poly2]): (List[Poly2],Poly2) = {
  92.     val aa:Array[Poly2] = fs.map{f => Poly2(Nil)}.toArray
  93.     var rr:Poly2 = Poly2(Nil)
  94.     var pp:Poly2 = this
  95.     while(!(pp.isZero)) {
  96.       var dived:Boolean = false
  97.       var i = 0
  98.       while(i < fs.length && !dived) {
  99.         (pp.lt / fs(i).lt) match {
  100.           case Some(t) => {aa(i) = aa(i) + Poly2(List(t)); pp = pp - fs(i)*t; dived = true}
  101.           case None => {i += 1}
  102.         }
  103.       }
  104.       if (!dived) {rr = rr + Poly2(List(pp.lt)); pp = Poly2(pp.monos.tail)}
  105.     }
  106.     (aa.toList,rr)
  107.   }
  108. }
  109. object Main {
  110.   implicit def toRational(n:Int): Rational = Rational(n,1)
  111.   def main(args: Array[String]) = {
  112.     val f = Poly2(List(Mono2(1,7,2), Mono2(1,3,2), Mono2(-1,0,1), Mono2(1,0,0)))
  113.     val f1 = Poly2(List(Mono2(1,1,2),Mono2(-1,1,0)))//> f1  : foo.Poly2 = 1xy^2+-1x
  114.     val f2 = Poly2(List(Mono2(1,1,0),Mono2(-1,0,3)))//> f2  : foo.Poly2 = -1y^3+1x
  115.   	println(f divMod List(f1,f2))
  116.   	println(f divMod List(f2,f1))
  117.   }
  118. }
Success #stdin #stdout 0.42s 382144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(List(1x^6+1x^2, ),1x^7+1x^3+-1y+1)
(List(, 1x^6+1x^2),1x^7+1x^3+-1y+1)
https://ideone.com/BUbIU8
language:
Scala (scala 2.12.8)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!