orbital.math
Interface Euclidean

All Superinterfaces:

Arithmetic, Normed

All Known Subinterfaces:

Integer, UnivariatePolynomial

public interface Euclidean
extends Arithmetic

Euclidean ring interface.

Let R be an integrity domain.

Euclidean ring

R is an Euclidean ring :<=> exist δ:R\{0}->N

for all f in R for all g in R\{0} exist q,r in R such that f = qg + r = (f div g)g + (f mod g)

with δ(r) < δ(g) or r = 0.

δ is called Euclidean degree of R. The Euclidean "quotient" q is denoted by f div g, the Euclidean remainder r is denoted by f mod g.

=> Properties:
• the Euclidean algorithm can compute greatest common divisors in R.
• R is a principal ideal integrity domain, therefore implying that for all a,b,d,m in R\{0}
  • (d)=(a)+(b) <=> d=gcd(a,b)
  • (m)=(a) section (b) <=> m=lcm(a,b)
  • (m)=(a)(b) <=> m=ab (always)
• for all a,b in R\{0} exist gcd(a,b) in R and (gcd(a,b)) = (a,b)

Author:

André Platzer

Method Summary

Integer	degree() Get the Euclidean degree.
Euclidean	modulo(Euclidean g) Get the Euclidean remainder, modulo g.
Euclidean	quotient(Euclidean g) Get the Euclidean "quotient" by g.

Methods inherited from interface orbital.math.Arithmetic

add, divide, equals, inverse, isOne, isZero, minus, multiply, one, power, scale, subtract, toString, zero

Methods inherited from interface orbital.math.Normed

norm

Method Detail

degree

Integer degree()

Get the Euclidean degree. In case R is a discrete valuation ring, this also is the valuation of Quot(R).

Returns:

the Euclidean degree δ(this) of this value.

Postconditions:

RES=δ(this)

quotient

Euclidean quotient(Euclidean g)

Get the Euclidean "quotient" by g.

Returns:

this div g in R.

Throws:

java.lang.IllegalArgumentException - if the argument type is illegal for this operation. Note: for single type handling it is also allowed to throw a ClassCastException, instead.

Postconditions:

this.equals(RES.multiply(g).add(this.modulo(RES)))

Note:

the Euclidean quotient f div g is distinct from the fractional quotient f/g=f.divide(g).

modulo

Euclidean modulo(Euclidean g)

Get the Euclidean remainder, modulo g.

Returns:

this mod g in R.

Throws:

java.lang.IllegalArgumentException - if the argument type is illegal for this operation. Note: for single type handling it is also allowed to throw a ClassCastException, instead.

Postconditions:

RES.degree() < g.degree() or RES==0 and this.equals(this.quotient(g).multiply(g).add(RES))