1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.1"> 7<link rel="home" href="../../index.html" title="Math Toolkit 2.12.0"> 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><h3 class="title"> 27<a name="math_toolkit.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</h3></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 (built-in) 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 the 48 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 for 68 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 and 74 the CPU times were judged from repeat runs to have an uncertainty of 10 %. 75 Comparing MSVC for <code class="computeroutput"><span class="keyword">double</span></code> and 76 <code class="computeroutput"><span class="keyword">long</span> <span class="keyword">double</span></code> 77 (which are identical on this platform) 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 on 162 the code-generation / processor architecture selection compiler options 163 used. One can assume that the standard library will have been compiled 164 with options <span class="emphasis"><em>nearly</em></span> optimal for the platform it 165 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 examples. 181 For example, it uses a polynomial approximation to generate a better 182 guess than dividing the exponent by three, and can avoid the complex 183 checks in <a class="link" href="../roots_deriv.html#math_toolkit.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 iterations, 186 allowing inlining and loop unrolling. It also algebraically simplifies 187 the Halley steps leading to a big reduction in the number of floating 188 point operations required compared to a "black box" implementation 189 that calculates the derivatives separately and then combines them in 190 the Halley code. Typically, it was found that computation using type 191 <code class="computeroutput"><span class="keyword">double</span></code> took a few times 192 longer when using the various root-finding algorithms directly rather 193 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 count 198 for the multiprecision case: here we "cheat" a little and use 199 the cube-root calculated to double precision as the initial guess. The 200 limitation of this tactic is that the range of possible (exponent) values 201 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 (built-in) types</a>, there was little to choose between the three 206 derivative 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_deriv.newton">Newton-Raphson iteration</a> 208 was twice as fast. Note that the cube-root is an extreme test case as 209 the cost of calling the functor is so cheap that the runtimes are largely 210 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 especially 217 noticeable. 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 because 222 most computation uses software rather than 64-bit floating-point hardware. 223 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_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 of 233 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.root_comparison.cbrt_comparison.h0"></a> 250 <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 251 root_finding_algorithms.cpp, Microsoft Visual C++ version 14.1, Dinkumware 252 standard library version 650, Win32, x86<br> 1000000 evaluations of each 253 of 5 root_finding algorithms.</a> 254 </h6> 255<div class="table"> 256<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> 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 78125 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 62500 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 93750 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 11890625 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 468750 540 </p> 541 </td> 542<td> 543 <p> 544 <span class="red">6.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 906250 562 </p> 563 </td> 564<td> 565 <p> 566 <span class="red">15.</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 906250 584 </p> 585 </td> 586<td> 587 <p> 588 <span class="red">9.7</span> 589 </p> 590 </td> 591<td> 592 <p> 593 2 594 </p> 595 </td> 596<td> 597 </td> 598<td> 599 <p> 600 6 601 </p> 602 </td> 603<td> 604 <p> 605 80859375 606 </p> 607 </td> 608<td> 609 <p> 610 <span class="red">7.6</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 203125 635 </p> 636 </td> 637<td> 638 <p> 639 2.6 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 234375 657 </p> 658 </td> 659<td> 660 <p> 661 3.8 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 187500 679 </p> 680 </td> 681<td> 682 <p> 683 2.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 10640625 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 234375 730 </p> 731 </td> 732<td> 733 <p> 734 3.0 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 265625 752 </p> 753 </td> 754<td> 755 <p> 756 <span class="red">4.3</span> 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 234375 774 </p> 775 </td> 776<td> 777 <p> 778 2.5 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 26250000 796 </p> 797 </td> 798<td> 799 <p> 800 2.5 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 296875 825 </p> 826 </td> 827<td> 828 <p> 829 3.8 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 281250 847 </p> 848 </td> 849<td> 850 <p> 851 <span class="red">4.5</span> 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 234375 869 </p> 870 </td> 871<td> 872 <p> 873 2.5 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 32437500 891 </p> 892 </td> 893<td> 894 <p> 895 3.0 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.root_comparison.cbrt_comparison.h1"></a> 911 <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 912 root_finding_algorithms.cpp, GNU C++ version 8.2.0, GNU libstdc++ version 913 20180728, linux, x64<br> 1000000 evaluations of each of 5 root_finding 914 algorithms.</a> 915 </h6> 916<div class="table"> 917<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> 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 30000 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 60000 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 70000 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 4440000 1172 </p> 1173 </td> 1174<td> 1175 <p> 1176 <span class="blue">1.0</span> 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 220000 1201 </p> 1202 </td> 1203<td> 1204 <p> 1205 <span class="red">7.3</span> 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 370000 1223 </p> 1224 </td> 1225<td> 1226 <p> 1227 <span class="red">6.2</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 580000 1245 </p> 1246 </td> 1247<td> 1248 <p> 1249 <span class="red">8.3</span> 1250 </p> 1251 </td> 1252<td> 1253 <p> 1254 -1 1255 </p> 1256 </td> 1257<td> 1258 </td> 1259<td> 1260 <p> 1261 6 1262 </p> 1263 </td> 1264<td> 1265 <p> 1266 28360000 1267 </p> 1268 </td> 1269<td> 1270 <p> 1271 <span class="red">6.7</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 120000 1296 </p> 1297 </td> 1298<td> 1299 <p> 1300 4.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 130000 1318 </p> 1319 </td> 1320<td> 1321 <p> 1322 2.2 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 180000 1340 </p> 1341 </td> 1342<td> 1343 <p> 1344 2.6 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 4260000 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 110000 1391 </p> 1392 </td> 1393<td> 1394 <p> 1395 3.7 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 140000 1413 </p> 1414 </td> 1415<td> 1416 <p> 1417 2.3 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 230000 1435 </p> 1436 </td> 1437<td> 1438 <p> 1439 3.3 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 9210000 1457 </p> 1458 </td> 1459<td> 1460 <p> 1461 2.2 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 120000 1486 </p> 1487 </td> 1488<td> 1489 <p> 1490 4.0 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 140000 1508 </p> 1509 </td> 1510<td> 1511 <p> 1512 2.3 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 280000 1530 </p> 1531 </td> 1532<td> 1533 <p> 1534 4.0 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 11630000 1552 </p> 1553 </td> 1554<td> 1555 <p> 1556 2.7 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-2019 Nikhar 1575 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 1576 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 1577 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 1578 Daryle Walker and Xiaogang Zhang<p> 1579 Distributed under the Boost Software License, Version 1.0. (See accompanying 1580 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>) 1581 </p> 1582</div></td> 1583</tr></table> 1584<hr> 1585<div class="spirit-nav"> 1586<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> 1587</div> 1588</body> 1589</html> 1590
