module Silicium::Algebra::PolynomRootsReal

PolynomRootsReal

Public Instance Methods

binary_root_finder(deg, edge_neg, edge_pos, cf) click to toggle source

+binary_root_finder(deg,edge_neg,edge_pos,cf)+ finds result of polynom using binary search edge_neg and edge_pos define the interval used for binary search

# File lib/algebra.rb, line 209
def binary_root_finder(deg, edge_neg, edge_pos, cf)
  loop do
    x = 0.5 * (edge_neg + edge_pos)
    return x if [edge_pos, edge_neg].include? x

    if eval_by_cf(deg, x, cf).positive?
      edge_pos = x
    else
      edge_neg = x
    end
  end
  [edge_pos, edge_neg]
end
coef_to_str(coef) click to toggle source

transform array of coefficient to string

# File lib/algebra.rb, line 368
def coef_to_str(coef)
  n = coef.length - 1
  s = ''
  (0..n).each { |i| s += coef_to_str_inner(coef, i, s) unless coef[i].zero? }
  s
end
coef_to_str_inner(coef, i, s) click to toggle source
# File lib/algebra.rb, line 375
def coef_to_str_inner(coef, i, s)
  i.zero? ? coef[i].to_s : "#{sign(coef[i])}#{coef[i]}*x**#{i}"
end
eval_by_cf(deg, val, kf) click to toggle source

+eval_by_cf(deg,val,cf)+ finds the result of polynom defined by array of coefficients

# File lib/algebra.rb, line 195
def eval_by_cf(deg, val, kf)
  s = kf[deg]
  i = deg - 1
  loop do
    s = s * val + kf[i]
    i -= 1
    break if i < 0
  end
  s
end
extra_helper(n,x_new,x) click to toggle source
# File lib/algebra.rb, line 434
def extra_helper(n,x_new,x)
  (0...n).each do |i|

    @s3 += x_new[i] - x[i]
    @s3 = @s3 ** 2
  end
  @s3
end
find_major(level, cf_dif) click to toggle source

+find_major(level,cf_dif)+ finds value, which we will use as infinity

# File lib/algebra.rb, line 252
def find_major(level, cf_dif)
  major = 0.0
  i = 0
  loop do
    s = cf_dif[i]
    major = s if s > major
    i += 1
    break if i == level
  end
  major + 1.0
end
form_coef_diff(deg, coef_diff, cur_root_count, root_dif) click to toggle source

forming array of differentiated polynoms, starting from source one

# File lib/algebra.rb, line 344
def form_coef_diff(deg, coef_diff, cur_root_count, root_dif)
  init_coef_diff(coef_diff)
  real_differentiration(deg, coef_diff)
  cur_root_count[1] = 1
  init_root_diff(root_dif)
  root_dif[1][0] = -coef_diff[1][0] / coef_diff[1][1]
end
form_left(args_pack) click to toggle source

forming left edge for root search

# File lib/algebra.rb, line 276
def form_left(args_pack)
  i, major, level, root_dif, kf_dif = args_pack
  edge_left = i.zero? ? -major : root_dif[level - 1][i - 1]
  left_val = eval_by_cf(level, edge_left, kf_dif[level])
  sign_left = left_val.positive? ? 1 : -1
  [edge_left, left_val, sign_left]
end
form_right(args_pack) click to toggle source

forming right edge fro root search

# File lib/algebra.rb, line 285
def form_right(args_pack)
  i, major, level, root_dif, kf_dif, cur_root_count = args_pack
  edge_right = i == cur_root_count[level] ? major : root_dif[level - 1][i - 1]

  right_val = eval_by_cf(level, edge_right, kf_dif[level])
  sigh_right = right_val.positive? ? 1 : -1
  [edge_right, right_val, sigh_right]
end
free_term?(term) click to toggle source
# File lib/algebra.rb, line 180
def free_term?(term)
  term.scan(/[a-z]/).empty?
end
gauss_seidel(a,b,eps) click to toggle source

Gauss–Seidel method is an iterative method used to solve a system of linear equations

