Class: MoreMath::ContinuedFraction

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/more_math/continued_fraction.rb

Overview

This class implements a continued fraction of the form:

b_1

a_0 + ————————-

                      b_2
a_1 + --------------------
                      b_3
     a_2 + ---------------
                      b_4
          a_3 + ----------
                      b_5
               a_4 + -----
                      ...

Constant Summary collapse

SIMPLE_B = 
proc { 1 }

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ ContinuedFraction

Creates a continued fraction instance. With the defaults for_a { 1 } and for_b { 1 } it approximates the golden ration phi if evaluated.



21
22
23
24
 
# File 'lib/more_math/continued_fraction.rb', line 21

def initialize
  @a = proc { 1 }
  @b = SIMPLE_B
end

Class Method Details

.for_a(arg = nil, &block) ⇒ Object

Creates a ContinuedFraction instances and passes its arguments to a call to for_a.



28
29
30
 
# File 'lib/more_math/continued_fraction.rb', line 28

def self.for_a(arg = nil, &block)
  new.for_a(arg, &block)
end

.for_b(arg = nil, &block) ⇒ Object

Creates a ContinuedFraction instances and passes its arguments to a call to for_b.



34
35
36
 
# File 'lib/more_math/continued_fraction.rb', line 34

def self.for_b(arg = nil, &block)
  new.for_b(arg, &block)
end

.from(number) ⇒ Object 



49
50
51
52
53
54
55
56
57
58
 
# File 'lib/more_math/continued_fraction.rb', line 49

def self.from(number)
  number = number.to_r
  n, d = number.numerator, number.denominator
  as = []
  while d > 0
    n, (a, d) = d, n.divmod(d)
    as << a
  end
  for_a(as)
end

Instance Method Details

#a(n, x = nil) ⇒ Object

Returns the value for a_n or a_n(x).



114
115
116
 
# File 'lib/more_math/continued_fraction.rb', line 114

def a(n, x = nil)
  value(@a, n, x)
end

#b(n, x = nil) ⇒ Object

Returns the value for b_n or b_n(x).



119
120
121
 
# File 'lib/more_math/continued_fraction.rb', line 119

def b(n, x = nil)
  value(@b, n, x)
end

#call(x = nil, epsilon: 1E-16, max_iterations: 1 << 31) ⇒ Object Also known as: [], to_f

Evaluates the continued fraction for the value x (if any) with the accuracy epsilon and max_iterations as the maximum number of iterations using the Wallis-method with scaling.



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/more_math/continued_fraction.rb', line 126

def call(x = nil, epsilon: 1E-16, max_iterations: 1 << 31)
  c_0, c_1 = 1.0, a(0, x)
  c_1 == nil and return 0 / 0.0
  d_0, d_1 = 0.0, 1.0
  result = c_1 / d_1
  n = 0
  error = 1 / 0.0
  $DEBUG and warn "n=%u, a=%f, b=nil, c=%f, d=%f result=%f, error=nil" %
    [ n, c_1, c_1, d_1, result ]
  while n < max_iterations and error > epsilon
    n += 1
    a_n, b_n = a(n, x), b(n, x)
    a_n and b_n or break
    c_2 = a_n * c_1 + b_n * c_0
    d_2 = a_n * d_1 + b_n * d_0
    if c_2.infinite? or d_2.infinite?
      if a_n != 0
        c_2 = c_1 + (b_n / a_n * c_0)
        d_2 = d_1 + (b_n / a_n * d_0)
      elsif b_n != 0
        c_2 = (a_n / b_n * c_1) + c_0
        d_2 = (a_n / b_n * d_1) + d_0
      else
        raise Errno::ERANGE
      end
    end
    r = c_2 / d_2
    error = (r / result - 1).abs

    result = r

    $DEBUG and warn "n=%u, a=%f, b=%f, c=%f, d=%f, result=%f, error=%.16f" %
      [ n, a_n, b_n, c_1, d_1, result, error ]

    c_0, c_1 = c_1, c_2
    d_0, d_1 = d_1, d_2
  end
  n >= max_iterations and raise Errno::ERANGE
  result
end

#each(&block) ⇒ Object 



89
90
91
92
93
 
# File 'lib/more_math/continued_fraction.rb', line 89

def each(&block)
  if simple?
    (0..Float::INFINITY).lazy.map { |i| @a[i] }.take_while { |x| x }.each(&block)
  end
end

#for_a(arg = nil, &block) ⇒ Object

This method either takes a block or an argument arg. The argument arg has to respond to an integer index n >= 0 and return the value a_n. The block has to return the value for a_n when n is passed as the first argument to the block. If a_n is dependent on an x value (see the call method) the x will be the second argument of the block.



65
66
67
68
 
# File 'lib/more_math/continued_fraction.rb', line 65

def for_a(arg = nil, &block)
  @a = for_arg(arg, &block)
  self
end

#for_b(arg = nil, &block) ⇒ Object

This method either takes a block or an argument arg. The argument arg has to respond to an integer index n >= 1 and return the value b_n. The block has to return the value for b_n when n is passed as the first argument to the block. If b_n is dependent on an x value (see the call method) the x will be the second argument of the block.



75
76
77
78
 
# File 'lib/more_math/continued_fraction.rb', line 75

def for_b(arg = nil, &block)
  @b = for_arg(arg, &block)
  self
end

#inspect ⇒ Object 



84
85
86
 
# File 'lib/more_math/continued_fraction.rb', line 84

def inspect
  "#<#{self.class} #{to_s}>"
end

#reciprocal ⇒ Object 



167
168
169
170
171
172
173
 
# File 'lib/more_math/continued_fraction.rb', line 167

def reciprocal
  if @a[0] > 0
    dup.for_a { |i| i == 0 ? 0 : @a[i - 1] }
  else
    dup.for_a { |i| @a[i + 1] }
  end
end

#simple? ⇒ Boolean

Returns:

  • (Boolean) 


80
81
82
 
# File 'lib/more_math/continued_fraction.rb', line 80

def simple?
  @b == SIMPLE_B
end

#to_proc ⇒ Object

Returns this continued fraction as a Proc object which takes the same arguments like its call method does.



181
182
183
 
# File 'lib/more_math/continued_fraction.rb', line 181

def to_proc
  proc { |*a| call(*a) }
end

#to_s(length: 10) ⇒ Object 



95
96
97
98
99
100
101
102
 
# File 'lib/more_math/continued_fraction.rb', line 95

def to_s(length: 10)
  if simple?
    convergents = take(length)
    "[#{convergents[0]}; #{convergents[1..-1] * ', '}#{",…" if convergents.size >= length}]"
  else
    "CF(a=#@a, b=#@b)"
  end
end