Class: MoreMath::ContinuedFraction

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

Overview

A continued fraction implementation that supports both simple and generalized continued fractions.

Continued fractions are represented in the form:

a₀ + b₁ / (a₁ + b₂ / (a₂ + b₃ / (a₃ + ...)))

For simple continued fractions, all ‘b` coefficients default to 1, and only `a` coefficients vary.

Examples:

Simple continued fraction for φ (golden ratio)

phi = ContinuedFraction.new
phi.() # => 1.618033988749895

Generalized continued fraction for √2

sqrt_2 = ContinuedFraction.for_a { |n| n == 0 ? 1 : 2 }
sqrt_2.()  # => 1.4142135623730951

Generalized continued fraction for π (finite)

pi = ContinuedFraction.for_a [3, 7, 15, 1, 292, 1, 1, 1, 2]
pi.() # => 3.141592653581078

Continued fraction with variable coefficients

atan = ContinuedFraction.for_a do |n, x|
  n == 0 ? 0 : 2 * n - 1
end.for_b do |n, x|
  n <= 1 ? x : ((n - 1) * x) ** 2
end
atan.(0.5)  # => 0.4636476090008061

Constant Summary collapse

SIMPLE_B =

Default b coefficient generator (returns 1 for all indices)

proc { 1 }

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ ContinuedFraction

Creates a new continued fraction with default coefficients. The defaults for ‘a` and `b` are both set to 1, which approximates the golden ratio when evaluated.

Examples:

Create a new instance

cf = ContinuedFraction.new


40
41
42
43
 
# File 'lib/more_math/continued_fraction.rb', line 40

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

Class Method Details

.for_a(arg = nil) {|index| ... } ⇒ ContinuedFraction

Creates a continued fraction instance and sets its ‘a` coefficients. This is a class method for convenience when building continued fractions.

Examples:

Using an array of values

cf = ContinuedFraction.for_a([1, 2, 3])

Using a block

cf = ContinuedFraction.for_a { |n| n + 1 }

Parameters:

  • arg (Array, nil) (defaults to: nil) —

    An array of coefficients or nil to use a block.

Yields:

  • (index) —

    A block that returns the coefficient for index ‘n`.

Yield Parameters:

  • index (Integer) —

    The index of the coefficient to retrieve.

Returns:

  • (ContinuedFraction) —

    A new continued fraction with specified ‘a` coefficients.



58
59
60
 
# File 'lib/more_math/continued_fraction.rb', line 58

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

.for_b(arg = nil) {|index| ... } ⇒ ContinuedFraction

Creates a continued fraction instance and sets its ‘b` coefficients. This is a class method for convenience when building continued fractions.

Examples:

Using an array of values

cf = ContinuedFraction.for_b([1, 2, 3])

Using a block

cf = ContinuedFraction.for_b { |n| n + 1 }

Parameters:

  • arg (Array, nil) (defaults to: nil) —

    An array of coefficients or nil to use a block.

Yields:

  • (index) —

    A block that returns the coefficient for index ‘n`.

Yield Parameters:

  • index (Integer) —

    The index of the coefficient to retrieve.

Returns:

  • (ContinuedFraction) —

    A new continued fraction with specified ‘b` coefficients.



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

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

.from(number) ⇒ ContinuedFraction

Creates a continued fraction from a Rational number.

Examples:

Create a continued fraction for π

pi_cf = ContinuedFraction.from(Math::PI)

Parameters:

  • number (Numeric) —

    The number to convert into a continued fraction.

Returns:



100
101
102
103
104
105
106
107
108
109
 