# File lib/algebra.rb, line 389
def gauss_seidel(a,b,eps)
  n = a.length
  x = Array.new(n,0)

  @s1 = 0.0
  @s2 = 0.0
  @s3 = 0.0

  converge = false
  until converge

    x_new = x
    (0...n).each do |i|
      helper_helper_1(i,a,x_new)
      helper_helper_2(i,n,a,x)

      x_new[i] = (b[i] - @s1 - @s2) / a[i][i]
    end

    extra_helper(n,x_new,x)

    converge = Math::sqrt(@s3) <= eps ? true : false
    x = x_new

  end
  round_helper(n,x)

  x
end
get_coef(str) click to toggle source

+get_coef(str)+ transforms polynom into array of coefficients arr = a0 * x^0 ; arr = a1 * x^1 ; … arr = an * x^(n-1)

get_coef('')    # =>
# File lib/algebra.rb, line 124
def get_coef(str)
  tokens = split_by_op(str)
  cf = Array.new(0.0)
  deg = 0
  tokens.each { |term| deg = process_term(term, cf, deg) }
  insert_zeroes(cf, deg) unless deg.zero?
  cf.reverse
end
get_coef_inner(cur_deg, deg) click to toggle source
# File lib/algebra.rb, line 152
def get_coef_inner(cur_deg, deg)
  deg.zero? ? cur_deg : deg
end
helper_helper_1(i,a,x_new) click to toggle source
# File lib/algebra.rb, line 420
def helper_helper_1(i,a,x_new)

  (0..i).each do |j|
    @s1 += a[i][j] * x_new[j]
  end
end
helper_helper_2(i,n,a,x) click to toggle source
# File lib/algebra.rb, line 427
def helper_helper_2(i,n,a,x)
  (i+1...n).each do |j|
    @s2 += a[i][j] * x[j]
  end

end
hit_root(arr_pack) click to toggle source

check if we suddenly found root

# File lib/algebra.rb, line 265
def hit_root(arr_pack)
  level, edge, val, root_dif, cur_roots_count = arr_pack
  if val == 0
    root_dif[level][cur_roots_count[level]] = edge
    cur_roots_count[level] += 1
    return true
  end
  false
end
init_coef_diff(coef_diff) click to toggle source
# File lib/algebra.rb, line 325
def init_coef_diff(coef_diff)
  j = coef_diff.length - 2
  loop do
    coef_diff[j] = []
    j -= 1
    break if j < 0
  end
end
init_root_diff(cur_root_count) click to toggle source
# File lib/algebra.rb, line 334
def init_root_diff(cur_root_count)
  j = cur_root_count.length - 1
  loop do
    cur_root_count[j] = []
    j -= 1
    break if j < 0
  end
end
initialize_cf_deg(term, par_cf, par_deg) click to toggle source

intialize cur_cf and cur_deg depend on current term

# File lib/algebra.rb, line 170
def initialize_cf_deg(term, par_cf, par_deg)
  return [term.to_f, 0] if free_term? term
  cf = if par_cf.empty?
         term.include?('-') ? -1 : 1
       else
         par_cf.to_f
       end
  [cf, par_deg.nil? ? 1 : par_deg.delete('^').to_i]
end
insert_zeroes(arr, count) click to toggle source

+insert_zeroes(arr,count)+ fills empty spaces in the coefficient array

# File lib/algebra.rb, line 185
def insert_zeroes(arr, count)
  loop do
    arr << 0.0
    count -= 1
    break if count == 0
  end
end
keep_split(str,delim) click to toggle source
# File lib/algebra.rb, line 140
def keep_split(str,delim)
  res = str.split(delim)
  return [] if res.length == 0
  [res.first] + res[1,res.length - 1].map {|x| x = delim + x }
end
polynom_real_roots(deg, coef) click to toggle source

evaluate real roots of polynom with order = deg

# File lib/algebra.rb, line 295
def polynom_real_roots(deg, coef)
  coef_diff = Array.new(deg + 1)
  root_diff = Array.new(deg + 1)
  cur_root_count = Array.new(deg + 1)
  coef_diff[deg] = rationing_polynom(deg, coef)
  form_coef_diff(deg, coef_diff, cur_root_count, root_diff)
  (2..deg).each { |i| step_up(i, coef_diff, root_diff, cur_root_count) }
  roots_arr = []
  root_diff[deg].each { |root| roots_arr << root }
  roots_arr
