Module: Silicium::Algebra::PolynomRootsReal

Defined in:
lib/algebra.rb

Overview

PolynomRootsReal

Instance Method Summary collapse

Instance Method Details

#binary_root_finder(deg, edge_neg, edge_pos, cf) ⇒ Object

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



209
210
211
212
213
214
215
216
217
218
219
220
221
 
# 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) ⇒ Object

transform array of coefficient to string



368
369
370
371
372
373
 
# 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) ⇒ Object 



375
376
377
 
# 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) ⇒ Object

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



195
196
197
198
199
200
201
202
203
204
 
# 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) ⇒ Object 



434
435
436
437
438
439
440
441
 
# 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) ⇒ Object

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



252
253
254
255
256
257
258
259
260
261
262
 
# 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) ⇒ Object

forming array of differentiated polynoms, starting from source one



344
345
346
347
348
349
350
 
# 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) ⇒ Object

forming left edge for root search



276
277
278
279
280
281
282
 
# 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) ⇒ Object

forming right edge fro root search



285
286
287
288
289
290
291
292
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


180
181
182
 
# File 'lib/algebra.rb', line 180

def free_term?(term)
  term.scan(/[a-z]/).empty?
end

#gauss_seidel(a, b, eps) ⇒ Object

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



389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
 
# 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) ⇒ Object

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



124
125
126
127
128
129
130
131
 
# 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) ⇒ Object 



152
153
154
 
# 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) ⇒ Object 



420
421
422
423
424
425
 
# 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) ⇒ Object 



427
428
429
430
431
432
 
# 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) ⇒ Object

check if we suddenly found root



265
266
267
268
269
270
271
272
273
 
# 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) ⇒ Object 



325
326
327
328
329
330
331
332
 
# 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) ⇒ Object 



334
335
336
337
338
339
340
341
 
# 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) ⇒ Object

intialize cur_cf and cur_deg depend on current term



170
171
172
173
174
175
176
177
178
 
# 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) ⇒ Object

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



185
186
187
188
189
190
191
 
# 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) ⇒ Object 



140
141
142
143
144
 
# 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) ⇒ Object

evaluate real roots of polynom with order = deg



295
296
297
298
299
300
301
302
303
304
305
 
# 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) ⇒ Object 



308
309
310
311
 
# 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) ⇒ Object 



156
157
158
159
160
161
162
163
164
165
166
167
 
# 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) ⇒ Object

rationing polynom



314
315
316
317
318
319
320
321
322
323
 
# 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) ⇒ Object 



353
354
355
356
357
358
359
360
361
362
363
364
365
 
# 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) ⇒ Object 



443
444
445
446
447
448
 
# 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) ⇒ Object 



379
380
381
382
383
384
385
 
# File 'lib/algebra.rb', line 379

def sign(val)
  if val > 0
    '+'
  else
    ''
  end
end

#split_by_neg(pos_tokens) ⇒ Object 



146
147
148
149
150
 
# 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) ⇒ Object 



133
134
135
136
137
 
# 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) ⇒ Object

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



228
229
230
231
232
233
 
# 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) ⇒ Object 



235
236
237
238
239
240
241
242
243
244
245
246
247
248
 
# 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