]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <html> |
2 | <head> | |
3 | <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> | |
4 | <title>Comparison of Cube Root Finding Algorithms</title> | |
5 | <link rel="stylesheet" href="../../../math.css" type="text/css"> | |
6 | <meta name="generator" content="DocBook XSL Stylesheets V1.77.1"> | |
7 | <link rel="home" href="../../../index.html" title="Math Toolkit 2.5.1"> | |
8 | <link rel="up" href="../root_comparison.html" title="Comparison of Root Finding Algorithms"> | |
9 | <link rel="prev" href="../root_comparison.html" title="Comparison of Root Finding Algorithms"> | |
10 | <link rel="next" href="root_n_comparison.html" title="Comparison of Nth-root Finding Algorithms"> | |
11 | </head> | |
12 | <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> | |
13 | <table cellpadding="2" width="100%"><tr> | |
14 | <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> | |
15 | <td align="center"><a href="../../../../../../../index.html">Home</a></td> | |
16 | <td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> | |
17 | <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> | |
18 | <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> | |
19 | <td align="center"><a href="../../../../../../../more/index.htm">More</a></td> | |
20 | </tr></table> | |
21 | <hr> | |
22 | <div class="spirit-nav"> | |
23 | <a accesskey="p" href="../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> | |
24 | </div> | |
25 | <div class="section"> | |
26 | <div class="titlepage"><div><div><h4 class="title"> | |
27 | <a name="math_toolkit.roots.root_comparison.cbrt_comparison"></a><a class="link" href="cbrt_comparison.html" title="Comparison of Cube Root Finding Algorithms">Comparison | |
28 | of Cube Root Finding Algorithms</a> | |
29 | </h4></div></div></div> | |
30 | <p> | |
31 | 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 | |
32 | types</a> floating-point types, and one <a href="../../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a> | |
33 | type <a href="../../../../../../../libs/multiprecision/doc/html/boost_multiprecision/tut/floats/cpp_bin_float.html" target="_top">cpp_bin_float</a> | |
34 | using 50 decimal digit precision, using four algorithms. | |
35 | </p> | |
36 | <p> | |
37 | The 'exact' answer was computed using a 100 decimal digit type: | |
38 | </p> | |
39 | <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> | |
40 | </pre> | |
41 | <p> | |
42 | Times were measured using <a href="../../../../../../../libs/timer/doc/index.html" target="_top">Boost.Timer</a> | |
43 | using <code class="computeroutput"><span class="keyword">class</span> <span class="identifier">cpu_timer</span></code>. | |
44 | </p> | |
45 | <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> | |
46 | <li class="listitem"> | |
47 | <span class="emphasis"><em>Its</em></span> is the number of iterations taken to find | |
48 | the root. | |
49 | </li> | |
50 | <li class="listitem"> | |
51 | <span class="emphasis"><em>Times</em></span> is the CPU time-taken in arbitrary units. | |
52 | </li> | |
53 | <li class="listitem"> | |
54 | <span class="emphasis"><em>Norm</em></span> is a normalized time, in comparison to the | |
55 | quickest algorithm (with value 1.00). | |
56 | </li> | |
57 | <li class="listitem"> | |
58 | <span class="emphasis"><em>Dis</em></span> is the distance from the nearest representation | |
59 | of the 'exact' root in bits. Distance from the 'exact' answer is measured | |
60 | by using function <a href="../../../../../../../libs/math/doc/html/math_toolkit/next_float/float_distance.html" target="_top">Boost.Math | |
61 | float_distance</a>. One or two bits distance means that all results | |
62 | 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> | |
63 | value for the floating-point type. | |
64 | </li> | |
65 | </ul></div> | |
66 | <p> | |
67 | The cube-root function is a simple function, and is a contrived example | |
68 | for root-finding. It does allow us to investigate some of the factors controlling | |
69 | efficiency that may be extrapolated to more complex functions. | |
70 | </p> | |
71 | <p> | |
72 | The program used was <a href="../../../../../example/root_finding_algorithms.cpp" target="_top">root_finding_algorithms.cpp</a>. | |
73 | 100000 evaluations of each floating-point type and algorithm were used | |
74 | and the CPU times were judged from repeat runs to have an uncertainty of | |
75 | 10 %. Comparing MSVC for <code class="computeroutput"><span class="keyword">double</span></code> | |
76 | and <code class="computeroutput"><span class="keyword">long</span> <span class="keyword">double</span></code> | |
77 | (which are identical on this patform) may give a guide to uncertainty of | |
78 | timing. | |
79 | </p> | |
80 | <p> | |
81 | The requested precision was set as follows: | |
82 | </p> | |
83 | <div class="informaltable"><table class="table"> | |
84 | <colgroup> | |
85 | <col> | |
86 | <col> | |
87 | </colgroup> | |
88 | <thead><tr> | |
89 | <th> | |
90 | <p> | |
91 | Function | |
92 | </p> | |
93 | </th> | |
94 | <th> | |
95 | <p> | |
96 | Precision Requested | |
97 | </p> | |
98 | </th> | |
99 | </tr></thead> | |
100 | <tbody> | |
101 | <tr> | |
102 | <td> | |
103 | <p> | |
104 | TOMS748 | |
105 | </p> | |
106 | </td> | |
107 | <td> | |
108 | <p> | |
109 | numeric_limits<T>::digits - 2 | |
110 | </p> | |
111 | </td> | |
112 | </tr> | |
113 | <tr> | |
114 | <td> | |
115 | <p> | |
116 | Newton | |
117 | </p> | |
118 | </td> | |
119 | <td> | |
120 | <p> | |
121 | floor(numeric_limits<T>::digits * 0.6) | |
122 | </p> | |
123 | </td> | |
124 | </tr> | |
125 | <tr> | |
126 | <td> | |
127 | <p> | |
128 | Halley | |
129 | </p> | |
130 | </td> | |
131 | <td> | |
132 | <p> | |
133 | floor(numeric_limits<T>::digits * 0.4) | |
134 | </p> | |
135 | </td> | |
136 | </tr> | |
137 | <tr> | |
138 | <td> | |
139 | <p> | |
140 | Schröder | |
141 | </p> | |
142 | </td> | |
143 | <td> | |
144 | <p> | |
145 | floor(numeric_limits<T>::digits * 0.4) | |
146 | </p> | |
147 | </td> | |
148 | </tr> | |
149 | </tbody> | |
150 | </table></div> | |
151 | <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> | |
152 | <li class="listitem"> | |
153 | The C++ Standard cube root function <a href="http://en.cppreference.com/w/cpp/numeric/math/cbrt" target="_top">std::cbrt</a> | |
154 | is only defined for built-in or fundamental types, so cannot be used | |
155 | with any User-Defined floating-point types like <a href="../../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>. | |
156 | This, and that the cube function is so impeccably-behaved, allows the | |
157 | implementer to use many tricks to achieve a fast computation. On some | |
158 | platforms,<code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">cbrt</span></code> appeared several times as quick | |
159 | 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>, | |
160 | 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> | |
161 | is noticeably faster. In general, the results are highly dependent | |
162 | on the code-generation / processor architecture selection compiler | |
163 | options used. One can assume that the standard library will have been | |
164 | compiled with options <span class="emphasis"><em>nearly</em></span> optimal for the platform | |
165 | it was installed on, where as the user has more choice over the options | |
166 | used for Boost.Math. Pick something too general/conservative and performance | |
167 | suffers, while selecting options that make use of the latest instruction | |
168 | set opcodes speed's things up noticeably. | |
169 | </li> | |
170 | <li class="listitem"> | |
171 | Two compilers in optimise mode were compared: GCC 4.9.1 using Netbeans | |
172 | IDS and Microsoft Visual Studio 2013 (Update 1) on the same hardware. | |
173 | The number of iterations seemed consistent, but the relative run-times | |
174 | surprisingly different. | |
175 | </li> | |
176 | <li class="listitem"> | |
177 | <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 | |
178 | user-defined floating-point type</em></span>, conveniently <a href="../../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a>. | |
179 | It too can take some advantage of the good-behaviour of the cube function, | |
180 | compared to the more general implementation in the nth root-finding | |
181 | examples. For example, it uses a polynomial approximation to generate | |
182 | a better guess than dividing the exponent by three, and can avoid the | |
183 | complex checks in <a class="link" href="../roots_deriv.html#math_toolkit.roots.roots_deriv.newton">Newton-Raphson | |
184 | iteration</a> required to prevent the search going wildly off-track. | |
185 | For a known precision, it may also be possible to fix the number of | |
186 | iterations, allowing inlining and loop unrolling. It also algebraically | |
187 | simplifies the Halley steps leading to a big reduction in the number | |
188 | of floating point operations required compared to a "black box" | |
189 | implementation that calculates the derivatives seperately and then | |
190 | combines them in the Halley code. Typically, it was found that computation | |
191 | using type <code class="computeroutput"><span class="keyword">double</span></code> took | |
192 | a few times longer when using the various root-finding algorithms directly | |
193 | rather than the hand coded/optimized <code class="computeroutput"><span class="identifier">cbrt</span></code> | |
194 | routine. | |
195 | </li> | |
196 | <li class="listitem"> | |
197 | The importance of getting a good guess can be seen by the iteration | |
198 | count for the multiprecision case: here we "cheat" a little | |
199 | and use the cube-root calculated to double precision as the initial | |
200 | guess. The limitation of this tactic is that the range of possible | |
201 | (exponent) values may be less than the multiprecision type. | |
202 | </li> | |
203 | <li class="listitem"> | |
204 | For <a href="http://en.cppreference.com/w/cpp/language/types" target="_top">fundamental | |
205 | types</a>, there was little to choose between the three derivative | |
206 | methods, but for <a href="../../../../../../../libs/multiprecision/doc/html/boost_multiprecision/tut/floats/cpp_bin_float.html" target="_top">cpp_bin_float</a>, | |
207 | <a class="link" href="../roots_deriv.html#math_toolkit.roots.roots_deriv.newton">Newton-Raphson | |
208 | iteration</a> was twice as fast. Note that the cube-root is an extreme | |
209 | test case as the cost of calling the functor is so cheap that the runtimes | |
210 | are largely dominated by the complexity of the iteration code. | |
211 | </li> | |
212 | <li class="listitem"> | |
213 | Compiling with optimisation halved computation times, and any differences | |
214 | between algorithms became nearly negligible. The optimisation speed-up | |
215 | of the <a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS | |
216 | Algorithm 748: enclosing zeros of continuous functions</a> was | |
217 | especially noticable. | |
218 | </li> | |
219 | <li class="listitem"> | |
220 | Using a multiprecision type like <code class="computeroutput"><span class="identifier">cpp_bin_float_50</span></code> | |
221 | for a precision of 50 decimal digits took a lot longer, as expected | |
222 | because most computation uses software rather than 64-bit floating-point | |
223 | hardware. Speeds are often more than 50 times slower. | |
224 | </li> | |
225 | <li class="listitem"> | |
226 | Using <code class="computeroutput"><span class="identifier">cpp_bin_float_50</span></code>, | |
227 | <a href="http://portal.acm.org/citation.cfm?id=210111" target="_top">TOMS Algorithm | |
228 | 748: enclosing zeros of continuous functions</a> was much slower | |
229 | showing the benefit of using derivatives. <a class="link" href="../roots_deriv.html#math_toolkit.roots.roots_deriv.newton">Newton-Raphson | |
230 | iteration</a> was found to be twice as quick as either of the second-derivative | |
231 | methods: this is an extreme case though, the function and its derivatives | |
232 | are so cheap to compute that we're really measuring the complexity | |
233 | of the boilerplate root-finding code. | |
234 | </li> | |
235 | <li class="listitem"> | |
236 | For multiprecision types only one or two extra <span class="emphasis"><em>iterations</em></span> | |
237 | are needed to get the remaining 35 digits, whatever the algorithm used. | |
238 | (The time taken was of course much greater for these types). | |
239 | </li> | |
240 | <li class="listitem"> | |
241 | Using a 100 decimal-digit type only doubled the time and required only | |
242 | a very few more iterations, so the cost of extra precision is mainly | |
243 | the underlying cost of computing more digits, not in the way the algorithm | |
244 | works. This confirms previous observations using <a href="http://www.shoup.net/ntl/" target="_top">NTL | |
245 | A Library for doing Number Theory</a> high-precision types. | |
246 | </li> | |
247 | </ul></div> | |
248 | <h6> | |
249 | <a name="math_toolkit.roots.root_comparison.cbrt_comparison.h0"></a> | |
250 | <span class="phrase"><a name="math_toolkit.roots.root_comparison.cbrt_comparison.program_root_finding_algorithms_"></a></span><a class="link" href="cbrt_comparison.html#math_toolkit.roots.root_comparison.cbrt_comparison.program_root_finding_algorithms_">Program | |
251 | root_finding_algorithms.cpp, Microsoft Visual C++ version 12.0, Dinkumware | |
252 | standard library version 610, Win32, x64<br> 1000000 evaluations of each | |
253 | of 5 root_finding algorithms.</a> | |
254 | </h6> | |
255 | <div class="table"> | |
256 | <a name="math_toolkit.roots.root_comparison.cbrt_comparison.cbrt_4"></a><p class="title"><b>Table 12.1. Cube root(28) for float, double, long double and cpp_bin_float_50</b></p> | |
257 | <div class="table-contents"><table class="table" summary="Cube root(28) for float, double, long double and cpp_bin_float_50"> | |
258 | <colgroup> | |
259 | <col> | |
260 | <col> | |
261 | <col> | |
262 | <col> | |
263 | <col> | |
264 | <col> | |
265 | <col> | |
266 | <col> | |
267 | <col> | |
268 | <col> | |
269 | <col> | |
270 | <col> | |
271 | <col> | |
272 | <col> | |
273 | <col> | |
274 | <col> | |
275 | <col> | |
276 | <col> | |
277 | <col> | |
278 | <col> | |
279 | <col> | |
280 | </colgroup> | |
281 | <thead><tr> | |
282 | <th> | |
283 | </th> | |
284 | <th> | |
285 | <p> | |
286 | float | |
287 | </p> | |
288 | </th> | |
289 | <th> | |
290 | </th> | |
291 | <th> | |
292 | </th> | |
293 | <th> | |
294 | </th> | |
295 | <th> | |
296 | </th> | |
297 | <th> | |
298 | <p> | |
299 | double | |
300 | </p> | |
301 | </th> | |
302 | <th> | |
303 | </th> | |
304 | <th> | |
305 | </th> | |
306 | <th> | |
307 | </th> | |
308 | <th> | |
309 | </th> | |
310 | <th> | |
311 | <p> | |
312 | long d | |
313 | </p> | |
314 | </th> | |
315 | <th> | |
316 | </th> | |
317 | <th> | |
318 | </th> | |
319 | <th> | |
320 | </th> | |
321 | <th> | |
322 | </th> | |
323 | <th> | |
324 | <p> | |
325 | cpp50 | |
326 | </p> | |
327 | </th> | |
328 | <th> | |
329 | </th> | |
330 | <th> | |
331 | </th> | |
332 | <td class="auto-generated"> </td> | |
333 | <td class="auto-generated"> </td> | |
334 | </tr></thead> | |
335 | <tbody> | |
336 | <tr> | |
337 | <td> | |
338 | <p> | |
339 | Algorithm | |
340 | </p> | |
341 | </td> | |
342 | <td> | |
343 | <p> | |
344 | Its | |
345 | </p> | |
346 | </td> | |
347 | <td> | |
348 | <p> | |
349 | Times | |
350 | </p> | |
351 | </td> | |
352 | <td> | |
353 | <p> | |
354 | Norm | |
355 | </p> | |
356 | </td> | |
357 | <td> | |
358 | <p> | |
359 | Dis | |
360 | </p> | |
361 | </td> | |
362 | <td> | |
363 | </td> | |
364 | <td> | |
365 | <p> | |
366 | Its | |
367 | </p> | |
368 | </td> | |
369 | <td> | |
370 | <p> | |
371 | Times | |
372 | </p> | |
373 | </td> | |
374 | <td> | |
375 | <p> | |
376 | Norm | |
377 | </p> | |
378 | </td> | |
379 | <td> | |
380 | <p> | |
381 | Dis | |
382 | </p> | |
383 | </td> | |
384 | <td> | |
385 | </td> | |
386 | <td> | |
387 | <p> | |
388 | Its | |
389 | </p> | |
390 | </td> | |
391 | <td> | |
392 | <p> | |
393 | Times | |
394 | </p> | |
395 | </td> | |
396 | <td> | |
397 | <p> | |
398 | Norm | |
399 | </p> | |
400 | </td> | |
401 | <td> | |
402 | <p> | |
403 | Dis | |
404 | </p> | |
405 | </td> | |
406 | <td> | |
407 | </td> | |
408 | <td> | |
409 | <p> | |
410 | Its | |
411 | </p> | |
412 | </td> | |
413 | <td> | |
414 | <p> | |
415 | Times | |
416 | </p> | |
417 | </td> | |
418 | <td> | |
419 | <p> | |
420 | Norm | |
421 | </p> | |
422 | </td> | |
423 | <td> | |
424 | <p> | |
425 | Dis | |
426 | </p> | |
427 | </td> | |
428 | <td> | |
429 | </td> | |
430 | </tr> | |
431 | <tr> | |
432 | <td> | |
433 | <p> | |
434 | cbrt | |
435 | </p> | |
436 | </td> | |
437 | <td> | |
438 | <p> | |
439 | 0 | |
440 | </p> | |
441 | </td> | |
442 | <td> | |
443 | <p> | |
444 | 46875 | |
445 | </p> | |
446 | </td> | |
447 | <td> | |
448 | <p> | |
449 | <span class="blue">1.0</span> | |
450 | </p> | |
451 | </td> | |
452 | <td> | |
453 | <p> | |
454 | 0 | |
455 | </p> | |
456 | </td> | |
457 | <td> | |
458 | </td> | |
459 | <td> | |
460 | <p> | |
461 | 0 | |
462 | </p> | |
463 | </td> | |
464 | <td> | |
465 | <p> | |
466 | 46875 | |
467 | </p> | |
468 | </td> | |
469 | <td> | |
470 | <p> | |
471 | <span class="blue">1.0</span> | |
472 | </p> | |
473 | </td> | |
474 | <td> | |
475 | <p> | |
476 | 1 | |
477 | </p> | |
478 | </td> | |
479 | <td> | |
480 | </td> | |
481 | <td> | |
482 | <p> | |
483 | 0 | |
484 | </p> | |
485 | </td> | |
486 | <td> | |
487 | <p> | |
488 | 46875 | |
489 | </p> | |
490 | </td> | |
491 | <td> | |
492 | <p> | |
493 | <span class="blue">1.0</span> | |
494 | </p> | |
495 | </td> | |
496 | <td> | |
497 | <p> | |
498 | 1 | |
499 | </p> | |
500 | </td> | |
501 | <td> | |
502 | </td> | |
503 | <td> | |
504 | <p> | |
505 | 0 | |
506 | </p> | |
507 | </td> | |
508 | <td> | |
509 | <p> | |
510 | 4906250 | |
511 | </p> | |
512 | </td> | |
513 | <td> | |
514 | <p> | |
515 | 1.1 | |
516 | </p> | |
517 | </td> | |
518 | <td> | |
519 | <p> | |
520 | 0 | |
521 | </p> | |
522 | </td> | |
523 | <td> | |
524 | </td> | |
525 | </tr> | |
526 | <tr> | |
527 | <td> | |
528 | <p> | |
529 | TOMS748 | |
530 | </p> | |
531 | </td> | |
532 | <td> | |
533 | <p> | |
534 | 8 | |
535 | </p> | |
536 | </td> | |
537 | <td> | |
538 | <p> | |
539 | 234375 | |
540 | </p> | |
541 | </td> | |
542 | <td> | |
543 | <p> | |
544 | <span class="red">5.0</span> | |
545 | </p> | |
546 | </td> | |
547 | <td> | |
548 | <p> | |
549 | -1 | |
550 | </p> | |
551 | </td> | |
552 | <td> | |
553 | </td> | |
554 | <td> | |
555 | <p> | |
556 | 11 | |
557 | </p> | |
558 | </td> | |
559 | <td> | |
560 | <p> | |
561 | 437500 | |
562 | </p> | |
563 | </td> | |
564 | <td> | |
565 | <p> | |
566 | <span class="red">9.3</span> | |
567 | </p> | |
568 | </td> | |
569 | <td> | |
570 | <p> | |
571 | 2 | |
572 | </p> | |
573 | </td> | |
574 | <td> | |
575 | </td> | |
576 | <td> | |
577 | <p> | |
578 | 11 | |
579 | </p> | |
580 | </td> | |
581 | <td> | |
582 | <p> | |
583 | 437500 | |
584 | </p> | |
585 | </td> | |
586 | <td> | |
587 | <p> | |
588 | <span class="red">9.3</span> | |
589 | </p> | |
590 | </td> | |
591 | <td> | |
592 | <p> | |
593 | 2 | |
594 | </p> | |
595 | </td> | |
596 | <td> | |
597 | </td> | |
598 | <td> | |
599 | <p> | |
600 | 7 | |
601 | </p> | |
602 | </td> | |
603 | <td> | |
604 | <p> | |
605 | 66218750 | |
606 | </p> | |
607 | </td> | |
608 | <td> | |
609 | <p> | |
610 | <span class="red">15.</span> | |
611 | </p> | |
612 | </td> | |
613 | <td> | |
614 | <p> | |
615 | -2 | |
616 | </p> | |
617 | </td> | |
618 | <td> | |
619 | </td> | |
620 | </tr> | |
621 | <tr> | |
622 | <td> | |
623 | <p> | |
624 | Newton | |
625 | </p> | |
626 | </td> | |
627 | <td> | |
628 | <p> | |
629 | 5 | |
630 | </p> | |
631 | </td> | |
632 | <td> | |
633 | <p> | |
634 | 109375 | |
635 | </p> | |
636 | </td> | |
637 | <td> | |
638 | <p> | |
639 | 2.3 | |
640 | </p> | |
641 | </td> | |
642 | <td> | |
643 | <p> | |
644 | 0 | |
645 | </p> | |
646 | </td> | |
647 | <td> | |
648 | </td> | |
649 | <td> | |
650 | <p> | |
651 | 6 | |
652 | </p> | |
653 | </td> | |
654 | <td> | |
655 | <p> | |
656 | 125000 | |
657 | </p> | |
658 | </td> | |
659 | <td> | |
660 | <p> | |
661 | 2.7 | |
662 | </p> | |
663 | </td> | |
664 | <td> | |
665 | <p> | |
666 | 0 | |
667 | </p> | |
668 | </td> | |
669 | <td> | |
670 | </td> | |
671 | <td> | |
672 | <p> | |
673 | 6 | |
674 | </p> | |
675 | </td> | |
676 | <td> | |
677 | <p> | |
678 | 140625 | |
679 | </p> | |
680 | </td> | |
681 | <td> | |
682 | <p> | |
683 | 3.0 | |
684 | </p> | |
685 | </td> | |
686 | <td> | |
687 | <p> | |
688 | 0 | |
689 | </p> | |
690 | </td> | |
691 | <td> | |
692 | </td> | |
693 | <td> | |
694 | <p> | |
695 | 2 | |
696 | </p> | |
697 | </td> | |
698 | <td> | |
699 | <p> | |
700 | 4531250 | |
701 | </p> | |
702 | </td> | |
703 | <td> | |
704 | <p> | |
705 | <span class="blue">1.0</span> | |
706 | </p> | |
707 | </td> | |
708 | <td> | |
709 | <p> | |
710 | 0 | |
711 | </p> | |
712 | </td> | |
713 | <td> | |
714 | </td> | |
715 | </tr> | |
716 | <tr> | |
717 | <td> | |
718 | <p> | |
719 | Halley | |
720 | </p> | |
721 | </td> | |
722 | <td> | |
723 | <p> | |
724 | 3 | |
725 | </p> | |
726 | </td> | |
727 | <td> | |
728 | <p> | |
729 | 125000 | |
730 | </p> | |
731 | </td> | |
732 | <td> | |
733 | <p> | |
734 | 2.7 | |
735 | </p> | |
736 | </td> | |
737 | <td> | |
738 | <p> | |
739 | 0 | |
740 | </p> | |
741 | </td> | |
742 | <td> | |
743 | </td> | |
744 | <td> | |
745 | <p> | |
746 | 4 | |
747 | </p> | |
748 | </td> | |
749 | <td> | |
750 | <p> | |
751 | 156250 | |
752 | </p> | |
753 | </td> | |
754 | <td> | |
755 | <p> | |
756 | 3.3 | |
757 | </p> | |
758 | </td> | |
759 | <td> | |
760 | <p> | |
761 | 0 | |
762 | </p> | |
763 | </td> | |
764 | <td> | |
765 | </td> | |
766 | <td> | |
767 | <p> | |
768 | 4 | |
769 | </p> | |
770 | </td> | |
771 | <td> | |
772 | <p> | |
773 | 156250 | |
774 | </p> | |
775 | </td> | |
776 | <td> | |
777 | <p> | |
778 | 3.3 | |
779 | </p> | |
780 | </td> | |
781 | <td> | |
782 | <p> | |
783 | 0 | |
784 | </p> | |
785 | </td> | |
786 | <td> | |
787 | </td> | |
788 | <td> | |
789 | <p> | |
790 | 2 | |
791 | </p> | |
792 | </td> | |
793 | <td> | |
794 | <p> | |
795 | 10625000 | |
796 | </p> | |
797 | </td> | |
798 | <td> | |
799 | <p> | |
800 | 2.3 | |
801 | </p> | |
802 | </td> | |
803 | <td> | |
804 | <p> | |
805 | 0 | |
806 | </p> | |
807 | </td> | |
808 | <td> | |
809 | </td> | |
810 | </tr> | |
811 | <tr> | |
812 | <td> | |
813 | <p> | |
814 | Schröder | |
815 | </p> | |
816 | </td> | |
817 | <td> | |
818 | <p> | |
819 | 4 | |
820 | </p> | |
821 | </td> | |
822 | <td> | |
823 | <p> | |
824 | 140625 | |
825 | </p> | |
826 | </td> | |
827 | <td> | |
828 | <p> | |
829 | 3.0 | |
830 | </p> | |
831 | </td> | |
832 | <td> | |
833 | <p> | |
834 | 0 | |
835 | </p> | |
836 | </td> | |
837 | <td> | |
838 | </td> | |
839 | <td> | |
840 | <p> | |
841 | 5 | |
842 | </p> | |
843 | </td> | |
844 | <td> | |
845 | <p> | |
846 | 187500 | |
847 | </p> | |
848 | </td> | |
849 | <td> | |
850 | <p> | |
851 | 4.0 | |
852 | </p> | |
853 | </td> | |
854 | <td> | |
855 | <p> | |
856 | 0 | |
857 | </p> | |
858 | </td> | |
859 | <td> | |
860 | </td> | |
861 | <td> | |
862 | <p> | |
863 | 5 | |
864 | </p> | |
865 | </td> | |
866 | <td> | |
867 | <p> | |
868 | 203125 | |
869 | </p> | |
870 | </td> | |
871 | <td> | |
872 | <p> | |
873 | <span class="red">4.3</span> | |
874 | </p> | |
875 | </td> | |
876 | <td> | |
877 | <p> | |
878 | 0 | |
879 | </p> | |
880 | </td> | |
881 | <td> | |
882 | </td> | |
883 | <td> | |
884 | <p> | |
885 | 2 | |
886 | </p> | |
887 | </td> | |
888 | <td> | |
889 | <p> | |
890 | 13109375 | |
891 | </p> | |
892 | </td> | |
893 | <td> | |
894 | <p> | |
895 | 2.9 | |
896 | </p> | |
897 | </td> | |
898 | <td> | |
899 | <p> | |
900 | 0 | |
901 | </p> | |
902 | </td> | |
903 | <td> | |
904 | </td> | |
905 | </tr> | |
906 | </tbody> | |
907 | </table></div> | |
908 | </div> | |
909 | <br class="table-break"><h6> | |
910 | <a name="math_toolkit.roots.root_comparison.cbrt_comparison.h1"></a> | |
911 | <span class="phrase"><a name="math_toolkit.roots.root_comparison.cbrt_comparison.program_root_finding_algorithms0"></a></span><a class="link" href="cbrt_comparison.html#math_toolkit.roots.root_comparison.cbrt_comparison.program_root_finding_algorithms0">Program | |
912 | root_finding_algorithms.cpp, GNU C++ version 4.9.2, GNU libstdc++ version | |
913 | 20141030, Win32, x64<br> 1000000 evaluations of each of 5 root_finding | |
914 | algorithms.</a> | |
915 | </h6> | |
916 | <div class="table"> | |
917 | <a name="math_toolkit.roots.root_comparison.cbrt_comparison.cbrt_4_0"></a><p class="title"><b>Table 12.2. Cube root(28) for float, double, long double and cpp_bin_float_50</b></p> | |
918 | <div class="table-contents"><table class="table" summary="Cube root(28) for float, double, long double and cpp_bin_float_50"> | |
919 | <colgroup> | |
920 | <col> | |
921 | <col> | |
922 | <col> | |
923 | <col> | |
924 | <col> | |
925 | <col> | |
926 | <col> | |
927 | <col> | |
928 | <col> | |
929 | <col> | |
930 | <col> | |
931 | <col> | |
932 | <col> | |
933 | <col> | |
934 | <col> | |
935 | <col> | |
936 | <col> | |
937 | <col> | |
938 | <col> | |
939 | <col> | |
940 | <col> | |
941 | </colgroup> | |
942 | <thead><tr> | |
943 | <th> | |
944 | </th> | |
945 | <th> | |
946 | <p> | |
947 | float | |
948 | </p> | |
949 | </th> | |
950 | <th> | |
951 | </th> | |
952 | <th> | |
953 | </th> | |
954 | <th> | |
955 | </th> | |
956 | <th> | |
957 | </th> | |
958 | <th> | |
959 | <p> | |
960 | double | |
961 | </p> | |
962 | </th> | |
963 | <th> | |
964 | </th> | |
965 | <th> | |
966 | </th> | |
967 | <th> | |
968 | </th> | |
969 | <th> | |
970 | </th> | |
971 | <th> | |
972 | <p> | |
973 | long d | |
974 | </p> | |
975 | </th> | |
976 | <th> | |
977 | </th> | |
978 | <th> | |
979 | </th> | |
980 | <th> | |
981 | </th> | |
982 | <th> | |
983 | </th> | |
984 | <th> | |
985 | <p> | |
986 | cpp50 | |
987 | </p> | |
988 | </th> | |
989 | <th> | |
990 | </th> | |
991 | <th> | |
992 | </th> | |
993 | <td class="auto-generated"> </td> | |
994 | <td class="auto-generated"> </td> | |
995 | </tr></thead> | |
996 | <tbody> | |
997 | <tr> | |
998 | <td> | |
999 | <p> | |
1000 | Algorithm | |
1001 | </p> | |
1002 | </td> | |
1003 | <td> | |
1004 | <p> | |
1005 | Its | |
1006 | </p> | |
1007 | </td> | |
1008 | <td> | |
1009 | <p> | |
1010 | Times | |
1011 | </p> | |
1012 | </td> | |
1013 | <td> | |
1014 | <p> | |
1015 | Norm | |
1016 | </p> | |
1017 | </td> | |
1018 | <td> | |
1019 | <p> | |
1020 | Dis | |
1021 | </p> | |
1022 | </td> | |
1023 | <td> | |
1024 | </td> | |
1025 | <td> | |
1026 | <p> | |
1027 | Its | |
1028 | </p> | |
1029 | </td> | |
1030 | <td> | |
1031 | <p> | |
1032 | Times | |
1033 | </p> | |
1034 | </td> | |
1035 | <td> | |
1036 | <p> | |
1037 | Norm | |
1038 | </p> | |
1039 | </td> | |
1040 | <td> | |
1041 | <p> | |
1042 | Dis | |
1043 | </p> | |
1044 | </td> | |
1045 | <td> | |
1046 | </td> | |
1047 | <td> | |
1048 | <p> | |
1049 | Its | |
1050 | </p> | |
1051 | </td> | |
1052 | <td> | |
1053 | <p> | |
1054 | Times | |
1055 | </p> | |
1056 | </td> | |
1057 | <td> | |
1058 | <p> | |
1059 | Norm | |
1060 | </p> | |
1061 | </td> | |
1062 | <td> | |
1063 | <p> | |
1064 | Dis | |
1065 | </p> | |
1066 | </td> | |
1067 | <td> | |
1068 | </td> | |
1069 | <td> | |
1070 | <p> | |
1071 | Its | |
1072 | </p> | |
1073 | </td> | |
1074 | <td> | |
1075 | <p> | |
1076 | Times | |
1077 | </p> | |
1078 | </td> | |
1079 | <td> | |
1080 | <p> | |
1081 | Norm | |
1082 | </p> | |
1083 | </td> | |
1084 | <td> | |
1085 | <p> | |
1086 | Dis | |
1087 | </p> | |
1088 | </td> | |
1089 | <td> | |
1090 | </td> | |
1091 | </tr> | |
1092 | <tr> | |
1093 | <td> | |
1094 | <p> | |
1095 | cbrt | |
1096 | </p> | |
1097 | </td> | |
1098 | <td> | |
1099 | <p> | |
1100 | 0 | |
1101 | </p> | |
1102 | </td> | |
1103 | <td> | |
1104 | <p> | |
1105 | 46875 | |
1106 | </p> | |
1107 | </td> | |
1108 | <td> | |
1109 | <p> | |
1110 | <span class="blue">1.0</span> | |
1111 | </p> | |
1112 | </td> | |
1113 | <td> | |
1114 | <p> | |
1115 | 0 | |
1116 | </p> | |
1117 | </td> | |
1118 | <td> | |
1119 | </td> | |
1120 | <td> | |
1121 | <p> | |
1122 | 0 | |
1123 | </p> | |
1124 | </td> | |
1125 | <td> | |
1126 | <p> | |
1127 | 46875 | |
1128 | </p> | |
1129 | </td> | |
1130 | <td> | |
1131 | <p> | |
1132 | <span class="blue">1.0</span> | |
1133 | </p> | |
1134 | </td> | |
1135 | <td> | |
1136 | <p> | |
1137 | 0 | |
1138 | </p> | |
1139 | </td> | |
1140 | <td> | |
1141 | </td> | |
1142 | <td> | |
1143 | <p> | |
1144 | 0 | |
1145 | </p> | |
1146 | </td> | |
1147 | <td> | |
1148 | <p> | |
1149 | 46875 | |
1150 | </p> | |
1151 | </td> | |
1152 | <td> | |
1153 | <p> | |
1154 | <span class="blue">1.0</span> | |
1155 | </p> | |
1156 | </td> | |
1157 | <td> | |
1158 | <p> | |
1159 | 0 | |
1160 | </p> | |
1161 | </td> | |
1162 | <td> | |
1163 | </td> | |
1164 | <td> | |
1165 | <p> | |
1166 | 0 | |
1167 | </p> | |
1168 | </td> | |
1169 | <td> | |
1170 | <p> | |
1171 | 3500000 | |
1172 | </p> | |
1173 | </td> | |
1174 | <td> | |
1175 | <p> | |
1176 | 1.1 | |
1177 | </p> | |
1178 | </td> | |
1179 | <td> | |
1180 | <p> | |
1181 | 0 | |
1182 | </p> | |
1183 | </td> | |
1184 | <td> | |
1185 | </td> | |
1186 | </tr> | |
1187 | <tr> | |
1188 | <td> | |
1189 | <p> | |
1190 | TOMS748 | |
1191 | </p> | |
1192 | </td> | |
1193 | <td> | |
1194 | <p> | |
1195 | 8 | |
1196 | </p> | |
1197 | </td> | |
1198 | <td> | |
1199 | <p> | |
1200 | 187500 | |
1201 | </p> | |
1202 | </td> | |
1203 | <td> | |
1204 | <p> | |
1205 | 4.0 | |
1206 | </p> | |
1207 | </td> | |
1208 | <td> | |
1209 | <p> | |
1210 | -1 | |
1211 | </p> | |
1212 | </td> | |
1213 | <td> | |
1214 | </td> | |
1215 | <td> | |
1216 | <p> | |
1217 | 11 | |
1218 | </p> | |
1219 | </td> | |
1220 | <td> | |
1221 | <p> | |
1222 | 406250 | |
1223 | </p> | |
1224 | </td> | |
1225 | <td> | |
1226 | <p> | |
1227 | <span class="red">8.7</span> | |
1228 | </p> | |
1229 | </td> | |
1230 | <td> | |
1231 | <p> | |
1232 | 2 | |
1233 | </p> | |
1234 | </td> | |
1235 | <td> | |
1236 | </td> | |
1237 | <td> | |
1238 | <p> | |
1239 | 10 | |
1240 | </p> | |
1241 | </td> | |
1242 | <td> | |
1243 | <p> | |
1244 | 609375 | |
1245 | </p> | |
1246 | </td> | |
1247 | <td> | |
1248 | <p> | |
1249 | <span class="red">13.</span> | |
1250 | </p> | |
1251 | </td> | |
1252 | <td> | |
1253 | <p> | |
1254 | -1 | |
1255 | </p> | |
1256 | </td> | |
1257 | <td> | |
1258 | </td> | |
1259 | <td> | |
1260 | <p> | |
1261 | 7 | |
1262 | </p> | |
1263 | </td> | |
1264 | <td> | |
1265 | <p> | |
1266 | 44531250 | |
1267 | </p> | |
1268 | </td> | |
1269 | <td> | |
1270 | <p> | |
1271 | <span class="red">14.</span> | |
1272 | </p> | |
1273 | </td> | |
1274 | <td> | |
1275 | <p> | |
1276 | -2 | |
1277 | </p> | |
1278 | </td> | |
1279 | <td> | |
1280 | </td> | |
1281 | </tr> | |
1282 | <tr> | |
1283 | <td> | |
1284 | <p> | |
1285 | Newton | |
1286 | </p> | |
1287 | </td> | |
1288 | <td> | |
1289 | <p> | |
1290 | 5 | |
1291 | </p> | |
1292 | </td> | |
1293 | <td> | |
1294 | <p> | |
1295 | 93750 | |
1296 | </p> | |
1297 | </td> | |
1298 | <td> | |
1299 | <p> | |
1300 | 2.0 | |
1301 | </p> | |
1302 | </td> | |
1303 | <td> | |
1304 | <p> | |
1305 | 0 | |
1306 | </p> | |
1307 | </td> | |
1308 | <td> | |
1309 | </td> | |
1310 | <td> | |
1311 | <p> | |
1312 | 6 | |
1313 | </p> | |
1314 | </td> | |
1315 | <td> | |
1316 | <p> | |
1317 | 109375 | |
1318 | </p> | |
1319 | </td> | |
1320 | <td> | |
1321 | <p> | |
1322 | 2.3 | |
1323 | </p> | |
1324 | </td> | |
1325 | <td> | |
1326 | <p> | |
1327 | 0 | |
1328 | </p> | |
1329 | </td> | |
1330 | <td> | |
1331 | </td> | |
1332 | <td> | |
1333 | <p> | |
1334 | 6 | |
1335 | </p> | |
1336 | </td> | |
1337 | <td> | |
1338 | <p> | |
1339 | 171875 | |
1340 | </p> | |
1341 | </td> | |
1342 | <td> | |
1343 | <p> | |
1344 | 3.7 | |
1345 | </p> | |
1346 | </td> | |
1347 | <td> | |
1348 | <p> | |
1349 | 0 | |
1350 | </p> | |
1351 | </td> | |
1352 | <td> | |
1353 | </td> | |
1354 | <td> | |
1355 | <p> | |
1356 | 2 | |
1357 | </p> | |
1358 | </td> | |
1359 | <td> | |
1360 | <p> | |
1361 | 3140625 | |
1362 | </p> | |
1363 | </td> | |
1364 | <td> | |
1365 | <p> | |
1366 | <span class="blue">1.0</span> | |
1367 | </p> | |
1368 | </td> | |
1369 | <td> | |
1370 | <p> | |
1371 | -1 | |
1372 | </p> | |
1373 | </td> | |
1374 | <td> | |
1375 | </td> | |
1376 | </tr> | |
1377 | <tr> | |
1378 | <td> | |
1379 | <p> | |
1380 | Halley | |
1381 | </p> | |
1382 | </td> | |
1383 | <td> | |
1384 | <p> | |
1385 | 3 | |
1386 | </p> | |
1387 | </td> | |
1388 | <td> | |
1389 | <p> | |
1390 | 93750 | |
1391 | </p> | |
1392 | </td> | |
1393 | <td> | |
1394 | <p> | |
1395 | 2.0 | |
1396 | </p> | |
1397 | </td> | |
1398 | <td> | |
1399 | <p> | |
1400 | 0 | |
1401 | </p> | |
1402 | </td> | |
1403 | <td> | |
1404 | </td> | |
1405 | <td> | |
1406 | <p> | |
1407 | 4 | |
1408 | </p> | |
1409 | </td> | |
1410 | <td> | |
1411 | <p> | |
1412 | 125000 | |
1413 | </p> | |
1414 | </td> | |
1415 | <td> | |
1416 | <p> | |
1417 | 2.7 | |
1418 | </p> | |
1419 | </td> | |
1420 | <td> | |
1421 | <p> | |
1422 | 0 | |
1423 | </p> | |
1424 | </td> | |
1425 | <td> | |
1426 | </td> | |
1427 | <td> | |
1428 | <p> | |
1429 | 4 | |
1430 | </p> | |
1431 | </td> | |
1432 | <td> | |
1433 | <p> | |
1434 | 218750 | |
1435 | </p> | |
1436 | </td> | |
1437 | <td> | |
1438 | <p> | |
1439 | <span class="red">4.7</span> | |
1440 | </p> | |
1441 | </td> | |
1442 | <td> | |
1443 | <p> | |
1444 | 0 | |
1445 | </p> | |
1446 | </td> | |
1447 | <td> | |
1448 | </td> | |
1449 | <td> | |
1450 | <p> | |
1451 | 2 | |
1452 | </p> | |
1453 | </td> | |
1454 | <td> | |
1455 | <p> | |
1456 | 7171875 | |
1457 | </p> | |
1458 | </td> | |
1459 | <td> | |
1460 | <p> | |
1461 | 2.3 | |
1462 | </p> | |
1463 | </td> | |
1464 | <td> | |
1465 | <p> | |
1466 | 0 | |
1467 | </p> | |
1468 | </td> | |
1469 | <td> | |
1470 | </td> | |
1471 | </tr> | |
1472 | <tr> | |
1473 | <td> | |
1474 | <p> | |
1475 | Schröder | |
1476 | </p> | |
1477 | </td> | |
1478 | <td> | |
1479 | <p> | |
1480 | 4 | |
1481 | </p> | |
1482 | </td> | |
1483 | <td> | |
1484 | <p> | |
1485 | 109375 | |
1486 | </p> | |
1487 | </td> | |
1488 | <td> | |
1489 | <p> | |
1490 | 2.3 | |
1491 | </p> | |
1492 | </td> | |
1493 | <td> | |
1494 | <p> | |
1495 | 0 | |
1496 | </p> | |
1497 | </td> | |
1498 | <td> | |
1499 | </td> | |
1500 | <td> | |
1501 | <p> | |
1502 | 5 | |
1503 | </p> | |
1504 | </td> | |
1505 | <td> | |
1506 | <p> | |
1507 | 171875 | |
1508 | </p> | |
1509 | </td> | |
1510 | <td> | |
1511 | <p> | |
1512 | 3.7 | |
1513 | </p> | |
1514 | </td> | |
1515 | <td> | |
1516 | <p> | |
1517 | 0 | |
1518 | </p> | |
1519 | </td> | |
1520 | <td> | |
1521 | </td> | |
1522 | <td> | |
1523 | <p> | |
1524 | 5 | |
1525 | </p> | |
1526 | </td> | |
1527 | <td> | |
1528 | <p> | |
1529 | 281250 | |
1530 | </p> | |
1531 | </td> | |
1532 | <td> | |
1533 | <p> | |
1534 | <span class="red">6.0</span> | |
1535 | </p> | |
1536 | </td> | |
1537 | <td> | |
1538 | <p> | |
1539 | 0 | |
1540 | </p> | |
1541 | </td> | |
1542 | <td> | |
1543 | </td> | |
1544 | <td> | |
1545 | <p> | |
1546 | 2 | |
1547 | </p> | |
1548 | </td> | |
1549 | <td> | |
1550 | <p> | |
1551 | 8703125 | |
1552 | </p> | |
1553 | </td> | |
1554 | <td> | |
1555 | <p> | |
1556 | 2.8 | |
1557 | </p> | |
1558 | </td> | |
1559 | <td> | |
1560 | <p> | |
1561 | 0 | |
1562 | </p> | |
1563 | </td> | |
1564 | <td> | |
1565 | </td> | |
1566 | </tr> | |
1567 | </tbody> | |
1568 | </table></div> | |
1569 | </div> | |
1570 | <br class="table-break"> | |
1571 | </div> | |
1572 | <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> | |
1573 | <td align="left"></td> | |
1574 | <td align="right"><div class="copyright-footer">Copyright © 2006-2010, 2012-2014 Nikhar Agrawal, | |
1575 | Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert | |
1576 | Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Johan Råde, Gautam Sewani, | |
1577 | Benjamin Sobotta, Thijs van den Berg, Daryle Walker and Xiaogang Zhang<p> | |
1578 | Distributed under the Boost Software License, Version 1.0. (See accompanying | |
1579 | 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>) | |
1580 | </p> | |
1581 | </div></td> | |
1582 | </tr></table> | |
1583 | <hr> | |
1584 | <div class="spirit-nav"> | |
1585 | <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> | |
1586 | </div> | |
1587 | </body> | |
1588 | </html> |