1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Roots of Quartic Polynomials</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="../root_finding.html" title="Chapter 10. Root Finding & Minimization Algorithms">
<link rel="prev" href="cubic_roots.html" title="Roots of Cubic Polynomials">
<link rel="next" href="root_finding_examples.html" title="Examples of Root-Finding (with and without derivatives)">
<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="cubic_roots.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.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="root_finding_examples.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.quartic_roots"></a><a class="link" href="quartic_roots.html" title="Roots of Quartic Polynomials">Roots of Quartic Polynomials</a>
</h2></div></div></div>
<h4>
<a name="math_toolkit.quartic_roots.h0"></a>
<span class="phrase"><a name="math_toolkit.quartic_roots.synopsis"></a></span><a class="link" href="quartic_roots.html#math_toolkit.quartic_roots.synopsis">Synopsis</a>
</h4>
<pre class="programlisting"><span class="preprocessor">#include</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">tools</span><span class="special">/</span><span class="identifier">quartic_roots</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="keyword">namespace</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="comment">// Solves ax⁴ + bx³ + cx² + dx + e = 0.</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">Real</span><span class="special">,</span><span class="number">3</span><span class="special">></span> <span class="identifier">quartic_roots</span><span class="special">(</span><span class="identifier">Real</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">b</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">c</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">d</span><span class="special">,</span> <span class="identifier">Real</span> <span class="identifier">e</span><span class="special">);</span>
<span class="special">}</span>
</pre>
<h4>
<a name="math_toolkit.quartic_roots.h1"></a>
<span class="phrase"><a name="math_toolkit.quartic_roots.background"></a></span><a class="link" href="quartic_roots.html#math_toolkit.quartic_roots.background">Background</a>
</h4>
<p>
The <code class="computeroutput"><span class="identifier">quartic_roots</span></code> function
extracts all real roots of a quartic polynomial ax⁴+ bx³ + cx² + dx + e.
The result is a <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">array</span><span class="special"><</span><span class="identifier">Real</span><span class="special">,</span> <span class="number">4</span><span class="special">></span></code>, which has length four, irrespective of
the number of real roots the polynomial possesses. (This is to prevent the
performance overhead of allocating a vector, which often exceeds the time to
extract the roots.) The roots are returned in nondecreasing order. If a root
is complex, then it is placed at the back of the array and set to a nan.
</p>
<p>
The algorithm uses the classical method of Ferrari, and follows <a href="https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c" target="_top">Graphics
Gems V</a>, with an additional Halley iterate for root polishing. A typical
use of a quartic real-root solver is to raytrace a torus.
</p>
<h4>
<a name="math_toolkit.quartic_roots.h2"></a>
<span class="phrase"><a name="math_toolkit.quartic_roots.performance_and_accuracy"></a></span><a class="link" href="quartic_roots.html#math_toolkit.quartic_roots.performance_and_accuracy">Performance
and Accuracy</a>
</h4>
<p>
On a consumer laptop, we observe extraction of the roots taking ~90ns. The
file <code class="computeroutput"><span class="identifier">reporting</span><span class="special">/</span><span class="identifier">performance</span><span class="special">/</span><span class="identifier">quartic_roots_performance</span><span class="special">.</span><span class="identifier">cpp</span></code> allows determination of the speed on
your system.
</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="cubic_roots.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_finding.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="root_finding_examples.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
