ceph/src/boost/libs/math/doc/html/math_toolkit/roots/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.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&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
 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&#160;12.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                     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&#246;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&#160;12.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                     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&#246;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 &#169; 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&#229;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>