Class: Polynomial

Inherits:
Object
  • Object
show all
Includes:
Comparable
Defined in:
lib/polynomial.rb,
lib/polynomial/version.rb,
lib/polynomial/legendre.rb,
lib/polynomial/chebyshev.rb,
lib/polynomial/ultraspherical.rb

Overview

:nodoc:

Direct Known Subclasses

Multivariate

Defined Under Namespace

Modules: Chebyshev, Legendre, Ultraspherical, VERSION

Constant Summary collapse

FromStringDefaults = 
HandyHash[
  :power_symbol => '**',
  :multiplication_symbol => '*',
  :variable_name => 'x',
]
ToSDefaults = 


Zero =



new([0])


Unity =



new([1])




Instance Attribute Summary collapse




Class Method Summary
collapse





Instance Method Summary
collapse






Constructor Details





#initialize(*coefs) ⇒ Polynomial







Creates a new polynomial with provided coefficients, which are interpreted as corresponding to increasing powers of x. Alternatively, a hash of power=>coefficients may be supplied, as well as the polynomial degree plus a block to compute each coefficient from correspoding degree. If a string, optionally followed by a arguments hash, is supplied, from_string is called.


Examples:


Polynomial.new(1, 2).to_s #=> "1 + 2*x"
Polynomial.new(1, Complex(2,3)).to_s #=> "1 + (2+3i)*x"
Polynomial.new(3) {|n| n+1 }.to_s #=> "1 + 2*x + 3*x**2 + 4*x**3"
Polynomial[3, 4, 5].to_s #=> "3 + 4*x + 5x**2"
Polynomial[1 => 2, 3 => 4].to_s #=> "2*x + 4x**3"
Polynomial.new('x^2-1', :power_symbol=>'^').to_s #=> "-1 + x**2"
















40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60




# File 'lib/polynomial.rb', line 40

def initialize(*coefs)
  case coefs[0]
  when Integer
    if block_given?
      coefs = 0.upto(coefs[0]).map {|degree| yield(degree) }
    end
  when Hash
    coefs = self.class.coefs_from_pow_coefs(coefs[0])
  when String
    coefs = self.class.coefs_from_string(coefs[0], coefs[1] || {})
  else
    coefs.flatten!
    if coefs.empty?
      raise ArgumentError, 'at least one coefficient should be supplied'
    elsif !coefs.all? {|c| c.is_a? Numeric }
      raise TypeError, 'non-Numeric coefficient supplied'
    end
  end
  @coefs = Polynomial.remove_trailing_zeroes(coefs)
  @coefs.freeze    
end













Instance Attribute Details






#coefs ⇒ Object (readonly)







Returns the value of attribute coefs.















15
16
17




# File 'lib/polynomial.rb', line 15

def coefs
  @coefs
end













Class Method Details





.from_string(s, params = {}) ⇒ Object







Creates Polynomial from a String in appropriate format. Coefficients must be integers or decimals (interpreted as floats).


Warning: complex coefficients are not currently accepted.


Examples:


Polynomial.from_string("1 - 7*x**2") == Polynomial.new(1,0,-7) #=> true
Polynomial.from_string("3 + 4.1x + 5x^2", :multiplication_symbol=>'', :power_symbol=>'^') == Polynomial.new(3,4.1,5) #=> true
Polynomial.from_string("-3*y", :variable_name=>'y') == Polynomial.new(0,-3) #=> true
Polynomial.from_string('x^2-1', :power_symbol=>'^').to_s #=> -1 + x**2
















78
79
80




# File 'lib/polynomial.rb', line 78

def self.from_string(s, params={})
  Polynomial.new(self.coefs_from_string(s, FromStringDefaults.merge_abbrv(params)))
end













Instance Method Details





#%(other) ⇒ Object







Remainder of division by supplied divisor, which may be another polynomial or a number.















252
253
254




# File 'lib/polynomial.rb', line 252

def %(other)
  divmod(other).last
end












#*(other) ⇒ Object







Multiply by another Polynomial or Numeric object. As the straightforward algorithm is used, multipling two polynomials of degree m and n takes O(m n) operations. It is well-known, though, that the Fast Fourier Transform may be employed to reduce the time complexity to O(K log K), where K = maxn.















157
158
159
160
161
162
163
164
165
166
167
168
169
170




# File 'lib/polynomial.rb', line 157

def *(other)
  case other
  when Numeric
    result_coefs = @coefs.map {|a| a * other}
  else
    result_coefs = [0] * (self.degree + other.degree + 2)
    for m in 0 .. self.degree
      for n in 0 .. other.degree
        result_coefs[m+n] += @coefs[m] * other.coefs[n]
      end
    end
  end
  Polynomial.new(result_coefs)
end












#**(n) ⇒ Object







Raises to non-negative integer power.








Raises:


    

  • 
(ArgumentError)

    • 










258
259
260
261
262
263
264
265




# File 'lib/polynomial.rb', line 258