# File 'lib/more_math/continued_fraction.rb', line 100

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 (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns the value for a_n or a_n(x).



284
285
286
 
# File 'lib/more_math/continued_fraction.rb', line 284

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

#b(n, x = nil) ⇒ Object (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns the value for b_n or b_n(x).



291
292
293
 
# File 'lib/more_math/continued_fraction.rb', line 291

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

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

Evaluates the continued fraction for a given value ‘x`.

For generalized continued fractions, the coefficients may depend on an external parameter ‘x`. The Wallis method with scaling is used for convergence.

Examples:

Evaluate the golden ratio

phi = ContinuedFraction.new
phi.()  # => 1.618033988749895

Evaluate atan(0.5)

atan = ContinuedFraction.for_a { |n, x| n == 0 ? 0 : 2 * n - 1 }
                     .for_b { |n, x| n <= 1 ? x : ((n - 1) * x) ** 2 }
atan.(0.5)  # => 0.4636476090008061

Parameters:

  • x (Numeric, nil) (defaults to: nil) —

    Optional external parameter for variable coefficients.

  • epsilon (Float) (defaults to: 1E-16) —

    Convergence tolerance (default: 1e-16).

  • max_iterations (Integer) (defaults to: 1 << 31) —

    Maximum number of iterations (default: 2^31).

Returns:

  • (Float) —

    The evaluated result of the continued fraction.



203
204
205
206
207
208
209
210
211
212
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
240
241
242
 
# File 'lib/more_math/continued_fraction.rb', line 203

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 {|convergent| ... } ⇒ Object

Iterates over convergents of this continued fraction (only for simple fractions).

Yields:

  • (convergent) —

    Yields each convergent value.

Yield Parameters:

  • convergent (Float) —

    The next convergent in the sequence.



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

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) {|index| ... } ⇒ ContinuedFraction

Sets the ‘a` coefficients for this continued fraction.

Examples:

Using an array of values

cf = ContinuedFraction.new.for_a([1, 2, 3])

Using a block

cf = ContinuedFraction.new.for_a { |n| n + 1 }

Parameters:

  • arg (Array, nil) (defaults to: nil) —

    An array of coefficients or nil to use a block.

Yields:

  • (index) —

    A block that returns the coefficient for index ‘n`.

Yield Parameters:

  • index (Integer) —

    The index of the coefficient to retrieve.

Returns:



123
124
125
126
 
# File 'lib/more_math/continued_fraction.rb', line 123

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

#for_arg(arg = nil, &block) ⇒ Object (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Helper method to validate and process arguments for ‘for_a` and `for_b`.



82
83
84
85
86
87
88
89
90
 
# File 'lib/more_math/continued_fraction.rb', line 82

def for_arg(arg = nil, &block)
  if arg && !block
    arg.freeze
  elsif block && !arg
    block
  else
    raise ArgumentError, "exactly one argument or one block required"
  end
end

#for_b(arg = nil) {|index| ... } ⇒ ContinuedFraction

Sets the ‘b` coefficients for this continued fraction.

Examples:

Using an array of values

cf = ContinuedFraction.new.for_b([1, 2, 3])

Using a block

cf = ContinuedFraction.new.for_b { |n| n + 1 }

Parameters:

  • arg (Array, nil) (defaults to: nil) —

    An array of coefficients or nil to use a block.

Yields:

  • (index) —

    A block that returns the coefficient for index ‘n`.

Yield Parameters:

  • index (Integer) —

    The index of the coefficient to retrieve.

Returns:



140
141
142
143
 
# File 'lib/more_math/continued_fraction.rb', line 140

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

#inspect ⇒ String

Returns a string representation of the continued fraction.

Returns:

  • (String) —

    A detailed string representation for debugging.



168
169
170
 
# File 'lib/more_math/continued_fraction.rb', line 168

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

#reciprocal ⇒ ContinuedFraction

Returns the reciprocal of this continued fraction.

Returns:



247
248
249
250
251
252
253
 
# File 'lib/more_math/continued_fraction.rb', line 247

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

Checks if this is a simple continued fraction (all ‘b` coefficients are 1).

Returns:

  • (Boolean) —

    True if all ‘b` coefficients are 1.



148
149
150
 
# File 'lib/more_math/continued_fraction.rb', line 148

def simple?
  @b == SIMPLE_B
end

#to_proc ⇒ Proc

Converts this continued fraction into a Proc that can be called directly.

Returns:

  • (Proc) —

    A proc that accepts the same arguments as ‘call`.



264
265
266
 
# File 'lib/more_math/continued_fraction.rb', line 264

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

#to_s(length: 10) ⇒ String

Returns a string representation of the continued fraction.

Parameters:

  • length (Integer) (defaults to: 10) —

    The number of terms to display for simple fractions.

Returns:

  • (String) —

    A formatted string representation.



156
157
158
159
160
161
162
163
 
# File 'lib/more_math/continued_fraction.rb', line 156

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

#value(v, n, x = nil) ⇒ Object (private)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Helper method for retrieving coefficient values, supporting both indexed access and block evaluation.



273
274
275
276
277
278
279
 
# File 'lib/more_math/continued_fraction.rb', line 273

def value(v, n, x = nil)
  result = if x
    v[n, x]
  else
    v[n]
  end and result.to_f
end