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_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_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