1590 lines
38 KiB
HTML
1590 lines
38 KiB
HTML
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
|
|
<title>Comparison of Cube Root Finding Algorithms</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 2.11.0">
|
|
<link rel="up" href="../root_comparison.html" title="Comparison of Root Finding Algorithms">
|
|
<link rel="prev" href="../root_comparison.html" title="Comparison of Root Finding Algorithms">
|
|
<link rel="next" href="root_n_comparison.html" title="Comparison of Nth-root Finding Algorithms">
|
|
</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="../root_comparison.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_comparison.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_n_comparison.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.root_comparison.cbrt_comparison"></a><a class="link" href="cbrt_comparison.html" title="Comparison of Cube Root Finding Algorithms">Comparison
|
|
of Cube Root Finding Algorithms</a>
|
|
</h3></div></div></div>
|
|
<p>
|
|
In the table below, the cube root of 28 was computed for three <a href="http://en.cppreference.com/w/cpp/language/types" target="_top">fundamental
|
|
(built-in) types</a> floating-point types, and one <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>
|
|
type <a href="../../../../../../libs/multiprecision/doc/html/boost_multiprecision/tut/floats/cpp_bin_float.html" target="_top">cpp_bin_float</a>
|
|
using 50 decimal digit precision, using four algorithms.
|
|
</p>
|
|
<p>
|
|
The 'exact' answer was computed using a 100 decimal digit type:
|
|
</p>
|
|
<pre class="programlisting"><span class="identifier">cpp_bin_float_100</span> <span class="identifier">full_answer</span> <span class="special">(</span><span class="string">"3.036588971875662519420809578505669635581453977248111123242141654169177268411884961770250390838097895"</span><span class="special">);</span>
|
|
</pre>
|
|
<p>
|
|
Times were measured using <a href="../../../../../../libs/timer/doc/index.html" target="_top">Boost.Timer</a>
|
|
using <code class="computeroutput"><span class="keyword">class</span> <span class="identifier">cpu_timer</span></code>.
|
|
</p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|
<li class="listitem">
|
|
<span class="emphasis"><em>Its</em></span> is the number of iterations taken to find the
|
|
root.
|
|
</li>
|
|
<li class="listitem">
|
|
<span class="emphasis"><em>Times</em></span> is the CPU time-taken in arbitrary units.
|
|
</li>
|
|
<li class="listitem">
|
|
<span class="emphasis"><em>Norm</em></span> is a normalized time, in comparison to the
|
|
quickest algorithm (with value 1.00).
|
|
</li>
|
|
<li class="listitem">
|
|
<span class="emphasis"><em>Dis</em></span> is the distance from the nearest representation
|
|
of the 'exact' root in bits. Distance from the 'exact' answer is measured
|
|
by using function <a href="../../../../../../libs/math/doc/html/math_toolkit/next_float/float_distance.html" target="_top">Boost.Math
|
|
float_distance</a>. One or two bits distance means that all results
|
|
are effectively 'correct'. Zero means 'exact' - the nearest <a href="http://en.wikipedia.org/wiki/Floating_point#Representable_numbers.2C_conversion_and_rounding" target="_top">representable</a>
|
|
value for the floating-point type.
|
|
</li>
|
|
</ul></div>
|
|
<p>
|
|
The cube-root function is a simple function, and is a contrived example for
|
|
root-finding. It does allow us to investigate some of the factors controlling
|
|
efficiency that may be extrapolated to more complex functions.
|
|
</p>
|
|
<p>
|
|
The program used was <a href="../../../../example/root_finding_algorithms.cpp" target="_top">root_finding_algorithms.cpp</a>.
|
|
100000 evaluations of each floating-point type and algorithm were used and
|
|
the CPU times were judged from repeat runs to have an uncertainty of 10 %.
|
|
Comparing MSVC for <code class="computeroutput"><span class="keyword">double</span></code> and
|
|
<code class="computeroutput"><span class="keyword">long</span> <span class="keyword">double</span></code>
|
|
(which are identical on this patform) may give a guide to uncertainty of
|
|
timing.
|
|
</p>
|
|
<p>
|
|
The requested precision was set as follows:
|
|
</p>
|
|
<div class="informaltable"><table class="table">
|
|
<colgroup>
|
|
<col>
|
|
<col>
|
|
</colgroup>
|
|
<thead><tr>
|
|
<th>
|
|
<p>
|
|
Function
|
|
</p>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
Precision Requested
|
|
</p>
|
|
</th>
|
|
</tr></thead>
|
|
<tbody>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
TOMS748
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
numeric_limits<T>::digits - 2
|
|
</p>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Newton
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
floor(numeric_limits<T>::digits * 0.6)
|
|
</p>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Halley
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
floor(numeric_limits<T>::digits * 0.4)
|
|
</p>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Schröder
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
floor(numeric_limits<T>::digits * 0.4)
|
|
</p>
|
|
</td>
|
|
</tr>
|
|
</tbody>
|
|
</table></div>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|
<li class="listitem">
|
|
The C++ Standard cube root function <a href="http://en.cppreference.com/w/cpp/numeric/math/cbrt" target="_top">std::cbrt</a>
|
|
is only defined for built-in or fundamental types, so cannot be used
|
|
with any User-Defined floating-point types like <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>.
|
|
This, and that the cube function is so impeccably-behaved, allows the
|
|
implementer to use many tricks to achieve a fast computation. On some
|
|
platforms,<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cbrt</span></code> appeared several times as quick
|
|
as the more general <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">cbrt</span></code>,
|
|
on other platforms / compiler options <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">cbrt</span></code>
|
|
is noticeably faster. In general, the results are highly dependent on
|
|
the code-generation / processor architecture selection compiler options
|
|
used. One can assume that the standard library will have been compiled
|
|
with options <span class="emphasis"><em>nearly</em></span> optimal for the platform it
|
|
was installed on, where as the user has more choice over the options
|
|
used for Boost.Math. Pick something too general/conservative and performance
|
|
suffers, while selecting options that make use of the latest instruction
|
|
set opcodes speed's things up noticeably.
|
|
</li>
|
|
<li class="listitem">
|
|
Two compilers in optimise mode were compared: GCC 4.9.1 using Netbeans
|
|
IDS and Microsoft Visual Studio 2013 (Update 1) on the same hardware.
|
|
The number of iterations seemed consistent, but the relative run-times
|
|
surprisingly different.
|
|
</li>
|
|
<li class="listitem">
|
|
<code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">cbrt</span></code> allows use with <span class="emphasis"><em>any
|
|
user-defined floating-point type</em></span>, conveniently <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>.
|
|
It too can take some advantage of the good-behaviour of the cube function,
|
|
compared to the more general implementation in the nth root-finding examples.
|
|
For example, it uses a polynomial approximation to generate a better
|
|
guess than dividing the exponent by three, and can avoid the complex
|
|
checks in <a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson
|
|
iteration</a> required to prevent the search going wildly off-track.
|
|
For a known precision, it may also be possible to fix the number of iterations,
|
|
allowing inlining and loop unrolling. It also algebraically simplifies
|
|
the Halley steps leading to a big reduction in the number of floating
|
|
point operations required compared to a "black box" implementation
|
|
that calculates the derivatives seperately and then combines them in
|
|
the Halley code. Typically, it was found that computation using type
|
|
<code class="computeroutput"><span class="keyword">double</span></code> took a few times
|
|
longer when using the various root-finding algorithms directly rather
|
|
than the hand coded/optimized <code class="computeroutput"><span class="identifier">cbrt</span></code>
|
|
routine.
|
|
</li>
|
|
<li class="listitem">
|
|
The importance of getting a good guess can be seen by the iteration count
|
|
for the multiprecision case: here we "cheat" a little and use
|
|
the cube-root calculated to double precision as the initial guess. The
|
|
limitation of this tactic is that the range of possible (exponent) values
|
|
may be less than the multiprecision type.
|
|
</li>
|
|
<li class="listitem">
|
|
For <a href="http://en.cppreference.com/w/cpp/language/types" target="_top">fundamental
|
|
(built-in) types</a>, there was little to choose between the three
|
|
derivative methods, but for <a href="../../../../../../libs/multiprecision/doc/html/boost_multiprecision/tut/floats/cpp_bin_float.html" target="_top">cpp_bin_float</a>,
|
|
<a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson iteration</a>
|
|
was twice as fast. Note that the cube-root is an extreme test case as
|
|
the cost of calling the functor is so cheap that the runtimes are largely
|
|
dominated by the complexity of the iteration code.
|
|
</li>
|
|
<li class="listitem">
|
|
Compiling with optimisation halved computation times, and any differences
|
|
between algorithms became nearly negligible. The optimisation speed-up
|
|
of the <a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS
|
|
Algorithm 748: enclosing zeros of continuous functions</a> was especially
|
|
noticable.
|
|
</li>
|
|
<li class="listitem">
|
|
Using a multiprecision type like <code class="computeroutput"><span class="identifier">cpp_bin_float_50</span></code>
|
|
for a precision of 50 decimal digits took a lot longer, as expected because
|
|
most computation uses software rather than 64-bit floating-point hardware.
|
|
Speeds are often more than 50 times slower.
|
|
</li>
|
|
<li class="listitem">
|
|
Using <code class="computeroutput"><span class="identifier">cpp_bin_float_50</span></code>,
|
|
<a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS Algorithm
|
|
748: enclosing zeros of continuous functions</a> was much slower
|
|
showing the benefit of using derivatives. <a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson
|
|
iteration</a> was found to be twice as quick as either of the second-derivative
|
|
methods: this is an extreme case though, the function and its derivatives
|
|
are so cheap to compute that we're really measuring the complexity of
|
|
the boilerplate root-finding code.
|
|
</li>
|
|
<li class="listitem">
|
|
For multiprecision types only one or two extra <span class="emphasis"><em>iterations</em></span>
|
|
are needed to get the remaining 35 digits, whatever the algorithm used.
|
|
(The time taken was of course much greater for these types).
|
|
</li>
|
|
<li class="listitem">
|
|
Using a 100 decimal-digit type only doubled the time and required only
|
|
a very few more iterations, so the cost of extra precision is mainly
|
|
the underlying cost of computing more digits, not in the way the algorithm
|
|
works. This confirms previous observations using <a href="http://www.shoup.net/ntl/" target="_top">NTL
|
|
A Library for doing Number Theory</a> high-precision types.
|
|
</li>
|
|
</ul></div>
|
|
<h6>
|
|
<a name="math_toolkit.root_comparison.cbrt_comparison.h0"></a>
|
|
<span class="phrase"><a name="math_toolkit.root_comparison.cbrt_comparison.program_root_finding_algorithms_"></a></span><a class="link" href="cbrt_comparison.html#math_toolkit.root_comparison.cbrt_comparison.program_root_finding_algorithms_">Program
|
|
root_finding_algorithms.cpp, Microsoft Visual C++ version 14.1, Dinkumware
|
|
standard library version 650, Win32, x86<br> 1000000 evaluations of each
|
|
of 5 root_finding algorithms.</a>
|
|
</h6>
|
|
<div class="table">
|
|
<a name="math_toolkit.root_comparison.cbrt_comparison.cbrt_4"></a><p class="title"><b>Table 10.1. Cube root(28) for float, double, long double and cpp_bin_float_50</b></p>
|
|
<div class="table-contents"><table class="table" summary="Cube root(28) for float, double, long double and cpp_bin_float_50">
|
|
<colgroup>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
</colgroup>
|
|
<thead><tr>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
float
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
double
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
long d
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
cpp50
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<td class="auto-generated"> </td>
|
|
<td class="auto-generated"> </td>
|
|
</tr></thead>
|
|
<tbody>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Algorithm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
cbrt
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
78125
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
62500
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
93750
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
11890625
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
1.1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
TOMS748
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
8
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
468750
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">6.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
-1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
11
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
906250
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">15.</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
11
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
906250
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">9.7</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
80859375
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">7.6</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
-2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Newton
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
203125
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
234375
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3.8
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
187500
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
10640625
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Halley
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
234375
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3.0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
265625
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">4.3</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
234375
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
26250000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Schröder
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
296875
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3.8
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
281250
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">4.5</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
234375
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
32437500
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3.0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
</tbody>
|
|
</table></div>
|
|
</div>
|
|
<br class="table-break"><h6>
|
|
<a name="math_toolkit.root_comparison.cbrt_comparison.h1"></a>
|
|
<span class="phrase"><a name="math_toolkit.root_comparison.cbrt_comparison.program_root_finding_algorithms0"></a></span><a class="link" href="cbrt_comparison.html#math_toolkit.root_comparison.cbrt_comparison.program_root_finding_algorithms0">Program
|
|
root_finding_algorithms.cpp, GNU C++ version 8.2.0, GNU libstdc++ version
|
|
20180728, linux, x64<br> 1000000 evaluations of each of 5 root_finding
|
|
algorithms.</a>
|
|
</h6>
|
|
<div class="table">
|
|
<a name="math_toolkit.root_comparison.cbrt_comparison.cbrt_4_0"></a><p class="title"><b>Table 10.2. Cube root(28) for float, double, long double and cpp_bin_float_50</b></p>
|
|
<div class="table-contents"><table class="table" summary="Cube root(28) for float, double, long double and cpp_bin_float_50">
|
|
<colgroup>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
<col>
|
|
</colgroup>
|
|
<thead><tr>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
float
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
double
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
long d
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
<p>
|
|
cpp50
|
|
</p>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<th>
|
|
</th>
|
|
<td class="auto-generated"> </td>
|
|
<td class="auto-generated"> </td>
|
|
</tr></thead>
|
|
<tbody>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Algorithm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Its
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Times
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Norm
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
Dis
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
cbrt
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
30000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
60000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
70000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4440000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
TOMS748
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
8
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
220000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">7.3</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
-1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
11
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
370000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">6.2</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
10
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
580000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">8.3</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
-1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
28360000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="red">6.7</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
-2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Newton
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
120000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4.0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
130000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
180000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.6
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4260000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
<span class="blue">1.0</span>
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
-1
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Halley
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
110000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3.7
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
140000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.3
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
230000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
3.3
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
9210000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
<tr>
|
|
<td>
|
|
<p>
|
|
Schröder
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
120000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4.0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
140000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.3
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
5
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
280000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
4.0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
11630000
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
2.7
|
|
</p>
|
|
</td>
|
|
<td>
|
|
<p>
|
|
0
|
|
</p>
|
|
</td>
|
|
<td>
|
|
</td>
|
|
</tr>
|
|
</tbody>
|
|
</table></div>
|
|
</div>
|
|
<br class="table-break">
|
|
</div>
|
|
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
|
|
<td align="left"></td>
|
|
<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar
|
|
Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
|
|
Hubert Holin, Bruno Lalande, John Maddock, 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></td>
|
|
</tr></table>
|
|
<hr>
|
|
<div class="spirit-nav">
|
|
<a accesskey="p" href="../root_comparison.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../root_comparison.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_n_comparison.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
|
|
</div>
|
|
</body>
|
|
</html>
|