boost/math
2
0
Fork 0
mirror of https://github.com/boostorg/math.git synced 2026-01-23 05:42:15 +00:00
Code Issues Projects Releases Wiki Activity
Files
cuda
math/doc/html/math_toolkit/root_comparison/root_n_comparison.html
jzmaddock bf57b10feb Documentation update [CI SKIP]
2018-05-27 17:38:50 +01:00

5287 lines
97 KiB
HTML
Raw Permalink Blame History

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Comparison of Nth-root Finding Algorithms</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Math Toolkit 2.6.1">
<link rel="up" href="../root_comparison.html" title="Comparison of Root Finding Algorithms">
<link rel="prev" href="cbrt_comparison.html" title="Comparison of Cube Root Finding Algorithms">
<link rel="next" href="elliptic_comparison.html" title="Comparison of Elliptic Integral Root Finding Algoritghms">
</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="cbrt_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="elliptic_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.root_n_comparison"></a><a class="link" href="root_n_comparison.html" title="Comparison of Nth-root Finding Algorithms">Comparison
of Nth-root Finding Algorithms</a>
</h3></div></div></div>
<p>
A second example compares four generalized nth-root finding algorithms for
various n-th roots (5, 7 and 13) of a single value 28.0, for four floating-point
types, <code class="computeroutput"><span class="keyword">float</span></code>, <code class="computeroutput"><span class="keyword">double</span></code>, <code class="computeroutput"><span class="keyword">long</span>
<span class="keyword">double</span></code> and a <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>
type <code class="computeroutput"><span class="identifier">cpp_bin_float_50</span></code>. In
each case the target accuracy was set using our "recomended" accuracy
limits (or at least limits that make a good starting point - which is likely
to give close to full accuracy without resorting to unnecessary iterations).
</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&lt;T&gt;::digits - 2
</p>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
floor(numeric_limits&lt;T&gt;::digits * 0.6)
</p>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
floor(numeric_limits&lt;T&gt;::digits * 0.4)
</p>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
floor(numeric_limits&lt;T&gt;::digits * 0.4)
</p>
</td>
</tr>
</tbody>
</table></div>
<p>
Tests used Microsoft Visual Studio 2013 (Update 1) and GCC 4.9.1 using source
code <a href="../../../../example/root_n_finding_algorithms.cpp" target="_top">root_n_finding_algorithms.cpp</a>.
</p>
<p>
The timing uncertainty (especially using MSVC) is at least 5% of normalized
time 'Norm'.
</p>
<p>
To pick out the 'best' and 'worst' algorithms are highlighted in blue and
red. More than one result can be 'best' when normalized times are indistinguishable
within the uncertainty.
</p>
<h4>
<a name="math_toolkit.root_comparison.root_n_comparison.h0"></a>
<span class="phrase"><a name="math_toolkit.root_comparison.root_n_comparison.program_example_root_n_finding_a"></a></span><a class="link" href="root_n_comparison.html#math_toolkit.root_comparison.root_n_comparison.program_example_root_n_finding_a">Program
..\example\root_n_finding_algorithms.cpp, Microsoft Visual C++ version 14.1,
Dinkumware standard library version 650, Win32 Compiled in optimise mode.,
_X86_SSE2</a>
</h4>
<p>
Fraction of full accuracy 1
</p>
<div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_5"></a><p class="title"><b>Table&#160;8.3.&#160;5th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X86_SSE2</b></p>
<div class="table-contents"><table class="table" summary="5th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X86_SSE2">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
457
</p>
</td>
<td>
<p>
2.00
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
11
</p>
</td>
<td>
<p>
860
</p>
</td>
<td>
<p>
3.54
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
11
</p>
</td>
<td>
<p>
806
</p>
</td>
<td>
<p>
3.02
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
226875
</p>
</td>
<td>
<p>
<span class="red">8.11</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
228
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
243
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
298
</p>
</td>
<td>
<p>
1.12
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
27968
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
<p>
250
</p>
</td>
<td>
<p>
1.10
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
268
</p>
</td>
<td>
<p>
1.10
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
267
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
52812
</p>
</td>
<td>
<p>
1.89
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
<p>
256
</p>
</td>
<td>
<p>
1.12
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
271
</p>
</td>
<td>
<p>
1.12
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
270
</p>
</td>
<td>
<p>
<span class="blue">1.01</span>
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
61406
</p>
</td>
<td>
<p>
2.20
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_7"></a><p class="title"><b>Table&#160;8.4.&#160;7th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X86_SSE2</b></p>
<div class="table-contents"><table class="table" summary="7th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X86_SSE2">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
825
</p>
</td>
<td>
<p>
3.06
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
15
</p>
</td>
<td>
<p>
1145
</p>
</td>
<td>
<p>
<span class="red">4.06</span>
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
15
</p>
</td>
<td>
<p>
1159
</p>
</td>
<td>
<p>
<span class="red">4.17</span>
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
295781
</p>
</td>
<td>
<p>
<span class="red">8.12</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
270
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
282
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
278
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
8
</p>
</td>
<td>
<p>
36406
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
303
</p>
</td>
<td>
<p>
1.12
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
329
</p>
</td>
<td>
<p>
1.17
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
335
</p>
</td>
<td>
<p>
1.21
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
78281
</p>
</td>
<td>
<p>
2.15
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
340
</p>
</td>
<td>
<p>
1.26
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
432
</p>
</td>
<td>
<p>
1.53
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
367
</p>
</td>
<td>
<p>
1.32
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
85156
</p>
</td>
<td>
<p>
2.34
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_11"></a><p class="title"><b>Table&#160;8.5.&#160;11th root(28) for float, double, long double and cpp_bin_float_50
types, using _X86_SSE2</b></p>
<div class="table-contents"><table class="table" summary="11th root(28) for float, double, long double and cpp_bin_float_50
types, using _X86_SSE2">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
714
</p>
</td>
<td>
<p>
3.16
</p>
</td>
<td>
<p>
-2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
909
</p>
</td>
<td>
<p>
<span class="red">4.19</span>
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
793
</p>
</td>
<td>
<p>
3.69
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
17
</p>
</td>
<td>
<p>
211718
</p>
</td>
<td>
<p>
<span class="red">9.28</span>
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
226
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
217
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
215
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
9
</p>
</td>
<td>
<p>
22812
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
262
</p>
</td>
<td>
<p>
1.16
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
260
</p>
</td>
<td>
<p>
1.20
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
260
</p>
</td>
<td>
<p>
1.21
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
40781
</p>
</td>
<td>
<p>
1.79
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
332
</p>
</td>
<td>
<p>
1.47
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
314
</p>
</td>
<td>
<p>
1.45
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
310
</p>
</td>
<td>
<p>
1.44
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
8
</p>
</td>
<td>
<p>
67187
</p>
</td>
<td>
<p>
2.95
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><h4>
<a name="math_toolkit.root_comparison.root_n_comparison.h1"></a>
<span class="phrase"><a name="math_toolkit.root_comparison.root_n_comparison.program_root_n_finding_algorithm"></a></span><a class="link" href="root_n_comparison.html#math_toolkit.root_comparison.root_n_comparison.program_root_n_finding_algorithm">Program
root_n_finding_algorithms.cpp, Microsoft Visual C++ version 12.0, Dinkumware
standard library version 610, Win32 Compiled in optimise mode., _X64_AVX</a>
</h4>
<p>
Fraction of full accuracy 1
</p>
<div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_5_0"></a><p class="title"><b>Table&#160;8.6.&#160;5th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_AVX</b></p>
<div class="table-contents"><table class="table" summary="5th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_AVX">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
239
</p>
</td>
<td>
<p>
1.50
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
11
</p>
</td>
<td>
<p>
451
</p>
</td>
<td>
<p>
2.53
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
11
</p>
</td>
<td>
<p>
439
</p>
</td>
<td>
<p>
2.49
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
90312
</p>
</td>
<td>
<p>
<span class="red">7.51</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
159
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
178
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
176
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
12031
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
<p>
168
</p>
</td>
<td>
<p>
1.06
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
203
</p>
</td>
<td>
<p>
1.14
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
198
</p>
</td>
<td>
<p>
1.13
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
20937
</p>
</td>
<td>
<p>
1.74
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
<p>
173
</p>
</td>
<td>
<p>
1.09
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
206
</p>
</td>
<td>
<p>
1.16
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
203
</p>
</td>
<td>
<p>
1.15
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
26250
</p>
</td>
<td>
<p>
2.18
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_7_0"></a><p class="title"><b>Table&#160;8.7.&#160;7th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_AVX</b></p>
<div class="table-contents"><table class="table" summary="7th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_AVX">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
385
</p>
</td>
<td>
<p>
2.19
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
15
</p>
</td>
<td>
<p>
635
</p>
</td>
<td>
<p>
3.13
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
15
</p>
</td>
<td>
<p>
621
</p>
</td>
<td>
<p>
3.17
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
114843
</p>
</td>
<td>
<p>
<span class="red">6.81</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
176
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
203
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
196
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
8
</p>
</td>
<td>
<p>
16875
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
209
</p>
</td>
<td>
<p>
1.19
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
254
</p>
</td>
<td>
<p>
1.25
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
246
</p>
</td>
<td>
<p>
1.26
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
32343
</p>
</td>
<td>
<p>
1.92
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
223
</p>
</td>
<td>
<p>
1.27
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
273
</p>
</td>
<td>
<p>
1.34
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
275
</p>
</td>
<td>
<p>
1.40
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
45156
</p>
</td>
<td>
<p>
2.68
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_11_0"></a><p class="title"><b>Table&#160;8.8.&#160;11th root(28) for float, double, long double and cpp_bin_float_50
types, using _X64_AVX</b></p>
<div class="table-contents"><table class="table" summary="11th root(28) for float, double, long double and cpp_bin_float_50
types, using _X64_AVX">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
467
</p>
</td>
<td>
<p>
2.42
</p>
</td>
<td>
<p>
-2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
648
</p>
</td>
<td>
<p>
3.06
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
640
</p>
</td>
<td>
<p>
2.99
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
17
</p>
</td>
<td>
<p>
170000
</p>
</td>
<td>
<p>
<span class="red">8.85</span>
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
193
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
212
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
214
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
9
</p>
</td>
<td>
<p>
19218
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
209
</p>
</td>
<td>
<p>
1.08
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
256
</p>
</td>
<td>
<p>
1.21
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
250
</p>
</td>
<td>
<p>
1.17
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
32656
</p>
</td>
<td>
<p>
1.70
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
248
</p>
</td>
<td>
<p>
1.28
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
306
</p>
</td>
<td>
<p>
1.44
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
298
</p>
</td>
<td>
<p>
1.39
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
8
</p>
</td>
<td>
<p>
53437
</p>
</td>
<td>
<p>
2.78
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><h4>
<a name="math_toolkit.root_comparison.root_n_comparison.h2"></a>
<span class="phrase"><a name="math_toolkit.root_comparison.root_n_comparison.program_example_root_n_finding_0"></a></span><a class="link" href="root_n_comparison.html#math_toolkit.root_comparison.root_n_comparison.program_example_root_n_finding_0">Program
..\example\root_n_finding_algorithms.cpp, GNU C++ version 7.1.0, GNU libstdc++
version 20170502, Win32 Compiled in optimise mode., _X64_SSE2</a>
</h4>
<p>
Fraction of full accuracy 1
</p>
<div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_5_1"></a><p class="title"><b>Table&#160;8.9.&#160;5th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_SSE2</b></p>
<div class="table-contents"><table class="table" summary="5th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_SSE2">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
206
</p>
</td>
<td>
<p>
2.24
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
11
</p>
</td>
<td>
<p>
460
</p>
</td>
<td>
<p>
<span class="red">4.04</span>
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
9
</p>
</td>
<td>
<p>
554
</p>
</td>
<td>
<p>
<span class="red">4.40</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
57656
</p>
</td>
<td>
<p>
<span class="red">8.39</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
92
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
114
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
126
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
6875
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
<p>
106
</p>
</td>
<td>
<p>
1.15
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
134
</p>
</td>
<td>
<p>
1.18
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
178
</p>
</td>
<td>
<p>
1.41
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
12500
</p>
</td>
<td>
<p>
1.82
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
<p>
126
</p>
</td>
<td>
<p>
1.37
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
143
</p>
</td>
<td>
<p>
1.25
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
3
</p>
</td>
<td>
<p>
198
</p>
</td>
<td>
<p>
1.57
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
15312
</p>
</td>
<td>
<p>
2.23
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_7_1"></a><p class="title"><b>Table&#160;8.10.&#160;7th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_SSE2</b></p>
<div class="table-contents"><table class="table" summary="7th root(28) for float, double, long double and cpp_bin_float_50 types,
using _X64_SSE2">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
345
</p>
</td>
<td>
<p>
2.09
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
15
</p>
</td>
<td>
<p>
615
</p>
</td>
<td>
<p>
3.14
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
13
</p>
</td>
<td>
<p>
875
</p>
</td>
<td>
<p>
3.98
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
70937
</p>
</td>
<td>
<p>
<span class="red">7.32</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
165
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
196
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
220
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
8
</p>
</td>
<td>
<p>
9687
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
193
</p>
</td>
<td>
<p>
1.17
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
239
</p>
</td>
<td>
<p>
1.22
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
298
</p>
</td>
<td>
<p>
1.35
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
19062
</p>
</td>
<td>
<p>
1.97
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
217
</p>
</td>
<td>
<p>
1.32
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
270
</p>
</td>
<td>
<p>
1.38
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
367
</p>
</td>
<td>
<p>
1.67
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
27343
</p>
</td>
<td>
<p>
2.82
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><div class="table">
<a name="math_toolkit.root_comparison.root_n_comparison.root_11_1"></a><p class="title"><b>Table&#160;8.11.&#160;11th root(28) for float, double, long double and cpp_bin_float_50
types, using _X64_SSE2</b></p>
<div class="table-contents"><table class="table" summary="11th root(28) for float, double, long double and cpp_bin_float_50
types, using _X64_SSE2">
<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">&#160;</td>
<td class="auto-generated">&#160;</td>
</tr></thead>
<tbody>
<tr>
<td>
<p>
Algo
</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>
TOMS748
</p>
</td>
<td>
<p>
12
</p>
</td>
<td>
<p>
412
</p>
</td>
<td>
<p>
2.15
</p>
</td>
<td>
<p>
-2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
646
</p>
</td>
<td>
<p>
2.96
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
<td>
<p>
14
</p>
</td>
<td>
<p>
1054
</p>
</td>
<td>
<p>
<span class="red">4.22</span>
</p>
</td>
<td>
<p>
1
</p>
</td>
<td>
</td>
<td>
<p>
17
</p>
</td>
<td>
<p>
107187
</p>
</td>
<td>
<p>
<span class="red">9.53</span>
</p>
</td>
<td>
<p>
2
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Newton
</p>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
192
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
218
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
250
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
9
</p>
</td>
<td>
<p>
11250
</p>
</td>
<td>
<p>
<span class="blue">1.00</span>
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Halley
</p>
</td>
<td>
<p>
4
</p>
</td>
<td>
<p>
200
</p>
</td>
<td>
<p>
<span class="blue">1.04</span>
</p>
</td>
<td>
<p>
-1
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
243
</p>
</td>
<td>
<p>
1.11
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
5
</p>
</td>
<td>
<p>
345
</p>
</td>
<td>
<p>
1.38
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
19687
</p>
</td>
<td>
<p>
1.75
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
<tr>
<td>
<p>
Schr&#246;der
</p>
</td>
<td>
<p>
6
</p>
</td>
<td>
<p>
254
</p>
</td>
<td>
<p>
1.32
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
321
</p>
</td>
<td>
<p>
1.47
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
7
</p>
</td>
<td>
<p>
471
</p>
</td>
<td>
<p>
1.88
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
<td>
<p>
8
</p>
</td>
<td>
<p>
33281
</p>
</td>
<td>
<p>
2.96
</p>
</td>
<td>
<p>
0
</p>
</td>
<td>
</td>
</tr>
</tbody>
</table></div>
</div>
<br class="table-break"><p>
Some tentative conclusions can be drawn from this limited exercise.
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Perhaps surprisingly, there is little difference between the various
algorithms for <a href="http://en.cppreference.com/w/cpp/language/types" target="_top">fundamental
types</a> floating-point types. Using the first derivatives (<a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson iteration</a>)
is usually the best, but while the improvement over the no-derivative
<a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS Algorithm
748: enclosing zeros of continuous functions</a> is considerable
in number of iterations, but little in execution time. This reflects
the fact that the function we are finding the root for is trivial to
evaluate, so runtimetimes are dominated by the time taken by the boilerplate
code in each method.
</li>
<li class="listitem">
The extra cost of evaluating the second derivatives (<a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.halley">Halley</a>
or <a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.schroder">Schr&#246;der</a>)
is usually too much for any net benefit: as with the cube root, these
functors are so cheap to evaluate that the runtime is largely dominated
by the complexity of the root finding method.
</li>
<li class="listitem">
For a <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>
floating-point type, the <a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson
iteration</a> is a clear winner with a several-fold gain over <a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS Algorithm 748:
enclosing zeros of continuous functions</a>, and again no improvement
from the second-derivative algorithms.
</li>
<li class="listitem">
The run-time of 50 decimal-digit <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>
is about 30-fold greater than <code class="computeroutput"><span class="keyword">double</span></code>.
</li>
<li class="listitem">
The column 'dis' showing the number of bits distance from the correct
result. The Newton-Raphson algorithm shows a bit or two better accuracy
than <a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS Algorithm
748: enclosing zeros of continuous functions</a>.
</li>
<li class="listitem">
The goodness of the 'guess' is especially crucial for <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>.
Separate experiments show that evaluating the 'guess' using <code class="computeroutput"><span class="keyword">double</span></code> allows convergence to the final
exact result in one or two iterations. So in this contrived example,
crudely dividing the exponent by N for a 'guess', it would be far better
to use a <code class="computeroutput"><span class="identifier">pow</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;</span></code>
or , if more precise <code class="computeroutput"><span class="identifier">pow</span><span class="special">&lt;</span><span class="keyword">long</span> <span class="keyword">double</span><span class="special">&gt;</span></code>,
function to estimate a '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">
Using floating-point extension <a href="http://en.wikipedia.org/wiki/SSE2" target="_top">SSE2
instructions</a> made a modest ten-percent speedup.
</li>
<li class="listitem">
Using MSVC, there was some improvement using 64-bit, markedly for <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>.
</li>
<li class="listitem">
The GCC compiler 4.9.1 using 64-bit was at least five-folder faster that
32-bit, apparently reflecting better optimization.
</li>
</ul></div>
<p>
Clearly, your mileage <span class="bold"><strong>will vary</strong></span>, but in
summary, <a class="link" href="../roots_deriv.html#math_toolkit.roots_deriv.newton">Newton-Raphson iteration</a>
seems the first choice of algorithm, and effort to find a good 'guess' the
first speed-up target, especially for <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>.
And of course, compiler optimisation is crucial for speed.
</p>
</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 &#169; 2006-2010, 2012-2014, 2017 Nikhar
Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos,
Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan R&#229;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="cbrt_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="elliptic_comparison.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink