libs/math/doc/html/math_toolkit/root_comparison/cbrt_comparison.html

   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.79.1">
   7 <link rel="home" href="../../index.html" title="Math Toolkit 2.11.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 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&lt;T&gt;::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&lt;T&gt;::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&lt;T&gt;::digits * 0.4)
 134                 </p>
 135               </td>
 136 </tr>
 137 <tr>
 138 <td>
 139                 <p>
 140                   Schr&#246;der
 141                 </p>
 142               </td>
 143 <td>
 144                 <p>
 145                   floor(numeric_limits&lt;T&gt;::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 seperately 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             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 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&#160;10.1.&#160;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">&#160;</td>
 333 <td class="auto-generated">&#160;</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&#246;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&#160;10.2.&#160;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">&#160;</td>
 994 <td class="auto-generated">&#160;</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&#246;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 &#169; 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&#229;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>