class Silicium::Algebra::PolynomialDivision

TODO: class docs

Constants

DELTA

Public Instance Methods

build_polynom_from_coeffs(coefficients) click to toggle source
# File lib/polynomial_division.rb, line 96
def build_polynom_from_coeffs(coefficients)
  "#{coefficients[0]}*x**#{coefficients.size - 1}" +
    coefficients[1..-1].each_with_index.inject('') do |acc, (coefficient, index)|
      leading_sign = coefficient >= 0 ? '+' : ''
      acc + "#{leading_sign}#{coefficient}*x**#{ coefficients.size - index - 2 }"
    end
end
compare_polynoms(poly1, poly2) click to toggle source
# File lib/polynomial_division.rb, line 82
def compare_polynoms(poly1, poly2)
  polynom_parser(poly1).size - polynom_parser(poly2).size
end
polynom_division(poly_1, poly_2) click to toggle source

This function returns array of 2 strings: first is the result of division polynom poly_1 on polynom poly_2 Second - remainder

# File lib/polynomial_division.rb, line 63
def polynom_division(poly_1, poly_2)
  coeff_1 = polynom_parser(poly_1)
  coeff_2 = polynom_parser(poly_2)
  res_size = coeff_1.size - coeff_2.size + 1
  coeff_result = Array.new(res_size)
  sgn_array = Array.new(res_size + 1,'')
  (0..res_size-1).each do |i|
    cur_coeff = coeff_1[i] / coeff_2[0]
    coeff_result[i] = cur_coeff
    coeff_result[i] < 0 ? sgn_array[i] = '-' : sgn_array[i] = '+'
    (0..coeff_2.size-1).each do |j|
      coeff_1[i+j] -= coeff_2[j]*cur_coeff
    end
  end
  res_exp = str_res_impl(coeff_result, sgn_array)
  rem_exp = str_rem_impl(coeff_1[coeff_result.size..coeff_1.size-1])
  [res_exp, rem_exp]
end
polynom_gcd(poly1, poly2, delta = DELTA) click to toggle source

This function returns a string: greatest common integer divisor of two polynoms

# File lib/polynomial_division.rb, line 105
def polynom_gcd(poly1, poly2, delta = DELTA)
  divisor, remainder = order_gcd_operands(poly1, poly2)
  until zero_coeffs?(remainder) do
    division = polynom_division(divisor, remainder)
    divisor = remainder
    remainder = division[1]
  end
  normalizer = polynom_parser(divisor)[0]
  temp_result = polynom_division(divisor, normalizer.to_s+'*x**0')[0]
  coefficients = round_coeffs(polynom_parser(temp_result), delta)
  build_polynom_from_coeffs(coefficients)
end
polynom_parser(str) click to toggle source

This function returns an array of coefficients obtained by parsing input string in format: “<coeff>x*<degree>+…” Even if in your expression don't exist x with some degree, you should to write it with 0 coefficient Also free term you should to write with 0 degree Example: “2*x**5-3*x**4+0*x**3+0*x**2-5*x**1-6*x**0”

# File lib/polynomial_division.rb, line 15
def polynom_parser(str)
  copy_str = str.clone
  sgn_array = []                    # Array of signs
  if copy_str[0] != '-'
    sgn_array.push('+')
  else
    sgn_array.push('-')
    copy_str[0] = ''
  end
  token = copy_str.split(/[-+]/)
  (0..copy_str.size-1).each do |i|
    sgn_array.push(copy_str[i]) if copy_str[i] == '-' || copy_str[i] == '+'
  end
  size = token.size - 1
  coeff = []                 # Array of coefficients
  (0..size).each do |i|
    degree = token[i].split('*')    # Split by '*' to get coefficient and degree
    degree[0] == 'x' ? coeff[i] = 1.0 : coeff[i] = degree[0].to_f
    coeff[i] *= -1 if sgn_array[i] == '-'
  end
  coeff
end
round_coeffs(coefficients, delta = DELTA) click to toggle source
# File lib/polynomial_division.rb, line 90
def round_coeffs(coefficients, delta = DELTA)
  coefficients.map do |element|
    (element.round - element).abs < delta ? element.round.to_f : element
  end
end
str_rem_impl(coeff_1) click to toggle source

String implementation of remained part

# File lib/polynomial_division.rb, line 50
def str_rem_impl(coeff_1)
  c = coeff_1.size
  rem_exp = ""
  (0..c-1).each do |i|
    rem_exp += '+' if coeff_1[i] >= 0.0
    rem_exp += ((coeff_1[i].ceil(3)).to_s+"*x**"+(c - i - 1).to_s)
  end
  rem_exp[0] = '' if rem_exp[0] == '+'
  rem_exp
end
str_res_impl(coeff_res, sgn_array) click to toggle source

String implementation of result

# File lib/polynomial_division.rb, line 39
def str_res_impl(coeff_res, sgn_array)
  res_size = coeff_res.size
  res_exp = ""
  (0..res_size-1).each do |i|
    res_exp += ((coeff_res[i].ceil(3)).to_s+"*x**"+(res_size - i - 1).to_s)
    res_exp += sgn_array[i+1] if sgn_array[i+1] != '-'
  end
  res_exp
end
zero_coeffs?(polynom, delta = DELTA) click to toggle source
# File lib/polynomial_division.rb, line 86
def zero_coeffs?(polynom, delta = DELTA)
  polynom_parser(polynom).all?{ |item| item.abs < delta }
end

Private Instance Methods

order_gcd_operands(poly1, poly2) click to toggle source
# File lib/polynomial_division.rb, line 120
def order_gcd_operands(poly1, poly2)
  if compare_polynoms(poly1, poly2) >= 0
    divisor = poly2
    remainder = polynom_division(poly1, divisor)[1]
  else
    divisor = poly1
    remainder = polynom_division(poly2, divisor)[1]
  end
  [divisor, remainder]
end