class Algebra::Polynomial

Public Class Methods

const(c) click to toggle source
# File lib/algebra/polynomial.rb, line 117
def self.const(c)
  new(c)
end
create(ground, *vs) click to toggle source
Calls superclass method
# File lib/algebra/polynomial.rb, line 51
def self.create(ground, *vs)
  if vs.empty?
    #raise "parameter objects must be given"
    vs = ["x"]
  end
  klass = super(vs.size > 1 ? create(ground, *vs[0..-2]) : ground)
  klass.sysvar(:variable, vs.last)
  klass.sysvar(:display_type, :norm)
  klass
end
euclidian?() click to toggle source
# File lib/algebra/polynomial.rb, line 170
def self.euclidian?
  #    ground.euclidian? or ground.field?
  ground.field?
end
indeterminate(obj) click to toggle source
# File lib/algebra/polynomial.rb, line 84
def self.indeterminate(obj)
  if obj == variable
    new(ground.zero, ground.unity)
  else
    new(ground.indeterminate(obj))
  end
end
monomial(n = 1) click to toggle source
# File lib/algebra/polynomial.rb, line 92
def self.monomial(n = 1)
  m = new(*([ground.zero] * n + [ground.unity]))
  m
end
mvar() click to toggle source
# File lib/algebra/polynomial.rb, line 64
def self.mvar
  g = self
  a = []
  while g <= Algebra::Polynomial
    a.unshift g.var # regulate(g.var)
    g = g.ground
  end
  a
end
new(*coeff) click to toggle source
# File lib/algebra/polynomial.rb, line 47
def initialize(*coeff)
  @coeff = coeff
end
reduction(ring, mod, var) click to toggle source
# File lib/algebra/polynomial-factor.rb, line 89
def self.reduction(ring, mod, var)
  pfx = Algebra.Polynomial(Algebra.ResidueClassRing(ring, mod), var)
  #    def pfx.[](poly)
  def pfx.reduce(poly)
    poly.project(self) { |c, _i| ground[c] }
  end
  pfx
end
to_ary() click to toggle source
# File lib/algebra/polynomial.rb, line 97
def self.to_ary
  [self, *mvar]
end
var() click to toggle source
# File lib/algebra/polynomial.rb, line 105
def self.var
  monomial
end
variables() click to toggle source
# File lib/algebra/polynomial.rb, line 74
def self.variables
  g = self
  a = []
  while g <= Algebra::Polynomial
    a.unshift g.variable
    g = g.ground
  end
  a
end
vars() click to toggle source
# File lib/algebra/polynomial.rb, line 62
def self.vars; mvar; end

Public Instance Methods

%(other)
Alias for: rem
*(other) click to toggle source
Calls superclass method Algebra::AlgebraBase#*
# File lib/algebra/polynomial.rb, line 244
def *(other)
  super { |o|
    d0, d1 = deg, o.deg
    return zero if d0 < 0 or d1 < 0

    # d = [d0, d1].max
    a = (0..(d0+d1)).collect{ground.zero}
    # i = j = 0
    0.upto d0 do |i|
      0.upto d1 do |j|
        a[i+j] += self[i]*o[j]
      end
    end
    self.class.new(*a)
  }
end
+(other) click to toggle source
Calls superclass method Algebra::AlgebraBase#+
# File lib/algebra/polynomial.rb, line 215
def +(other)
  super { |o|
    d0, d1 = deg, o.deg
    d = [d0, d1].max
    a = []
    # i = 0
    0.upto d do |i|
      c = (i <= d0 ? self[i] : ground.zero)
      d = (i <= d1 ? o[i] : ground.zero)
      a.push( c + d )
    end
    self.class.new(*a)
  }
end
-(other) click to toggle source
Calls superclass method Algebra::AlgebraBase#-
# File lib/algebra/polynomial.rb, line 230
def -(other)
  super { |o|
    d0, d1 = deg, o.deg
    d = [d0, d1].max
    a = []
    # i = 0
    0.upto d do |i|
      a.push( (i <= d0 ? self[i] : ground.zero) -
      (i <= d1 ? o[i] : ground.zero))
    end
    self.class.new(*a)
  }
