Module: Polynomial::Legendre

Defined in:
lib/polynomial/legendre.rb

Overview

Generate Legendre polynomials. For the mathematics, see Wikipedia entry.

Class Method Summary collapse

Class Method Details

.cached_legendre(n) ⇒ Object Also known as: legendre

Generate the n-th Legendre polynomial using a cached interactive implementation of the recurrence relation. Caching reduces amortized (average after many calls) time consumption to O(1) in the hypothetical case of infinite calls with uniform distribution in a bounded range.

Warning: due to caching, memory usage is proportional to the square of the greatest degree computed. Use the uncached_first_kind method if no caching is wanted.



23
24
25
26
27
28
29
30
 
# File 'lib/polynomial/legendre.rb', line 23

def self.cached_legendre(n)
  n >= 0 or raise RangeError, 'degree should be non-negative'

  for m in @cache.size-1 ... n
    @cache[m+1] = (Polynomial.new(0,2*m+1)*@cache[m] - m*@cache[m-1]).quo(m+1)
  end
  @cache[n]
end

.uncached_legendre(n) ⇒ Object

Generate the n-th Legendre polynomial, but uncached. It saves memory but the amortized time consumption is higher, namely O(n^2).



37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/polynomial/legendre.rb', line 37

def self.uncached_legendre(n)
  n >= 0 or raise RangeError, 'degree should be non-negative'

  case n
  when 0 then @cache[0]
  when 1 then @cache[1]
  else
    prev2 = @cache[0]
    prev1 = @cache[1]
    curr = nil # scope
    for m in 1 ... n
      curr = (Polynomial.new(0,2*m+1)*prev1 - m*prev2).quo(m+1)
      prev1, prev2 = curr, prev1
    end
    curr
  end
end