module Algebra::EuclidianRing

Public Instance Methods

cont() click to toggle source
# File lib/algebra/euclidian-ring.rb, line 119
def cont
  t = nil
  each do |x|
    break if t && t.unit?
    t = t ? t.gcd_rec(x) : x
  end
  t ? t : self
end
cont_pp() click to toggle source
# File lib/algebra/euclidian-ring.rb, line 129
def cont_pp; [c = cont, self / c]; end
gcd(n) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 31
def gcd(n)
  m = self
  while n != 0
    m %= n
    tmp = m; m = n; n = tmp
  end
  m
end
gcd3(b) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 22
def gcd3(b)
  x, y = self, b
  until y.zero?
    _q, r = x.divmod y
    x, y = y, r
  end
  x
end
gcd_all(*a) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 40
def gcd_all(*a)
  t = self
  a.each do |x|
    t = t.gcd(x)
  end
  t
end
gcd_coeff(g)
Alias for: gcd_ext
gcd_coeff0(b) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 63
def gcd_coeff0(b)
  if b.zero?
    [self, unity, zero]
  else
    q, r = divmod b
    d, x, y = b.gcd_coeff(r)
    [d, y, x - y * q]
  end
end
gcd_coeff_all(*a0) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 73
def gcd_coeff_all(*a0)
  return [self, self] if a0.empty?
  t, *a = a0
  d, x, y = gcd_ext(t)
  r = [x, y]
  a.each do |u|
    d, x, y = d.gcd_coeff(u)
    r = r.collect{|v| x*v} + [y]
  end
  [d] + r
end
Also aliased as: gcd_ext_all
gcd_ext(g) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 48
def gcd_ext(g)
  h, s = self, g
  a, b = self.class.unity, self.class.zero
  c, d = self.class.zero, self.class.unity
  loop do
    q, r = h.divmod s
    return [s, c, d] if r.zero?
    h, s = s, r # r == h - q * s
    a, c = c, a - q * c
    b, d = d, b - q * d
  end
end
Also aliased as: gcd_coeff
gcd_ext_all(*a0)
Alias for: gcd_coeff_all
gcd_rec(b) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 96
def gcd_rec(b)
  return self if b.zero?
  return b if zero?
  if is_a?(Polynomial) && !ground.field?
    ac, ap = cont_pp
    bc, bp = b.cont_pp
    c = ac.gcd_rec(bc)
    x, y = ap, bp
    until y.zero?
      q, r = x.pdivmod y
      x, y = y, r
    end
    x.pp * c
  else
    x, y = self, b
    until y.zero?
      q, r = x.pdivmod y
      x, y = y, r
    end
    x
  end
end
lcm(b) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 10
def lcm(b)
  self * b / gcd(b)
end
lcm_all(*a) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 14
def lcm_all(*a)
  t = self
  a.each do |x|
    t = t.lcm(x)
  end
  t
end
pgcd(b) click to toggle source
# File lib/algebra/euclidian-ring.rb, line 87
def pgcd(b)
  x, y = self, b
  until y.zero?
    _q, r = x.pdivmod y
    x, y = y, r
  end
  x
end
pp() click to toggle source
# File lib/algebra/euclidian-ring.rb, line 128
def pp; self / cont; end