end
/(other)
Alias for: div
<=>(o) click to toggle source
# File lib/algebra/polynomial.rb, line 200
def <=>(o)
  d0, d1 = deg, o.deg
  return d0 <=> d1 unless d0 == d1
  d = d0
  if ground.method_defined? :<=>
    0.upto d do |i|
      c0, c1 = self[i], o[i]
      unless (c = (c0 <=> c1)).zero?
        return c
      end
    end
  end
  0
end
==(other) click to toggle source
Calls superclass method Algebra::AlgebraBase#==
# File lib/algebra/polynomial.rb, line 188
def ==(other)
  super {|o|
    d0, d1 = deg, o.deg
    return false unless d0 == d1
    d = d0
    0.upto d do |i|
      return false unless self[i] == o[i]
    end
    true
  }
end
[](x) click to toggle source
# File lib/algebra/polynomial.rb, line 142
def [](x)
  @coeff[x] || ground.zero
end
[]=(x, v) click to toggle source
# File lib/algebra/polynomial.rb, line 146
def []=(x, v)
  @coeff[x]= v
end
_inspect()
Alias for: inspect
call(*a)
Alias for: evaluate
callL(x)
Alias for: evaluateL
callR(*a)
Alias for: evaluateR
compact!() click to toggle source
# File lib/algebra/polynomial.rb, line 175
def compact!
  d = deg
  @coeff.slice!((d+1)..-1) if d >= 0
  self
end
constant?() click to toggle source
# File lib/algebra/polynomial.rb, line 121
def constant?
  deg <= 0
end
convert_to(ring) click to toggle source
# File lib/algebra/polynomial.rb, line 500
def convert_to(ring)
  project(ring){|c, n| c}
end
deg() click to toggle source
# File lib/algebra/polynomial.rb, line 181
def deg
  i = size - 1
  i -= 1 while i >= 0 && self[i].zero?
  #    i >= 0 ? i : nil
  i
end
derivate() click to toggle source
# File lib/algebra/polynomial.rb, line 504
def derivate
  e = zero
  n = size - 1
  reverse_each do |c|
    e = e * var + c * n
    break if n <= 1
    n -= 1
  end
  e
end
div(other) click to toggle source
# File lib/algebra/polynomial.rb, line 295
def div(other)
  if o = regulate(other)
    divmod(o).first
  else
    raise "unknown divisor self.class #{other.class}"
  end
end
Also aliased as: /
divide?(other) click to toggle source
# File lib/algebra/polynomial.rb, line 315
def divide?(other)
  _q, r = other.divmod(self)
  r.zero?
end
divmod(o) click to toggle source
# File lib/algebra/polynomial.rb, line 276
def divmod(o)
  raise ZeroDivisionError, "divisor is zero" if o.zero?
  d0, d1 = deg, o.deg
  if d1 <= 0
    [self.class.new(*collect{|c|
      c / o.lc
      }), zero
    ]
  elsif d0 < d1
    [zero, self]
  else
    tk = monomial(d0 - d1) * ground_div(lc, o.lc)
    e = rt - o.rt * tk
    #      e.compact!
    q, r = e.divmod(o)
    [q + tk, r]
  end
end
each(&b) click to toggle source

def self.[](obj)

ground = obj
monomial

end

# File lib/algebra/polynomial.rb, line 130
def each(&b)
  @coeff.each(&b)
end
evaluate(*a) click to toggle source
# File lib/algebra/polynomial.rb, line 449
def evaluate(*a)
  #project(self.class, x){|c, n| c}
  x = a.last
  if a.size > 1
    project(ground, x){|c, n| c.evaluate(* a[0...-1])}
  elsif a.size == 1
    project(ground, x){|c, n| c}
  else
    raise "can't evaluate"
  end
end
Also aliased as: evaluateR, call
evaluateL(x) click to toggle source
# File lib/algebra/polynomial.rb, line 490
def evaluateL(x)
  projectL(ground, x){|c, n| c}
end
Also aliased as: callL
evaluateR(*a)
Also aliased as: callR
Alias for: evaluate
evaluate_old(obj) click to toggle source
# File lib/algebra/polynomial.rb, line 431
def evaluate_old(obj)
  e = ground.zero
  reverse_each do |c|
    e = e * obj + c
  end
  e
