Class: Xirr::Brent

Inherits:
Object
  • Object
show all
Includes:
Base
Defined in:
lib/xirr/brent.rb

Overview

Brent's method: a derivative-free root finder combining inverse quadratic interpolation, the secant method, and bisection. It reuses RtSafe's bracketing, so it is as robust as the default solver but never evaluates the NPV derivative — each iteration is cheaper, though it needs more of them.

In practice it roughly ties RtSafe; it is offered for very large cashflows, where the cheaper per-iteration cost can win. Select it with xirr(method: :brent). Unlike the Newton-based solvers it ignores the initial guess — it works from the bracket.

Instance Attribute Summary

Attributes included from Base

#cf

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Base

#initialize, #periods_from_start, #xnpv, #xnpv_derivative

Class Method Details

.find(flows, tolerance: Xirr.config.eps, iteration_limit: Xirr.config.iteration_limit, precision: Xirr.config.precision) ⇒ Float?

Pure solver over normalized [time, amount] flows.

Parameters:

  • flows (Array<Array(Float, Float)>)

Returns:

  • (Float, nil) 


27
28
29
30
31
32
33
34
35
 
# File 'lib/xirr/brent.rb', line 27

def self.find(flows, tolerance: Xirr.config.eps, iteration_limit: Xirr.config.iteration_limit, precision: Xirr.config.precision)
  rate = zbrent(flows, tolerance.to_f, iteration_limit)
  return nil if rate.nil? || rate.nan? || rate.infinite?

  rounded = rate.round(precision)
  rounded <= -1.0 ? nil : rounded
rescue FloatDomainError, Math::DomainError
  nil
end

.zbrent(flows, tol, iteration_limit) ⇒ Object

Bracket a sign change (reusing RtSafe), then iterate Brent's method within it. Returns the rate, or nil if it can't bracket or converge.



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/xirr/brent.rb', line 39

def self.zbrent(flows, tol, iteration_limit)
  low = RtSafe.safe_low(flows)
  f_low = RtSafe.present_value(flows, low)
  bounds = RtSafe.bracket(flows, low, f_low, 1.0)
  return nil if bounds.nil?

  a, b = bounds
  fa = f_low # a == low
  fb = RtSafe.present_value(flows, b)
  c = a
  fc = fa
  d = e = b - a

  iteration_limit.times do
    # Keep c as the contrapoint — opposite sign to b, so [b, c] brackets.
    if (fb.positive? && fc.positive?) || (fb.negative? && fc.negative?)
      c = a
      fc = fa
      d = e = b - a
    end
    # Ensure b is the better estimate.
    if fc.abs < fb.abs
      a = b
      b = c
      c = a
      fa = fb
      fb = fc
      fc = fa
    end

    tol1 = 2.0 * Float::EPSILON * b.abs + 0.5 * tol
    xm = 0.5 * (c - b)
    return b if xm.abs <= tol1 || fb.zero?

    if e.abs >= tol1 && fa.abs > fb.abs
      s = fb / fa
      if a == c
        # Secant step.
        p = 2.0 * xm * s
        q = 1.0 - s
      else
        # Inverse quadratic interpolation.
        q = fa / fc
        r = fb / fc
        p = s * (2.0 * xm * q * (q - r) - (b - a) * (r - 1.0))
        q = (q - 1.0) * (r - 1.0) * (s - 1.0)
      end
      q = -q if p.positive?
      p = p.abs
      min1 = 3.0 * xm * q - (tol1 * q).abs
      min2 = (e * q).abs
      if 2.0 * p < (min1 < min2 ? min1 : min2)
        e = d
        d = p / q # accept interpolation
      else
        d = e = xm # fall back to bisection
      end
    else
      d = e = xm # bounds decreasing too slowly; bisect
    end

    a = b
    fa = fb
    b += d.abs > tol1 ? d : (xm.positive? ? tol1 : -tol1)
    fb = RtSafe.present_value(flows, b)
  end
  nil
end

Instance Method Details

#xirr(_guess, options) ⇒ Float?

Parameters:

  • guess (Float, nil) —

    ignored; Brent brackets the root itself

  • options (Hash) —

    reads :iteration_limit

Returns:

  • (Float, nil) 


19
20
21
22
 
# File 'lib/xirr/brent.rb', line 19

def xirr(_guess, options)
  limit = (options && options[:iteration_limit]) || Xirr.config.iteration_limit
  Brent.find(flows, iteration_limit: limit)
end