libs/math/doc/html/math_toolkit/internals/recurrence.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Tools For 3-Term Recurrence Relations</title>
   5 <link rel="stylesheet" href="../../math.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
   7 <link rel="home" href="../../index.html" title="Math Toolkit 2.11.0">
   8 <link rel="up" href="../internals.html" title="Internal tools">
   9 <link rel="prev" href="cf.html" title="Continued Fraction Evaluation">
  10 <link rel="next" href="tuples.html" title="Tuples">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="cf.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="tuples.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="math_toolkit.internals.recurrence"></a><a class="link" href="recurrence.html" title="Tools For 3-Term Recurrence Relations">Tools For 3-Term Recurrence
  28       Relations</a>
  29 </h3></div></div></div>
  30 <h5>
  31 <a name="math_toolkit.internals.recurrence.h0"></a>
  32         <span class="phrase"><a name="math_toolkit.internals.recurrence.synopsis"></a></span><a class="link" href="recurrence.html#math_toolkit.internals.recurrence.synopsis">Synopsis</a>
  33       </h5>
  34 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">tools</span><span class="special">/</span><span class="identifier">recurrence</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  35 </pre>
  36 <pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">tools</span><span class="special">{</span>
  37
  38 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
  39 <span class="identifier">T</span> <span class="identifier">function_ratio_from_backwards_recurrence</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">factor</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>
  40
  41 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
  42 <span class="identifier">T</span> <span class="identifier">function_ratio_from_forwards_recurrence</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">factor</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>
  43
  44 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">NextCoefs</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
  45 <span class="identifier">T</span> <span class="identifier">apply_recurrence_relation_forward</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">NextCoefs</span><span class="special">&amp;</span> <span class="identifier">get_coefs</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">number_of_steps</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">second</span><span class="special">,</span> <span class="keyword">int</span><span class="special">*</span> <span class="identifier">log_scaling</span> <span class="special">=</span> <span class="number">0</span><span class="special">,</span> <span class="identifier">T</span><span class="special">*</span> <span class="identifier">previous</span> <span class="special">=</span> <span class="number">0</span><span class="special">);</span>
  46
  47 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">NextCoefs</span><span class="special">&gt;</span>
  48 <span class="identifier">T</span> <span class="identifier">apply_recurrence_relation_backward</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">NextCoefs</span><span class="special">&amp;</span> <span class="identifier">get_coefs</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">number_of_steps</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">second</span><span class="special">,</span> <span class="keyword">int</span><span class="special">*</span> <span class="identifier">log_scaling</span> <span class="special">=</span> <span class="number">0</span><span class="special">,</span> <span class="identifier">T</span><span class="special">*</span> <span class="identifier">previous</span> <span class="special">=</span> <span class="number">0</span><span class="special">);</span>
  49
  50 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">&gt;</span>
  51 <span class="keyword">struct</span> <span class="identifier">forward_recurrence_iterator</span><span class="special">;</span>
  52
  53 <span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">&gt;</span>
  54 <span class="keyword">struct</span> <span class="identifier">backward_recurrence_iterator</span><span class="special">;</span>
  55
  56 <span class="special">}}}</span> <span class="comment">// namespaces</span>
  57 </pre>
  58 <h5>
  59 <a name="math_toolkit.internals.recurrence.h1"></a>
  60         <span class="phrase"><a name="math_toolkit.internals.recurrence.description"></a></span><a class="link" href="recurrence.html#math_toolkit.internals.recurrence.description">Description</a>
  61       </h5>
  62 <p>
  63         All of the tools in this header require a description of the recurrence relation:
  64         this takes the form of a functor that returns a tuple containing the 3 coefficients,
  65         specifically, given a recurrence relation:
  66       </p>
  67 <div class="blockquote"><blockquote class="blockquote"><p>
  68           <span class="inlinemediaobject"><img src="../../../equations/three_term_recurrence.svg"></span>
  69
  70         </p></blockquote></div>
  71 <p>
  72         And a functor <code class="computeroutput"><span class="identifier">F</span></code> then the
  73         expression:
  74       </p>
  75 <div class="blockquote"><blockquote class="blockquote"><p>
  76           <span class="serif_italic">F(n);</span>
  77         </p></blockquote></div>
  78 <p>
  79         Returns a tuple containing <span class="serif_italic">{ a<sub>n</sub>, b<sub>n</sub>, c<sub>n</sub> }</span>.
  80       </p>
  81 <p>
  82         For example, the recurrence relation for the Bessel J and Y functions when
  83         written in this form is:
  84       </p>
  85 <p>
  86         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/three_term_recurrence_bessel_jy.svg" width="250" height="38"></object></span>
  87       </p>
  88 <p>
  89         Therefore, given local variables <span class="emphasis"><em>x</em></span> and <span class="emphasis"><em>v</em></span>
  90         of type <code class="computeroutput"><span class="keyword">double</span></code> the recurrence
  91         relation for Bessel J and Y can be encoded in a lambda expression like this:
  92       </p>
  93 <pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">recurrence_functor_jy</span> <span class="special">=</span> <span class="special">[&amp;](</span><span class="keyword">int</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_tuple</span><span class="special">(</span><span class="number">1.0</span><span class="special">,</span> <span class="special">-</span><span class="number">2</span> <span class="special">*</span> <span class="special">(</span><span class="identifier">v</span> <span class="special">+</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">/</span> <span class="identifier">x</span><span class="special">,</span> <span class="number">1.0</span><span class="special">);</span> <span class="special">};</span>
  94 </pre>
  95 <p>
  96         Similarly, the Bessel I and K recurrence relation differs just by the sign
  97         of the final term:
  98       </p>
  99 <p>
 100         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/three_term_recurrence_bessel_ik.svg" width="244" height="38"></object></span>
 101       </p>
 102 <p>
 103         And this could be encoded as:
 104       </p>
 105 <pre class="programlisting"><span class="keyword">auto</span> <span class="identifier">recurrence_functor_ik</span> <span class="special">=</span> <span class="special">[&amp;](</span><span class="keyword">int</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">make_tuple</span><span class="special">(</span><span class="number">1.0</span><span class="special">,</span> <span class="special">-</span><span class="number">2</span> <span class="special">*</span> <span class="special">(</span><span class="identifier">v</span> <span class="special">+</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">/</span> <span class="identifier">x</span><span class="special">,</span> <span class="special">-</span><span class="number">1.0</span><span class="special">);</span> <span class="special">};</span>
 106 </pre>
 107 <p>
 108         The tools are then as follows:
 109       </p>
 110 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 111 <span class="identifier">T</span> <span class="identifier">function_ratio_from_backwards_recurrence</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">factor</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>
 112 </pre>
 113 <p>
 114         Given a functor <code class="computeroutput"><span class="identifier">r</span></code> which encodes
 115         the recurrence relation for function <code class="computeroutput"><span class="identifier">F</span></code>
 116         at some location <span class="emphasis"><em>n</em></span>, then returns the ratio:
 117       </p>
 118 <p>
 119         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/three_term_recurrence_backwards_ratio.svg" width="63" height="20"></object></span>
 120       </p>
 121 <p>
 122         This calculation is stable only if recurrence is stable in the backwards
 123         direction. Further the ratio calculated is for the dominant solution (in
 124         the backwards direction) of the recurrence relation, if there are multiple
 125         solutions, then there is no guarantee that this will find the one you want
 126         or expect.
 127       </p>
 128 <p>
 129         Argument <span class="emphasis"><em>factor</em></span> is the tolerance required for convergence
 130         of the continued fraction associated with the recurrence relation, and should
 131         be no smaller than machine epsilon. Argument <span class="emphasis"><em>max_iter</em></span>
 132         sets the maximum number of permitted iterations in the associated continued
 133         fraction.
 134       </p>
 135 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 136 <span class="identifier">T</span> <span class="identifier">function_ratio_from_forwards_recurrence</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">T</span><span class="special">&amp;</span> <span class="identifier">factor</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span><span class="special">&amp;</span> <span class="identifier">max_iter</span><span class="special">);</span>
 137 </pre>
 138 <p>
 139         Given a functor <code class="computeroutput"><span class="identifier">r</span></code> which encodes
 140         the recurrence relation for function F at some location <span class="emphasis"><em>n</em></span>,
 141         then returns the ratio:
 142       </p>
 143 <p>
 144         <span class="inlinemediaobject"><object type="image/svg+xml" data="../../../equations/three_term_recurrence_forwards_ratio.svg" width="63" height="20"></object></span>
 145       </p>
 146 <p>
 147         This calculation is stable only if recurrence is stable in the forwards direction.
 148         Further the ratio calculated is for the dominant solution (in the forwards
 149         direction) of the recurrence relation, if there are multiple solutions, then
 150         there is no guarantee that this will find the one you want or expect.
 151       </p>
 152 <p>
 153         Argument <span class="emphasis"><em>factor</em></span> is the tolerance required for convergence
 154         of the continued fraction associated with the recurrence relation, and should
 155         be no smaller than machine epsilon. Argument <span class="emphasis"><em>max_iter</em></span>
 156         sets the maximum number of permitted iterations in the associated continued
 157         fraction.
 158       </p>
 159 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">NextCoefs</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 160 <span class="identifier">T</span> <span class="identifier">apply_recurrence_relation_forward</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">NextCoefs</span><span class="special">&amp;</span> <span class="identifier">get_coefs</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">number_of_steps</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">second</span><span class="special">,</span> <span class="keyword">int</span><span class="special">*</span> <span class="identifier">log_scaling</span> <span class="special">=</span> <span class="number">0</span><span class="special">,</span> <span class="identifier">T</span><span class="special">*</span> <span class="identifier">previous</span> <span class="special">=</span> <span class="number">0</span><span class="special">);</span>
 161 </pre>
 162 <p>
 163         Applies a recurrence relation in a stable forward direction, starting with
 164         the values F<sub>n-1</sub> and F<sub>n</sub>.
 165       </p>
 166 <div class="variablelist">
 167 <p class="title"><b></b></p>
 168 <dl class="variablelist">
 169 <dt><span class="term">get_coefs</span></dt>
 170 <dd><p>
 171               Functor that returns the corefficients of the recurrence relation.
 172               The coefficients should be centered on position <span class="emphasis"><em>second</em></span>.
 173             </p></dd>
 174 <dt><span class="term">number_of_steps</span></dt>
 175 <dd><p>
 176               The number of steps to apply the recurrence relation onwards from
 177               <span class="emphasis"><em>second</em></span>.
 178             </p></dd>
 179 <dt><span class="term">first</span></dt>
 180 <dd><p>
 181               The value of F<sub>n-1</sub>
 182             </p></dd>
 183 <dt><span class="term">second</span></dt>
 184 <dd><p>
 185               The value of F<sub>n</sub>
 186             </p></dd>
 187 <dt><span class="term">log_scaling</span></dt>
 188 <dd><p>
 189               When provided, the recurrence relations may be rescaled internally
 190               to avoid over/underflow issues. The result should be multiplied by
 191               <code class="computeroutput"><span class="identifier">exp</span><span class="special">(*</span><span class="identifier">log_scaling</span><span class="special">)</span></code>
 192               to get the true value of the result.
 193             </p></dd>
 194 <dt><span class="term">previous</span></dt>
 195 <dd><p>
 196               When provided, is set to the value of F<sub>n + number_of_steps - 1</sub>
 197             </p></dd>
 198 </dl>
 199 </div>
 200 <p>
 201         Returns F<sub>n + number_of_steps</sub>.
 202       </p>
 203 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">NextCoefs</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
 204 <span class="identifier">T</span> <span class="identifier">apply_recurrence_relation_backward</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">NextCoefs</span><span class="special">&amp;</span> <span class="identifier">get_coefs</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">number_of_steps</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">T</span> <span class="identifier">second</span><span class="special">,</span> <span class="keyword">int</span><span class="special">*</span> <span class="identifier">log_scaling</span> <span class="special">=</span> <span class="number">0</span><span class="special">,</span> <span class="identifier">T</span><span class="special">*</span> <span class="identifier">previous</span> <span class="special">=</span> <span class="number">0</span><span class="special">);</span>
 205 </pre>
 206 <p>
 207         Applies a recurrence relation in a stable backward direction, starting with
 208         the values F<sub>n+1</sub> and F<sub>n</sub>.
 209       </p>
 210 <div class="variablelist">
 211 <p class="title"><b></b></p>
 212 <dl class="variablelist">
 213 <dt><span class="term">get_coefs</span></dt>
 214 <dd><p>
 215               Functor that returns the corefficients of the recurrence relation.
 216               The coefficients should be centered on position <span class="emphasis"><em>second</em></span>.
 217             </p></dd>
 218 <dt><span class="term">number_of_steps</span></dt>
 219 <dd><p>
 220               The number of steps to apply the recurrence relation backwards from
 221               <span class="emphasis"><em>second</em></span>.
 222             </p></dd>
 223 <dt><span class="term">first</span></dt>
 224 <dd><p>
 225               The value of F<sub>n+1</sub>
 226             </p></dd>
 227 <dt><span class="term">second</span></dt>
 228 <dd><p>
 229               The value of F<sub>n</sub>
 230             </p></dd>
 231 <dt><span class="term">log_scaling</span></dt>
 232 <dd><p>
 233               When provided, the recurrence relations may be rescaled internally
 234               to avoid over/underflow issues. The result should be multiplied by
 235               <code class="computeroutput"><span class="identifier">exp</span><span class="special">(*</span><span class="identifier">log_scaling</span><span class="special">)</span></code>
 236               to get the true value of the result.
 237             </p></dd>
 238 <dt><span class="term">previous</span></dt>
 239 <dd><p>
 240               When provided, is set to the value of F<sub>n - number_of_steps + 1</sub>
 241             </p></dd>
 242 </dl>
 243 </div>
 244 <p>
 245         Returns F<sub>n - number_of_steps</sub>.
 246       </p>
 247 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">&gt;</span>
 248 <span class="keyword">struct</span> <span class="identifier">forward_recurrence_iterator</span>
 249 <span class="special">{</span>
 250    <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">remove_reference</span><span class="special">&lt;</span><span class="keyword">decltype</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">get</span><span class="special">&lt;</span><span class="number">0</span><span class="special">&gt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">declval</span><span class="special">&lt;</span><span class="identifier">Recurrence</span><span class="special">&amp;&gt;()(</span><span class="number">0</span><span class="special">)))&gt;::</span><span class="identifier">type</span> <span class="identifier">value_type</span><span class="special">;</span>
 251
 252    <span class="identifier">forward_recurrence_iterator</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="identifier">f_n_minus_1</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="identifier">f_n</span><span class="special">);</span>
 253    <span class="identifier">forward_recurrence_iterator</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="identifier">f_n</span><span class="special">);</span>
 254    <span class="comment">/* Operators omitted for clarity */</span>
 255 <span class="special">};</span>
 256 </pre>
 257 <p>
 258         Type <code class="computeroutput"><span class="identifier">forward_recurrence_iterator</span></code>
 259         defines a forward-iterator for a recurrence relation stable in the forward
 260         direction. The constructors take the recurrence relation, plus either one
 261         or two values: if only one value is provided, then the second is computed
 262         by using the recurrence relation to calculate the function ratio.
 263       </p>
 264 <pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">Recurrence</span><span class="special">&gt;</span>
 265 <span class="keyword">struct</span> <span class="identifier">backward_recurrence_iterator</span>
 266 <span class="special">{</span>
 267    <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">remove_reference</span><span class="special">&lt;</span><span class="keyword">decltype</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">get</span><span class="special">&lt;</span><span class="number">0</span><span class="special">&gt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">declval</span><span class="special">&lt;</span><span class="identifier">Recurrence</span><span class="special">&amp;&gt;()(</span><span class="number">0</span><span class="special">)))&gt;::</span><span class="identifier">type</span> <span class="identifier">value_type</span><span class="special">;</span>
 268
 269    <span class="identifier">backward_recurrence_iterator</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="identifier">f_n_plus_1</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="identifier">f_n</span><span class="special">);</span>
 270    <span class="identifier">backward_recurrence_iterator</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Recurrence</span><span class="special">&amp;</span> <span class="identifier">r</span><span class="special">,</span> <span class="identifier">value_type</span> <span class="identifier">f_n</span><span class="special">);</span>
 271    <span class="comment">/* Operators omitted for clarity */</span>
 272 <span class="special">};</span>
 273 </pre>
 274 <p>
 275         Type <code class="computeroutput"><span class="identifier">backward_recurrence_iterator</span></code>
 276         defines a forward-iterator for a recurrence relation stable in the backward
 277         direction. The constructors take the recurrence relation, plus either one
 278         or two values: if only one value is provided, then the second is computed
 279         by using the recurrence relation to calculate the function ratio.
 280       </p>
 281 <p>
 282         Note that <span class="emphasis"><em>incrementing</em></span> this iterator moves the value
 283         returned successively to F<sub>n-1</sub>, F<sub>n-2</sub> etc.
 284       </p>
 285 </div>
 286 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 287 <td align="left"></td>
 288 <td align="right"><div class="copyright-footer">Copyright &#169; 2006-2019 Nikhar
 289       Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
 290       Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan
 291       R&#229;de, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg,
 292       Daryle Walker and Xiaogang Zhang<p>
 293         Distributed under the Boost Software License, Version 1.0. (See accompanying
 294         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 295       </p>
 296 </div></td>
 297 </tr></table>
 298 <hr>
 299 <div class="spirit-nav">
 300 <a accesskey="p" href="cf.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../internals.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="tuples.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 301 </div>
 302 </body>
 303 </html>