end
factorize_alg(s = 0) click to toggle source
# File lib/algebra/polynomial-factor-alg.rb, line 42
def factorize_alg(s = 0)
  return Algebra::Factors.new([[self, 1]]) if deg <= 1

  t = ground.var
  x = var
  sf = sqfree.monic

  nm = sf.evaluate(x - t * s).norm
  fac0 = Algebra::Factors.new
  nm.factorize.each do |f0, n|
    next if f0.deg <= 0
    g = f0.convert_to(self.class).evaluate(x + t * s)
    g = g.gcd(sf).monic
    if n == 1
      fac0.multiply g
    elsif n >= 2
      h = g.factorize_alg(s + 1)
      fac0.concat h
    end
  end
  fac0.fact_all(self).correct_lc!(self)
end
factorize_alg_old() click to toggle source
# File lib/algebra/polynomial-factor-alg.rb, line 20
def factorize_alg_old
  #    if !respond_to?(:deg) or deg <= 1
  return Algebra::Factors.new([[self, 1]]) if deg <= 1

  t = ground.var
  x = var
  sf = sqfree.monic

  n = 0
  loop do
    nm = sf.norm
    break if nm.sqfree?
    n += 1
    sf = sf.evaluate(x - t)
  end
  fac = nm.factorize
  fac.map! do |f0|
    f0.convert_to(self.class).gcd(sf).evaluate(x + t * n).monic
  end
  fac.fact_all(self).correct_lc!(self)
end
ground_div(n, d) click to toggle source
# File lib/algebra/polynomial.rb, line 261
def ground_div(n, d)
  if ground.field?
    n / d
  elsif ground.euclidian?
    q, r = n.divmod(d)
    raise "devide #{n} by #{d} in #{n.class}" unless r.zero?
    q
  else
    q = n / d
    r = n - q*d
    raise "devide #{n} by #{d} in #{n.class}" unless r.zero?
    q
  end
end
inspect()
Also aliased as: _inspect
Alias for: to_s
lc() click to toggle source
# File lib/algebra/polynomial.rb, line 349
def lc
  self[deg]
end
lm() click to toggle source
# File lib/algebra/polynomial.rb, line 353
def lm
  monomial(deg)
end
lt() click to toggle source
# File lib/algebra/polynomial.rb, line 357
def lt
  lc * lm
end
monic() click to toggle source
# File lib/algebra/polynomial.rb, line 365
def monic
  self / lc
end
monomial(n = 1) click to toggle source
# File lib/algebra/polynomial.rb, line 101
def monomial(n = 1)
  self.class.monomial(n)
end
monomial?() click to toggle source
# File lib/algebra/polynomial.rb, line 150
def monomial?
  flag = false
  each do |x|
    unless x.zero?
      #       if !flag && x.respond_to?(:monomial?) && x.monomial?
      if !flag# && x.respond_to?(:monomial?) && x.monomial?
        flag = true
      else
        return false
      end
      #       if flag || !x.respond_to?(:monomial?) || !x.monomial?
      #         return false
      #       else
      #         flag = true
      #       end
    end
  end
  flag
end
move_const(a, coef = 1) click to toggle source
# File lib/algebra/polynomial.rb, line 496
def move_const(a, coef = 1)
  evaluate(self.class.var + a*coef)
end
need_paren_in_coeff?() click to toggle source

def cont; @coeff.first.gcd_all(* @coeff); end def pp; self / cont; end

# File lib/algebra/polynomial.rb, line 372
def need_paren_in_coeff?
  if constant?
    c = @coeff[0]
    if c.respond_to?(:need_paren_in_coeff?)
      c.need_paren_in_coeff?
    elsif c.is_a?(Numeric)
      false
    else
      true
    end
  elsif !monomial?
    true
  else
    false
  end
end
pdiv(other) click to toggle source
# File lib/algebra/polynomial.rb, line 333
def pdiv(other)
  if o = regulate(other)
    pdivmod(o).first
  else
    raise "unknown divisor self.class #{other.class}"
  end
end
pdivmod(other) click to toggle source
# File lib/algebra/polynomial.rb, line 320
def pdivmod(other)
  if o = regulate(other)
    deg0, deg1 = deg,  o.deg
    if deg0 < deg1
      [zero, self]
    else
      ((o.lc)**(deg0 - deg1 + 1) * self).divmod(o)
    end
  else
    raise "unknown divisor self.class #{other.class}"
  end