end
polynom_real_roots_by_str(deg, str) click to toggle source
# File lib/algebra.rb, line 308
def polynom_real_roots_by_str(deg, str)
  cf = get_coef(str)
  polynom_real_roots(deg, cf)
end
process_term(term, cf, deg) click to toggle source
# File lib/algebra.rb, line 156
def process_term(term, cf, deg)
  term[/(-?\d*[.|,]?\d*)\*?[a-z](\^\d*)?/]
  par_cf = Regexp.last_match(1)
  par_deg = Regexp.last_match(2)
  cur_cf, cur_deg = initialize_cf_deg(term, par_cf, par_deg)
  # initialize deg for the first time
  deg = cur_deg if deg.zero?
  # add 0 coefficient to missing degrees
  insert_zeroes(cf, deg - cur_deg - 1) if deg - cur_deg > 1
  cf << cur_cf
  deg = cur_deg
end
rationing_polynom(deg, coef) click to toggle source

rationing polynom

# File lib/algebra.rb, line 314
def rationing_polynom(deg, coef)
  res = []
  i = 0
  loop do
    res[i] = coef[i] / coef[deg].to_f
    i += 1
    break if i > deg
  end
  res
end
real_differentiration(deg, coef_diff) click to toggle source
# File lib/algebra.rb, line 353
def real_differentiration(deg, coef_diff)
  loop do
    j = deg
    loop do
      coef_diff[deg - 1][j - 1] = coef_diff[deg][j] * j

      j -= 1
      break if j.zero?
    end
    deg -= 1
    break if deg < 2
  end
end
round_helper(n,x) click to toggle source
# File lib/algebra.rb, line 443
def round_helper(n,x)
  (0...n).each do |i|
    x[i] = x[i].round
  end
  x
end
sign(val) click to toggle source
# File lib/algebra.rb, line 379
def sign(val)
  if val > 0
    '+'
  else
    ''
  end
end
split_by_neg(pos_tokens) click to toggle source
# File lib/algebra.rb, line 146
def split_by_neg(pos_tokens)
  res = []
  pos_tokens.each { |token| res.concat(keep_split(token, '-')) }
  res
end
split_by_op(str) click to toggle source
# File lib/algebra.rb, line 133
def split_by_op(str)
  space_clear_str = str.gsub(/\s/,'')
  pos_tokens = space_clear_str.split('+')
  split_by_neg(pos_tokens)
end
step_up(level, cf_dif, root_dif, cur_root_count) click to toggle source

this method finds roots for each differentiated polynom and use previous ones to find next one roots located in interval, which has different sign in edges if we've found such interval then we begin binary_search on that interval to find root major is value, which we use to modulate +-infinite

# File lib/algebra.rb, line 228
def step_up(level, cf_dif, root_dif, cur_root_count)
  major = find_major(level, cf_dif[level])
  cur_root_count[level] = 0
  # main loop
  (0..cur_root_count[level - 1]).each { |i| step_up_loop([i, major, level, root_dif, cf_dif, cur_root_count]) }
end
step_up_loop(arr_pack) click to toggle source
# File lib/algebra.rb, line 235
def step_up_loop(arr_pack)
  i, major, level, root_dif, cf_dif, cur_root_count = arr_pack
  edge_left, left_val, sign_left = form_left([i, major, level, root_dif, cf_dif])

  return if hit_root([level, edge_left, left_val, root_dif, cur_root_count])

  edge_right, right_val, sigh_right = form_right([i, major, level, root_dif, cf_dif, cur_root_count])

  return if hit_root([level, edge_right, right_val, root_dif, cur_root_count])

  return if sigh_right == sign_left
  edge_neg, edge_pos = sign_left.negative? ? [edge_left, edge_right] : [edge_right, edge_left]
  root_dif[level][cur_root_count[level]] = binary_root_finder(level, edge_neg, edge_pos, cf_dif[level])
end