def **(n)
  raise ArgumentError, "negative argument" if n < 0
  result = Polynomial[1]
  n.times do
    result *= self
  end
  result
end












#+(other) ⇒ Object







Add another Polynomial or Numeric object.















125
126
127
128
129
130
131
132
133
134
135
136
137




# File 'lib/polynomial.rb', line 125

def +(other)
  case other
    when Numeric
      self + Polynomial.new(other)
    else
      small, big = [self, other].sort
      a = big.coefs.dup
      for n in 0 .. small.degree
        a[n] += small.coefs[n]
      end
      Polynomial.new(a)
  end
end












#-(other) ⇒ Object







Subtract another Polynomial or Numeric object.















147
148
149




# File 'lib/polynomial.rb', line 147

def -(other)
  self + (-other)
end












#-@ ⇒ Object







Generates a Polynomial object with negated coefficients.















141
142
143




# File 'lib/polynomial.rb', line 141

def -@
  Polynomial.new(coefs.map {|x| -x})
end












#<=>(other) ⇒ Object







Compares with another Polynomial by degrees then coefficients.















376
377
378
379
380
381
382
383
384
385




# File 'lib/polynomial.rb', line 376

def <=>(other)
  case other
  when Numeric
    [self.degree, @coefs[0]] <=> [0, other]
  when Polynomial
    [self.degree, @coefs] <=> [other.degree, other.coefs]
  else
    raise TypeError, "can't compare #{other.class} to Polynomial"
  end
end












#coerce(other) ⇒ Object










112
113
114
115
116
117
118
119
120
121




# File 'lib/polynomial.rb', line 112

def coerce(other)
  case other
  when Numeric
    [Polynomial.new(other), self]
  when Polynomial
    [other, self]
  else
    raise TypeError, "#{other.class} can't be coerced into Polynomial"
  end
end












#degree ⇒ Object







Degree of the polynomial (i.e., highest not null power of the variable).















84
85
86




# File 'lib/polynomial.rb', line 84

def degree
  @coefs.size-1
end












#derivative ⇒ Object







Computes polynomial’s derivative (which is itself a polynomial).















284
285
286
287
288
289
290
291
292




# File 'lib/polynomial.rb', line 284

def derivative
  if degree > 0
    a = Array.new(@coefs.size-1)
    a.each_index { |n| a[n] = (n+1) * @coefs[n+1] }
  else
    a = [0]
  end
  Polynomial.new(a)
end












#derivatives ⇒ Object







Returns an array with the 1st, 2nd, …, degree derivatives. These are the only possibly non null derivatives, subsequent ones would necesseraly be zero.















102
103
104
105
106
107
108
109
110




# File 'lib/polynomial.rb', line 102

def derivatives
  ds = []
  d = self
  begin
    d = d.derivative
    ds << d
  end until d.zero?
  ds
end












#div(other) ⇒ Object
Also known as:
/








Divides polynomial by a number or another polynomial, which need not be divisible by the former.















244
245
246




# File 'lib/polynomial.rb', line 244

def div(other)
  divmod(other).first
end












#divmod(divisor) ⇒ Object







Divides by divisor, returing quotient and rest. If divisor is a polynomial, uses polynomial long division. Otherwise, performs the division direclty on the coefficients.















213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239




# File 'lib/polynomial.rb', line 213

def divmod(divisor)
  case divisor
  when Numeric
    new_coefs = @coefs.map do |a|
      if divisor.is_a?(Integer)
        qq, rr = a.divmod(divisor)
        if rr.zero? then qq else a / divisor.to_f end
      else
        a / divisor
      end
    end
    q, r = Polynomial.new(new_coefs), 0
  when Polynomial
    a = self; b = divisor; q = 0; r = self
    (a.degree - b.degree + 1).times do
      dd = r.degree - b.degree
      qqa = r.coefs[-1] / (b.coefs[-1].to_f rescue b.coefs[-1]) # rescue for complex numbers
      qq = Polynomial[dd => qqa]
      q += qq
      r -= qq * divisor
      break if r.zero?
    end
  else
    raise ArgumentError, 'divisor should be Numeric or Polynomial'
  end
  [q, r]
end












#dup ⇒ Object










21
22
23




# File 'lib/polynomial.rb', line 21

def dup
  Marshal.load(Marshal.dump(self))
end












#equal_in_delta(other, delta) ⇒ Object







Returns true if the other Polynomial has same degree and close-enough (up to delta absolute difference) coefficients. Returns false otherwise.















391
392
393
394
395
396
397




# File 'lib/polynomial.rb', line 391

def equal_in_delta(other, delta)
  return false unless self.degree == other.degree
  for n in 0 .. degree
    return false unless (@coefs[n] - other.coefs[n]).abs <= delta
  end  
  true
end












#integral ⇒ Object







Computes polynomial’s indefinite integral (which is itself a polynomial).















269
270
271
272
273
274
275
276
277
278
279
280




# File 'lib/polynomial.rb', line 269