end
prem(other) click to toggle source
# File lib/algebra/polynomial.rb, line 341
def prem(other)
  if _o = regulate(other)
    pdivmod(other).last
  else
    raise "unknown divisor self.class #{other.class}"
  end
end
project(ring, x = ring.var) { |c, n| ... } click to toggle source
# File lib/algebra/polynomial.rb, line 439
def project(ring, x = ring.var)
  e = ring.zero
  n = size
  reverse_each do |c|
    n -= 1
    e = e * x + yield(c, n)
  end
  e
end
projectL(ring = self.class, x = ring.var) { |c, n| ... } click to toggle source
# File lib/algebra/polynomial.rb, line 480
def projectL(ring = self.class, x = ring.var)
  e = ring.zero
  n = size
  reverse_each do |c|
    n -= 1
    e = x * e + yield(c, n)
  end
  e
end
rem(other) click to toggle source
# File lib/algebra/polynomial.rb, line 305
def rem(other)
  if o = regulate(other)
    divmod(o)[1]
  else
    raise "unknown divisor self.class #{other.class}"
  end
end
Also aliased as: %
resultant(other) click to toggle source
# File lib/algebra/polynomial.rb, line 533
def resultant(other)
  sylvester_matrix(other).determinant
end
reverse_each(&b) click to toggle source
# File lib/algebra/polynomial.rb, line 134
def reverse_each(&b)
  @coeff.reverse_each(&b)
end
rt() click to toggle source
# File lib/algebra/polynomial.rb, line 361
def rt
  self - lt
end
size() click to toggle source
# File lib/algebra/polynomial.rb, line 138
def size
  @coeff.size
end
sub(var, value) click to toggle source
# File lib/algebra/polynomial.rb, line 465
def sub(var, value)
  vs = self.class.vars
  if i = vs.index(var)
    vs = vs.dup
    vs[i] = value
    evaluate(*vs)
  else
    raise "#{var} is not a variable"
  end
end
sylvester_matrix(o, k = 0) click to toggle source
# File lib/algebra/polynomial.rb, line 515
def sylvester_matrix(o, k = 0)
  m, n = deg, o.deg
  if k.zero?
    sm = Algebra.SquareMatrix(ground, m + n - 2*k)
  else
    sm = Algebra.MatrixAlgebra(ground, m + n - 2*k, m + n - k)
  end
  sm.matrix{|i, j|
    if i < n - k
      i0 = j - i
      i0 >= 0 && i0 <= m ? self[m-i0] : ground.zero
    else
      i0 = j - i + n - k
      i0 >= 0 && i0 <= n ? o[n-i0] : ground.zero
    end
  }
end
to_proc() click to toggle source
# File lib/algebra/polynomial.rb, line 461
def to_proc
  Proc.new{|*a| evaluate(*a)}
end
to_s() click to toggle source
# File lib/algebra/polynomial.rb, line 389
def to_s
  a = []
  case self.class.display_type
  when :code
    pr, po =  "*",  "**"
  else
    pr, po =  "",  "^"
  end

  x = variable ? variable.to_s : "x"
  each_with_index do |c, i|
    next if c.zero?
    s = case i
    when 0
      c.to_s
    else
      c = if c == 1
        ""
      elsif c == -1
        "-"
      elsif c.respond_to?(:need_paren_in_coeff?)
        if c.need_paren_in_coeff?
          "(#{c})" + pr
        else
          c.to_s + pr
        end
      elsif c.is_a?(Numeric)
        c.to_s + pr
      else
        "(#{c})" + pr
      end
      i == 1 ? c + x :  c + x + "#{po}#{i}"
    end
    a.unshift s
  end
  a.unshift "0" if a.empty?
  a.join(" + ").gsub(/\+ -/, "- ")
end
Also aliased as: inspect
value_on_one(ring, n = 0) click to toggle source
# File lib/algebra/m-polynomial-factor.rb, line 286
def value_on_one(ring, n = 0)
  e = ring.zero
  x = ring.vars[n]
  reverse_each do |c|
    e = e * x + c
  end
  e
end
var() click to toggle source
# File lib/algebra/polynomial.rb, line 109
def var
  self.class.monomial
end
variable() click to toggle source
# File lib/algebra/polynomial.rb, line 113
def variable; self.class.variable; end
variable=(bf) click to toggle source
# File lib/algebra/polynomial.rb, line 115
def variable=(bf); self.class.variable = bf; end