Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Евклидово кольцо

Евклидово кольцо — это коммутативное кольцо с единицей, в котором определена функция, называемая евклидовой нормой, позволяющая обобщить алгоритм Евклида для нахождения наибольшего общего делителя (НОД). Евклидовы кольца являются важным классом алгебраических структур, обобщающих свойства целых чисел и многочленов.

Определение евклидова кольца

Евклидово кольцо — это коммутативное кольцо с единицей \(R\), на котором задана функция \(\nu: R \setminus {0} \to \mathbb{N}_0\) (называемая евклидовой нормой), удовлетворяющая следующим условиям:

Примеры евклидовых колец

Свойства евклидовых колец

Зачем нужны евклидовы кольца?

Евклидовы кольца находят применение в различных областях:

Формальное определение

Евклидово кольцо — это кольцо НОД, которое также поддерживает евклидово деление (например, поэтапное или целочисленное деление).

Формально евклидовы кольца определяют евклидову функцию f такую, что для любого x и y в A, если y ненулевое, то существуют q и r (частное и остаток) такие, что a = b*q + r и r = 0 или f(r) < f(b). Для целых чисел обычно f - это функция абсолютного значения.

EuclideanRing[A] добавляет следующие операции:

В целых числах евклидово частное и остаток соответствуют делению с остатком; однако знак результата является вопросом соглашения. Для рациональных чисел (или с плавающей запятой) a /~ b = a / b и a % b = 0 по определению.

Помимо законов кольца НОД:

должен соблюдаться закон:

Код

trait EuclideanRing[A] extends GCDRing[A]:
  def quot(x: A, y: A): A

  def mod(x: A, y: A): A

Числа относительно сложения с 0 и умножения с 1

(Z, +, *)

given EuclideanRing[Int] with
  val empty: Int                   = 0
  val one: Int                     = 1
  def combine(x: Int, y: Int): Int = x + y
  def times(x: Int, y: Int): Int   = x * y
  def gcd(x: Int, y: Int): Int = if y == 0 then x else gcd(y, x % y)
  def lcm(x: Int, y: Int): Int                 = times(x, y) / gcd(x, y)
  def quot(x: Int, y: Int): Int                = x / y
  def mod(x: Int, y: Int): Int                 = x % y
  extension (a: Int) override def inverse: Int = -a

Законы

Законы наследуются от Кольца НОД.

Кроме того:

... // Законы кольца НОД

def checkQuotModMultiplication[A](x: A, y: A)(using
    er: EuclideanRing[A]
): ValidatedNel[String, Unit] =
  Either.cond[String, Unit](
    er.combine(er.times(y, er.quot(x, y)), er.mod(x, y)) == x,
    (),
    "Для частного и остатка должен соблюдаться закон: b * (a /~ b) + (a % b) = a"
  ).toValidatedNel

Схема

classDiagram
    class Semigroup~A~{
        +combine(x: A, y: A) A
    }  
    class Monoid~A~{
        +empty() A
    }
    Semigroup <|-- Monoid
    class CommutativeSemigroup~A~
    Semigroup <|-- CommutativeSemigroup  
    class Group~A~{
      +inverse(x: A) A
    }  
    Monoid <|-- Group 
    class CommutativeMonoid~A~
    Monoid <|-- CommutativeMonoid
    CommutativeSemigroup <|-- CommutativeMonoid
    class AbelianGroup~A~
    Group <|-- AbelianGroup
    CommutativeMonoid <|-- AbelianGroup
    class Semiring~A~
    CommutativeMonoid <|-- Semiring
    class MultiplicativeSemigroup~A~{
        +times(x: A, y: A) A
    }
    MultiplicativeSemigroup <|-- Semiring
    Semigroup .. MultiplicativeSemigroup
    class Ring~A~
    AbelianGroup <|-- Ring
    Semiring <|-- Ring
    class CommutativeSemiring~A~
    Semiring <|-- CommutativeSemiring
    class SemiringWithUnity~A~{
        +one() A
    }
    Semiring <|-- SemiringWithUnity
    class CommutativeRing~A~
    Ring <|-- CommutativeRing
    CommutativeSemiring <|-- CommutativeRing
    class RingWithUnity~A~
    Ring <|-- RingWithUnity
    SemiringWithUnity <|-- RingWithUnity
    class CommutativeRingWithUnity~A~
    CommutativeRing <|-- CommutativeRingWithUnity
    RingWithUnity <|-- CommutativeRingWithUnity
    class GCDRing~A~{
        +gcd(x: A, y: A) A
        +lcm(x: A, y: A) A
    }
    CommutativeRingWithUnity <|-- GCDRing
    class EuclideanRing~A~{
        +quot(x: A, y: A) A
        +mod(x: A, y: A) A
    }
    GCDRing <|-- EuclideanRing

Реализация в библиотеках

Реализация в Spire

import spire.algebra.EuclideanRing
import spire.std.int.*

EuclideanRing.plus(15, 10)
// val res0: Int = 25
EuclideanRing.times(15, 10)
// val res1: Int = 150
EuclideanRing.pow(15, 2)
// val res2: Int = 225
EuclideanRing.negate(15)
// val res3: Int = -15
EuclideanRing.minus(15, 10)
// val res4: Int = 5
EuclideanRing.zero[Int]
// val res5: Int = 0
EuclideanRing.one[Int]
// val res6: Int = 1
EuclideanRing.gcd(15, 10)
// val res7: Int = 5
EuclideanRing.lcm(15, 10)
// val res8: Int = 30
EuclideanRing.equot(15, 10)
// val res9: Int = 1
EuclideanRing.emod(15, 10)
// val res10: Int = 5
EuclideanRing.equotmod(15, 10)
// val res11: (Int, Int) = (1,5)

Ссылки: