module Silicium::Algebra::PolynomRootsReal
PolynomRootsReal
Public Instance Methods
+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
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
# 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,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
# 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)+ 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
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
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
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
# File lib/algebra.rb, line 180 def free_term?(term) term.scan(/[a-z]/).empty? end
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)+ 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
# File lib/algebra.rb, line 152 def get_coef_inner(cur_deg, deg) deg.zero? ? cur_deg : deg end
# 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
# 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
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
# 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
# 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
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)+ 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
# 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
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
# File lib/algebra.rb, line 308 def polynom_real_roots_by_str(deg, str) cf = get_coef(str) polynom_real_roots(deg, cf) end
# 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
# 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
# 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
# File lib/algebra.rb, line 443 def round_helper(n,x) (0...n).each do |i| x[i] = x[i].round end x end
# File lib/algebra.rb, line 379 def sign(val) if val > 0 '+' else '' end end
# File lib/algebra.rb, line 146 def split_by_neg(pos_tokens) res = [] pos_tokens.each { |token| res.concat(keep_split(token, '-')) } res end
# 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
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
# 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