def integral
  a = Array.new(@coefs.size+1)
  a[0] = 0
  @coefs.each.with_index do |coef, n|
    if coef.is_a?(Integer) && coef.modulo(n+1).zero?
      a[n+1] = coef / (n + 1)
    else
      a[n+1] = coef / (n + 1.0)
    end
  end
  Polynomial.new(a)
end












#quo(divisor) ⇒ Object







Divides by divisor (using coefficients’ #quo), which may be a number or another polynomial, which need not be divisible by the former. If dividend and divisor have Intenger or Rational coefficients, then the quotient will have Rational coefficients.















205
206
207




# File 'lib/polynomial.rb', line 205

def quo(divisor)
  quomod(divisor).first
end












#quomod(divisor) ⇒ Object







Divides by divisor (using coefficients’ #quo), returning quotient and rest. If dividend and divisor have Intenger or Rational coefficients, then both quotient and rest will have Rational coefficients. If divisor is a polynomial, uses polynomial long division. Otherwise, performs the division direclty on the coefficients.















178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197




# File 'lib/polynomial.rb', line 178

def quomod(divisor)
  case divisor
  when Numeric
    new_coefs = @coefs.map {|a| a.quo(divisor) }
    q, r = Polynomial.new(new_coefs), 0
  when Polynomial
    a = self; b = divisor; q = 0; r = self
    (a.degree - b.degree + 1).times do
      dd = r.degree - b.degree
      qqa = r.coefs[-1].quo(b.coefs[-1])
      qq = Polynomial[dd => qqa]
      q += qq
      r -= qq * divisor
      break if r.zero?
    end
  else
    raise ArgumentError, 'divisor should be Numeric or Polynomial'
  end
  [q, r]
end












#substitute(x) ⇒ Object







Evaluates Polynomial of degree n at point x in O(n) time using Horner’s rule.















90
91
92
93
94
95
96




# File 'lib/polynomial.rb', line 90

def substitute(x)
  total = @coefs.last
  @coefs[0..-2].reverse.each do |a|
    total = total * x + a
  end
  total
end












#to_f ⇒ Object







Returns the only coefficient of a zero-degree polynomial converted to a Float. If degree is positive, an exception is raised.















354




# File 'lib/polynomial.rb', line 354

def to_f; to_num.to_f; end












#to_i ⇒ Object







Returns the only coefficient of a zero-degree polynomial converted to an Integer. If degree is positive, an exception is raised.















359




# File 'lib/polynomial.rb', line 359

def to_i; to_num.to_i; end












#to_num ⇒ Object







Converts a zero-degree polynomial to a number, i.e., returns its only coefficient. If degree is positive, an exception is raised.















343
344
345
346
347
348
349




# File 'lib/polynomial.rb', line 343

def to_num
  if self.degree == 0
    @coefs[0]
  else
    raise ArgumentError, "can't convert Polynomial of positive degree to Numeric"
  end
end












#to_s(params = {}) ⇒ Object







Generate the string corresponding to the polynomial. If :verbose is false (default), omits zero-coefficiented monomials. If :spaced is true (default), monomials are spaced. If :decreasing is false (default), monomials are present from lowest to greatest degree.


Examples:


Polynomial[1,-2,3].to_s #=> "1 - 2*x + 3*x**2"
Polynomial[1,-2,3].to_s(:spaced=>false) #=> "1-2*x+3*x**2"
Polynomial[1,-2,3].to_s(:decreasing=>true) #=> "3*x**2 - 2*x + 1"
Polynomial[1,0,3].to_s(:verbose=>true) #=> "1 + 0*x + 3*x**2"
















314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338




# File 'lib/polynomial.rb', line 314

def to_s(params={})
  params = ToSDefaults.merge_abbrv(params)
  mult = params[:multiplication_symbol]
  pow = params[:power_symbol]
  var = params[:variable_name]
  coefs_index_enumerator = if params[:decreasing]
                             @coefs.each.with_index.reverse_each
                           else
                             @coefs.each.with_index
                           end
  result = ''
  coefs_index_enumerator.each do |a,n|
    next if a.zero? && degree > 0 && !params[:verbose]
    result += '+' unless result.empty?
    coef_str = a.to_s
    coef_str = '(' + coef_str + ')' if coef_str[/[+\/]/]
    result += coef_str unless a == 1 && n > 0
    result += "#{mult}" if a != 1 && n > 0
    result += "#{var}" if n >= 1
    result += "#{pow}#{n}" if n >= 2
  end
  result.gsub!(/\+-/,'-')
  result.gsub!(/([^e\(])(\+|-)(.)/,'\1 \2 \3') if params[:spaced]
  result
end












#unity? ⇒ Boolean







Returns true if and only if the polynomial is unity.








Returns:


    

  • 
(Boolean)

    • 










502
503
504




# File 'lib/polynomial.rb', line 502

def unity?
  self == Unity
end












#zero? ⇒ Boolean







Returns true if and only if the polynomial is null.








Returns:


    

  • 
(Boolean)

    • 










496
497
498




# File 'lib/polynomial.rb', line 496

def zero?
  self == Zero
end