boost/math
2
0
Fork 0
mirror of https://github.com/boostorg/math.git synced 2026-02-02 21:02:20 +00:00
Code Issues Projects Releases Wiki Activity
Files
fix_ci
math/doc/html/math_toolkit/number_series/fibonacci_numbers.html
jzmaddock 4c2cdc2cf6 Regenerate docs.
2024-08-06 13:18:32 +01:00

197 lines
19 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters
This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Fibonacci Numbers</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../number_series.html" title="Number Series">
<link rel="prev" href="primes.html" title="Prime Numbers">
<link rel="next" href="../sf_gamma.html" title="Gamma Functions">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="primes.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../number_series.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="../sf_gamma.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.number_series.fibonacci_numbers"></a><a class="link" href="fibonacci_numbers.html" title="Fibonacci Numbers">Fibonacci
Numbers</a>
</h3></div></div></div>
<p>
<a href="https://en.wikipedia.org/wiki/Fibonacci_number" target="_top">Fibonacci numbers</a>
(F<sub>n</sub>) follows the linear recurrence F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub> starting with F<sub>0</sub>=0, F<sub>1</sub>=1.
</p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h0"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.synopsis"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.synopsis">Synopsis</a>
</h5>
<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">special_functions</span><span class="special">/</span><span class="identifier">fibonacci</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<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">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">Policy</span><span class="special">&gt;</span>
<span class="keyword">constexpr</span> <span class="identifier">T</span> <span class="identifier">fibonacci</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">)</span> <span class="comment">// Checked version (default policy)</span>
<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">Policy</span><span class="special">&gt;</span>
<span class="keyword">constexpr</span> <span class="identifier">T</span> <span class="identifier">fibonacci</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">Policy</span> <span class="special">&amp;</span><span class="identifier">pol</span><span class="special">)</span> <span class="comment">// Checked version (policy for errors etc.)</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="keyword">constexpr</span> <span class="identifier">T</span> <span class="identifier">unchecked_fibonacci</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">)</span> <span class="keyword">noexcept</span><span class="special">(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">is_fundamental</span><span class="special">&lt;</span><span class="identifier">T</span><span class="special">&gt;::</span><span class="identifier">value</span><span class="special">);</span> <span class="special">{</span> <span class="comment">// Unchecked version (no policy).</span>
<span class="special">}}</span> <span class="comment">// namespaces</span>
</pre>
<p>
The functions return F<sub>n</sub> for a given input <code class="literal">n</code> having type
<code class="literal">T</code>.
</p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h1"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.description"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.description">Description</a>
</h5>
<p>
The checked versions checks for the overflow before starting the computation.
If <code class="literal">n</code> is so large that the result can not be represented
in type <code class="literal">T</code>, it then calls <a class="link" href="../error_handling.html#math_toolkit.error_handling.overflow_error">overflow_error</a>.
The overflow check is susceptible to off-by-one errors around the overflow
limit. See Binet's Formula below for more details on the check.
</p>
<p>
These functions are all <code class="computeroutput"><span class="keyword">constexpr</span></code>
from C++14 onwards, and in addition <code class="computeroutput"><span class="identifier">unchecked_fibonacci</span></code>
is <code class="computeroutput"><span class="keyword">noexcept</span></code> when T is a fundamental
type.
</p>
<p>
The final <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can
be used to control the behaviour of the function: how it handles errors,
what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">policy
documentation for more details</a>.
</p>
<p>
If in the checked version, the overflow check succeeds then the unchecked
version is called which computes the desired F<sub>n</sub>. Checked version is slower
because of the overhead involved in overflow check.
</p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h2"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.generator"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.generator">Generator</a>
</h5>
<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">special_functions</span><span class="special">/</span><span class="identifier">fibonacci</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">fibonacci_generator</span> <span class="special">{</span>
<span class="comment">// returns consecutive fibonacci number starting from 0, 1, 1, 2, ...</span>
<span class="identifier">T</span> <span class="keyword">operator</span><span class="special">()();</span>
<span class="comment">// reset the generator to start from nth fibonacci number</span>
<span class="keyword">void</span> <span class="identifier">set</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> <span class="identifier">n</span><span class="special">);</span>
<span class="special">}</span>
</pre>
<p>
The generator returns consecutive fibonacci numbers starting with 0, 1, 1,
2...
</p>
<p>
The state of the generator can be modified using <code class="literal">set()</code>
which makes generator return consecutive fibonacci numbers starting from
<code class="literal">n</code>[sup th] fibonacci number.
</p>
<pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">fibonacci_generator</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">gen</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">x</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span> <span class="comment">// x is 0</span>
<span class="keyword">int</span> <span class="identifier">y</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span> <span class="comment">// y is 1</span>
<span class="keyword">for</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="number">5</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="comment">// this loop is same as gen.set(7);</span>
<span class="identifier">gen</span><span class="special">();</span>
<span class="keyword">int</span> <span class="identifier">z</span> <span class="special">=</span> <span class="identifier">gen</span><span class="special">();</span> <span class="comment">// z is 13 </span>
</pre>
<p>
Generator is non-throwing for all fundamental types and will not check for
overflows.
</p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h3"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.type_requirements"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.type_requirements">Type
Requirements</a>
</h5>
<p>
The type must be an arithmetic type supporting +, -, * and can be initialized
from trivial integral types.
</p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h4"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.example"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.example">Example</a>
</h5>
<p>
The file <a href="../../../../example/reciprocal_fibonacci_constant.cpp" target="_top">reciprocal_fibonacci_constant.cpp</a>
uses <code class="computeroutput"><span class="identifier">fibonacci_generator</span></code>
to calculate the reciprocal fibonacci constant to 1000 digit precision like
so:
</p>
<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">special_functions</span><span class="special">/</span><span class="identifier">fibonacci</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">multiprecision</span><span class="special">/</span><span class="identifier">mpfr</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iomanip</span><span class="special">&gt;</span>
<span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iostream</span><span class="special">&gt;</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> <span class="special">{</span>
<span class="keyword">using</span> <span class="identifier">Real</span> <span class="special">=</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">multiprecision</span><span class="special">::</span><span class="identifier">mpfr_float_1000</span><span class="special">;</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">fibonacci_generator</span><span class="special">&lt;</span><span class="identifier">Real</span><span class="special">&gt;</span> <span class="identifier">gen</span><span class="special">;</span>
<span class="identifier">gen</span><span class="special">.</span><span class="identifier">set</span><span class="special">(</span><span class="number">1</span><span class="special">);</span> <span class="comment">// start producing values from 1st fibonacci number</span>
<span class="identifier">Real</span> <span class="identifier">ans</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span>
<span class="keyword">const</span> <span class="keyword">int</span> <span class="identifier">ITR</span> <span class="special">=</span> <span class="number">1000</span><span class="special">;</span>
<span class="keyword">for</span> <span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> <span class="identifier">i</span> <span class="special">&lt;</span> <span class="identifier">ITR</span><span class="special">;</span> <span class="special">++</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{</span>
<span class="identifier">ans</span> <span class="special">+=</span> <span class="number">1.0</span> <span class="special">/</span> <span class="identifier">gen</span><span class="special">();</span>
<span class="special">}</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">setprecision</span><span class="special">(</span><span class="number">1000</span><span class="special">)</span> <span class="special">&lt;&lt;</span> <span class="string">"Reciprocal fibonacci constant after "</span>
<span class="special">&lt;&lt;</span> <span class="identifier">ITR</span> <span class="special">&lt;&lt;</span> <span class="string">" iterations is: "</span> <span class="special">&lt;&lt;</span> <span class="identifier">ans</span> <span class="special">&lt;&lt;</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h5"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.implementation"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.implementation">Implementation</a>
</h5>
<p>
The time complexity for computing fibonacci number is O(log n), without considering
the time complexities of multiplication and addition (where <code class="literal">n</code>
is the input parameter). The implementation is iterative version of <a href="http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF" target="_top">Dijkstra's identities</a>
and which simply walks down the bits of <code class="literal">n</code>.
</p>
<h5>
<a name="math_toolkit.number_series.fibonacci_numbers.h6"></a>
<span class="phrase"><a name="math_toolkit.number_series.fibonacci_numbers.binet"></a></span><a class="link" href="fibonacci_numbers.html#math_toolkit.number_series.fibonacci_numbers.binet">Binet's
Formula</a>
</h5>
<p>
There is a closed form expression for computing fibonacci numbers but since
it suffers from imprecision issues (using floating point computation), it
is not implemented.
</p>
<p>
However an approximate formula is used for the overflow checking in the checked
version.
</p>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
Walker and Xiaogang Zhang<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
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>)
</p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="primes.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../number_series.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="../sf_gamma.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink