1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Comparison of Elliptic Integral Root Finding Algorithms</title> 5<link rel="stylesheet" href="../../math.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../index.html" title="Math Toolkit 2.12.0"> 8<link rel="up" href="../root_comparison.html" title="Comparison of Root Finding Algorithms"> 9<link rel="prev" href="root_n_comparison.html" title="Comparison of Nth-root Finding Algorithms"> 10<link rel="next" href="../../poly.html" title="Chapter 11. Polynomials and Rational Functions"> 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_n_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="../../poly.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.elliptic_comparison"></a><a class="link" href="elliptic_comparison.html" title="Comparison of Elliptic Integral Root Finding Algorithms">Comparison 28 of Elliptic Integral Root Finding Algorithms</a> 29</h3></div></div></div> 30<p> 31 A second example compares four root finding algorithms for locating the second 32 radius of an ellipse with first radius 28 and arc length 300, for four floating-point 33 types, <code class="computeroutput"><span class="keyword">float</span></code>, <code class="computeroutput"><span class="keyword">double</span></code>, <code class="computeroutput"><span class="keyword">long</span> 34 <span class="keyword">double</span></code> and a <a href="../../../../../../libs/multiprecision/doc/html/index.html" target="_top">Boost.Multiprecision</a> 35 type <code class="computeroutput"><span class="identifier">cpp_bin_float_50</span></code>. 36 </p> 37<p> 38 Which is to say we're solving: 39 </p> 40<pre class="programlisting">4xE(sqrt(1 - 28<sup>2</sup> / x<sup>2</sup>)) - 300 = 0</pre> 41<p> 42 In each case the target accuracy was set using our "recommended" 43 accuracy limits (or at least limits that make a good starting point - which 44 is likely to give close to full accuracy without resorting to unnecessary 45 iterations). 46 </p> 47<div class="informaltable"><table class="table"> 48<colgroup> 49<col> 50<col> 51</colgroup> 52<thead><tr> 53<th> 54 <p> 55 Function 56 </p> 57 </th> 58<th> 59 <p> 60 Precision Requested 61 </p> 62 </th> 63</tr></thead> 64<tbody> 65<tr> 66<td> 67 <p> 68 TOMS748 69 </p> 70 </td> 71<td> 72 <p> 73 numeric_limits<T>::digits - 2 74 </p> 75 </td> 76</tr> 77<tr> 78<td> 79 <p> 80 Newton 81 </p> 82 </td> 83<td> 84 <p> 85 floor(numeric_limits<T>::digits * 0.6) 86 </p> 87 </td> 88</tr> 89<tr> 90<td> 91 <p> 92 Halley 93 </p> 94 </td> 95<td> 96 <p> 97 floor(numeric_limits<T>::digits * 0.4) 98 </p> 99 </td> 100</tr> 101<tr> 102<td> 103 <p> 104 Schröder 105 </p> 106 </td> 107<td> 108 <p> 109 floor(numeric_limits<T>::digits * 0.4) 110 </p> 111 </td> 112</tr> 113</tbody> 114</table></div> 115<p> 116 Tests used Microsoft Visual Studio 2013 (Update 1) and GCC 4.9.1 using source 117 code <a href="../../../../example/root_elliptic_finding.cpp" target="_top">root_elliptic_finding.cpp</a>. 118 </p> 119<p> 120 The timing uncertainty (especially using MSVC) is at least 5% of normalized 121 time 'Norm'. 122 </p> 123<p> 124 To pick out the 'best' and 'worst' algorithms are highlighted in blue and 125 red. More than one result can be 'best' when normalized times are indistinguishable 126 within the uncertainty. 127 </p> 128<h4> 129<a name="math_toolkit.root_comparison.elliptic_comparison.h0"></a> 130 <span class="phrase"><a name="math_toolkit.root_comparison.elliptic_comparison.program_example_root_elliptic_fi"></a></span><a class="link" href="elliptic_comparison.html#math_toolkit.root_comparison.elliptic_comparison.program_example_root_elliptic_fi">Program 131 root_elliptic_finding.cpp, 132 Microsoft Visual C++ version 14.1, Dinkumware standard library version 650, 133 Win32 Compiled in optimise mode., _X86_SSE2</a> 134 </h4> 135<div class="table"> 136<a name="math_toolkit.root_comparison.elliptic_comparison.elliptic"></a><p class="title"><b>Table 10.12. root with radius 28 and arc length 300) for float, double, long double 137 and cpp_bin_float_50 types, using _X86_SSE2</b></p> 138<div class="table-contents"><table class="table" summary="root with radius 28 and arc length 300) for float, double, long double 139 and cpp_bin_float_50 types, using _X86_SSE2"> 140<colgroup> 141<col> 142<col> 143<col> 144<col> 145<col> 146<col> 147<col> 148<col> 149<col> 150<col> 151<col> 152<col> 153<col> 154<col> 155<col> 156<col> 157<col> 158<col> 159<col> 160<col> 161<col> 162</colgroup> 163<thead><tr> 164<th> 165 </th> 166<th> 167 <p> 168 float 169 </p> 170 </th> 171<th> 172 </th> 173<th> 174 </th> 175<th> 176 </th> 177<th> 178 </th> 179<th> 180 <p> 181 double 182 </p> 183 </th> 184<th> 185 </th> 186<th> 187 </th> 188<th> 189 </th> 190<th> 191 </th> 192<th> 193 <p> 194 long d 195 </p> 196 </th> 197<th> 198 </th> 199<th> 200 </th> 201<th> 202 </th> 203<th> 204 </th> 205<th> 206 <p> 207 cpp50 208 </p> 209 </th> 210<th> 211 </th> 212<th> 213 </th> 214<td class="auto-generated"> </td> 215<td class="auto-generated"> </td> 216</tr></thead> 217<tbody> 218<tr> 219<td> 220 <p> 221 Algo 222 </p> 223 </td> 224<td> 225 <p> 226 Its 227 </p> 228 </td> 229<td> 230 <p> 231 Times 232 </p> 233 </td> 234<td> 235 <p> 236 Norm 237 </p> 238 </td> 239<td> 240 <p> 241 Dis 242 </p> 243 </td> 244<td> 245 </td> 246<td> 247 <p> 248 Its 249 </p> 250 </td> 251<td> 252 <p> 253 Times 254 </p> 255 </td> 256<td> 257 <p> 258 Norm 259 </p> 260 </td> 261<td> 262 <p> 263 Dis 264 </p> 265 </td> 266<td> 267 </td> 268<td> 269 <p> 270 Its 271 </p> 272 </td> 273<td> 274 <p> 275 Times 276 </p> 277 </td> 278<td> 279 <p> 280 Norm 281 </p> 282 </td> 283<td> 284 <p> 285 Dis 286 </p> 287 </td> 288<td> 289 </td> 290<td> 291 <p> 292 Its 293 </p> 294 </td> 295<td> 296 <p> 297 Times 298 </p> 299 </td> 300<td> 301 <p> 302 Norm 303 </p> 304 </td> 305<td> 306 <p> 307 Dis 308 </p> 309 </td> 310<td> 311 </td> 312</tr> 313<tr> 314<td> 315 <p> 316 TOMS748 317 </p> 318 </td> 319<td> 320 <p> 321 6 322 </p> 323 </td> 324<td> 325 <p> 326 906 327 </p> 328 </td> 329<td> 330 <p> 331 2.07 332 </p> 333 </td> 334<td> 335 <p> 336 0 337 </p> 338 </td> 339<td> 340 </td> 341<td> 342 <p> 343 9 344 </p> 345 </td> 346<td> 347 <p> 348 1312 349 </p> 350 </td> 351<td> 352 <p> 353 1.79 354 </p> 355 </td> 356<td> 357 <p> 358 1 359 </p> 360 </td> 361<td> 362 </td> 363<td> 364 <p> 365 9 366 </p> 367 </td> 368<td> 369 <p> 370 1281 371 </p> 372 </td> 373<td> 374 <p> 375 1.75 376 </p> 377 </td> 378<td> 379 <p> 380 1 381 </p> 382 </td> 383<td> 384 </td> 385<td> 386 <p> 387 11 388 </p> 389 </td> 390<td> 391 <p> 392 1690625 393 </p> 394 </td> 395<td> 396 <p> 397 1.52 398 </p> 399 </td> 400<td> 401 <p> 402 -3 403 </p> 404 </td> 405<td> 406 </td> 407</tr> 408<tr> 409<td> 410 <p> 411 Newton 412 </p> 413 </td> 414<td> 415 <p> 416 3 417 </p> 418 </td> 419<td> 420 <p> 421 640 422 </p> 423 </td> 424<td> 425 <p> 426 1.46 427 </p> 428 </td> 429<td> 430 <p> 431 -1 432 </p> 433 </td> 434<td> 435 </td> 436<td> 437 <p> 438 4 439 </p> 440 </td> 441<td> 442 <p> 443 875 444 </p> 445 </td> 446<td> 447 <p> 448 1.19 449 </p> 450 </td> 451<td> 452 <p> 453 1 454 </p> 455 </td> 456<td> 457 </td> 458<td> 459 <p> 460 4 461 </p> 462 </td> 463<td> 464 <p> 465 843 466 </p> 467 </td> 468<td> 469 <p> 470 1.15 471 </p> 472 </td> 473<td> 474 <p> 475 1 476 </p> 477 </td> 478<td> 479 </td> 480<td> 481 <p> 482 5 483 </p> 484 </td> 485<td> 486 <p> 487 1368750 488 </p> 489 </td> 490<td> 491 <p> 492 1.23 493 </p> 494 </td> 495<td> 496 <p> 497 0 498 </p> 499 </td> 500<td> 501 </td> 502</tr> 503<tr> 504<td> 505 <p> 506 Halley 507 </p> 508 </td> 509<td> 510 <p> 511 2 512 </p> 513 </td> 514<td> 515 <p> 516 437 517 </p> 518 </td> 519<td> 520 <p> 521 <span class="blue">1.00</span> 522 </p> 523 </td> 524<td> 525 <p> 526 0 527 </p> 528 </td> 529<td> 530 </td> 531<td> 532 <p> 533 3 534 </p> 535 </td> 536<td> 537 <p> 538 734 539 </p> 540 </td> 541<td> 542 <p> 543 <span class="blue">1.00</span> 544 </p> 545 </td> 546<td> 547 <p> 548 3 549 </p> 550 </td> 551<td> 552 </td> 553<td> 554 <p> 555 3 556 </p> 557 </td> 558<td> 559 <p> 560 734 561 </p> 562 </td> 563<td> 564 <p> 565 <span class="blue">1.00</span> 566 </p> 567 </td> 568<td> 569 <p> 570 3 571 </p> 572 </td> 573<td> 574 </td> 575<td> 576 <p> 577 4 578 </p> 579 </td> 580<td> 581 <p> 582 1109375 583 </p> 584 </td> 585<td> 586 <p> 587 <span class="blue">1.00</span> 588 </p> 589 </td> 590<td> 591 <p> 592 0 593 </p> 594 </td> 595<td> 596 </td> 597</tr> 598<tr> 599<td> 600 <p> 601 Schröder 602 </p> 603 </td> 604<td> 605 <p> 606 3 607 </p> 608 </td> 609<td> 610 <p> 611 671 612 </p> 613 </td> 614<td> 615 <p> 616 1.54 617 </p> 618 </td> 619<td> 620 <p> 621 -1 622 </p> 623 </td> 624<td> 625 </td> 626<td> 627 <p> 628 6 629 </p> 630 </td> 631<td> 632 <p> 633 1296 634 </p> 635 </td> 636<td> 637 <p> 638 1.77 639 </p> 640 </td> 641<td> 642 <p> 643 1 644 </p> 645 </td> 646<td> 647 </td> 648<td> 649 <p> 650 6 651 </p> 652 </td> 653<td> 654 <p> 655 1406 656 </p> 657 </td> 658<td> 659 <p> 660 1.92 661 </p> 662 </td> 663<td> 664 <p> 665 1 666 </p> 667 </td> 668<td> 669 </td> 670<td> 671 <p> 672 5 673 </p> 674 </td> 675<td> 676 <p> 677 1462500 678 </p> 679 </td> 680<td> 681 <p> 682 1.32 683 </p> 684 </td> 685<td> 686 <p> 687 -2 688 </p> 689 </td> 690<td> 691 </td> 692</tr> 693</tbody> 694</table></div> 695</div> 696<br class="table-break"><h4> 697<a name="math_toolkit.root_comparison.elliptic_comparison.h1"></a> 698 <span class="phrase"><a name="math_toolkit.root_comparison.elliptic_comparison.program_example_root_elliptic_f0"></a></span><a class="link" href="elliptic_comparison.html#math_toolkit.root_comparison.elliptic_comparison.program_example_root_elliptic_f0">Program 699 root_elliptic_finding.cpp, 700 Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, 701 Win32 Compiled in optimise mode., _X64_AVX</a> 702 </h4> 703<div class="table"> 704<a name="math_toolkit.root_comparison.elliptic_comparison.elliptic0"></a><p class="title"><b>Table 10.13. root with radius 28 and arc length 300) for float, double, long double 705 and cpp_bin_float_50 types, using _X64_AVX</b></p> 706<div class="table-contents"><table class="table" summary="root with radius 28 and arc length 300) for float, double, long double 707 and cpp_bin_float_50 types, using _X64_AVX"> 708<colgroup> 709<col> 710<col> 711<col> 712<col> 713<col> 714<col> 715<col> 716<col> 717<col> 718<col> 719<col> 720<col> 721<col> 722<col> 723<col> 724<col> 725<col> 726<col> 727<col> 728<col> 729<col> 730</colgroup> 731<thead><tr> 732<th> 733 </th> 734<th> 735 <p> 736 float 737 </p> 738 </th> 739<th> 740 </th> 741<th> 742 </th> 743<th> 744 </th> 745<th> 746 </th> 747<th> 748 <p> 749 double 750 </p> 751 </th> 752<th> 753 </th> 754<th> 755 </th> 756<th> 757 </th> 758<th> 759 </th> 760<th> 761 <p> 762 long d 763 </p> 764 </th> 765<th> 766 </th> 767<th> 768 </th> 769<th> 770 </th> 771<th> 772 </th> 773<th> 774 <p> 775 cpp50 776 </p> 777 </th> 778<th> 779 </th> 780<th> 781 </th> 782<td class="auto-generated"> </td> 783<td class="auto-generated"> </td> 784</tr></thead> 785<tbody> 786<tr> 787<td> 788 <p> 789 Algo 790 </p> 791 </td> 792<td> 793 <p> 794 Its 795 </p> 796 </td> 797<td> 798 <p> 799 Times 800 </p> 801 </td> 802<td> 803 <p> 804 Norm 805 </p> 806 </td> 807<td> 808 <p> 809 Dis 810 </p> 811 </td> 812<td> 813 </td> 814<td> 815 <p> 816 Its 817 </p> 818 </td> 819<td> 820 <p> 821 Times 822 </p> 823 </td> 824<td> 825 <p> 826 Norm 827 </p> 828 </td> 829<td> 830 <p> 831 Dis 832 </p> 833 </td> 834<td> 835 </td> 836<td> 837 <p> 838 Its 839 </p> 840 </td> 841<td> 842 <p> 843 Times 844 </p> 845 </td> 846<td> 847 <p> 848 Norm 849 </p> 850 </td> 851<td> 852 <p> 853 Dis 854 </p> 855 </td> 856<td> 857 </td> 858<td> 859 <p> 860 Its 861 </p> 862 </td> 863<td> 864 <p> 865 Times 866 </p> 867 </td> 868<td> 869 <p> 870 Norm 871 </p> 872 </td> 873<td> 874 <p> 875 Dis 876 </p> 877 </td> 878<td> 879 </td> 880</tr> 881<tr> 882<td> 883 <p> 884 TOMS748 885 </p> 886 </td> 887<td> 888 <p> 889 5 890 </p> 891 </td> 892<td> 893 <p> 894 500 895 </p> 896 </td> 897<td> 898 <p> 899 1.33 900 </p> 901 </td> 902<td> 903 <p> 904 -1 905 </p> 906 </td> 907<td> 908 </td> 909<td> 910 <p> 911 9 912 </p> 913 </td> 914<td> 915 <p> 916 1046 917 </p> 918 </td> 919<td> 920 <p> 921 1.72 922 </p> 923 </td> 924<td> 925 <p> 926 1 927 </p> 928 </td> 929<td> 930 </td> 931<td> 932 <p> 933 9 934 </p> 935 </td> 936<td> 937 <p> 938 1062 939 </p> 940 </td> 941<td> 942 <p> 943 1.70 944 </p> 945 </td> 946<td> 947 <p> 948 1 949 </p> 950 </td> 951<td> 952 </td> 953<td> 954 <p> 955 11 956 </p> 957 </td> 958<td> 959 <p> 960 698437 961 </p> 962 </td> 963<td> 964 <p> 965 1.54 966 </p> 967 </td> 968<td> 969 <p> 970 -3 971 </p> 972 </td> 973<td> 974 </td> 975</tr> 976<tr> 977<td> 978 <p> 979 Newton 980 </p> 981 </td> 982<td> 983 <p> 984 3 985 </p> 986 </td> 987<td> 988 <p> 989 484 990 </p> 991 </td> 992<td> 993 <p> 994 1.29 995 </p> 996 </td> 997<td> 998 <p> 999 -1 1000 </p> 1001 </td> 1002<td> 1003 </td> 1004<td> 1005 <p> 1006 4 1007 </p> 1008 </td> 1009<td> 1010 <p> 1011 734 1012 </p> 1013 </td> 1014<td> 1015 <p> 1016 1.21 1017 </p> 1018 </td> 1019<td> 1020 <p> 1021 1 1022 </p> 1023 </td> 1024<td> 1025 </td> 1026<td> 1027 <p> 1028 4 1029 </p> 1030 </td> 1031<td> 1032 <p> 1033 687 1034 </p> 1035 </td> 1036<td> 1037 <p> 1038 1.10 1039 </p> 1040 </td> 1041<td> 1042 <p> 1043 1 1044 </p> 1045 </td> 1046<td> 1047 </td> 1048<td> 1049 <p> 1050 5 1051 </p> 1052 </td> 1053<td> 1054 <p> 1055 545312 1056 </p> 1057 </td> 1058<td> 1059 <p> 1060 1.20 1061 </p> 1062 </td> 1063<td> 1064 <p> 1065 0 1066 </p> 1067 </td> 1068<td> 1069 </td> 1070</tr> 1071<tr> 1072<td> 1073 <p> 1074 Halley 1075 </p> 1076 </td> 1077<td> 1078 <p> 1079 2 1080 </p> 1081 </td> 1082<td> 1083 <p> 1084 375 1085 </p> 1086 </td> 1087<td> 1088 <p> 1089 <span class="blue">1.00</span> 1090 </p> 1091 </td> 1092<td> 1093 <p> 1094 0 1095 </p> 1096 </td> 1097<td> 1098 </td> 1099<td> 1100 <p> 1101 3 1102 </p> 1103 </td> 1104<td> 1105 <p> 1106 609 1107 </p> 1108 </td> 1109<td> 1110 <p> 1111 <span class="blue">1.00</span> 1112 </p> 1113 </td> 1114<td> 1115 <p> 1116 3 1117 </p> 1118 </td> 1119<td> 1120 </td> 1121<td> 1122 <p> 1123 3 1124 </p> 1125 </td> 1126<td> 1127 <p> 1128 625 1129 </p> 1130 </td> 1131<td> 1132 <p> 1133 <span class="blue">1.00</span> 1134 </p> 1135 </td> 1136<td> 1137 <p> 1138 3 1139 </p> 1140 </td> 1141<td> 1142 </td> 1143<td> 1144 <p> 1145 4 1146 </p> 1147 </td> 1148<td> 1149 <p> 1150 453125 1151 </p> 1152 </td> 1153<td> 1154 <p> 1155 <span class="blue">1.00</span> 1156 </p> 1157 </td> 1158<td> 1159 <p> 1160 0 1161 </p> 1162 </td> 1163<td> 1164 </td> 1165</tr> 1166<tr> 1167<td> 1168 <p> 1169 Schröder 1170 </p> 1171 </td> 1172<td> 1173 <p> 1174 3 1175 </p> 1176 </td> 1177<td> 1178 <p> 1179 546 1180 </p> 1181 </td> 1182<td> 1183 <p> 1184 1.46 1185 </p> 1186 </td> 1187<td> 1188 <p> 1189 -1 1190 </p> 1191 </td> 1192<td> 1193 </td> 1194<td> 1195 <p> 1196 6 1197 </p> 1198 </td> 1199<td> 1200 <p> 1201 1109 1202 </p> 1203 </td> 1204<td> 1205 <p> 1206 1.82 1207 </p> 1208 </td> 1209<td> 1210 <p> 1211 1 1212 </p> 1213 </td> 1214<td> 1215 </td> 1216<td> 1217 <p> 1218 6 1219 </p> 1220 </td> 1221<td> 1222 <p> 1223 1187 1224 </p> 1225 </td> 1226<td> 1227 <p> 1228 1.90 1229 </p> 1230 </td> 1231<td> 1232 <p> 1233 1 1234 </p> 1235 </td> 1236<td> 1237 </td> 1238<td> 1239 <p> 1240 5 1241 </p> 1242 </td> 1243<td> 1244 <p> 1245 564062 1246 </p> 1247 </td> 1248<td> 1249 <p> 1250 1.24 1251 </p> 1252 </td> 1253<td> 1254 <p> 1255 -2 1256 </p> 1257 </td> 1258<td> 1259 </td> 1260</tr> 1261</tbody> 1262</table></div> 1263</div> 1264<br class="table-break"><h4> 1265<a name="math_toolkit.root_comparison.elliptic_comparison.h2"></a> 1266 <span class="phrase"><a name="math_toolkit.root_comparison.elliptic_comparison.program_example_root_elliptic_f1"></a></span><a class="link" href="elliptic_comparison.html#math_toolkit.root_comparison.elliptic_comparison.program_example_root_elliptic_f1">Program 1267 root_elliptic_finding.cpp, 1268 GNU C++ version 7.1.0, GNU libstdc++ version 20170502, Win32 Compiled in 1269 optimise mode., _X64_SSE2</a> 1270 </h4> 1271<div class="table"> 1272<a name="math_toolkit.root_comparison.elliptic_comparison.elliptic1"></a><p class="title"><b>Table 10.14. root with radius 28 and arc length 300) for float, double, long double 1273 and cpp_bin_float_50 types, using _X64_SSE2</b></p> 1274<div class="table-contents"><table class="table" summary="root with radius 28 and arc length 300) for float, double, long double 1275 and cpp_bin_float_50 types, using _X64_SSE2"> 1276<colgroup> 1277<col> 1278<col> 1279<col> 1280<col> 1281<col> 1282<col> 1283<col> 1284<col> 1285<col> 1286<col> 1287<col> 1288<col> 1289<col> 1290<col> 1291<col> 1292<col> 1293<col> 1294<col> 1295<col> 1296<col> 1297<col> 1298</colgroup> 1299<thead><tr> 1300<th> 1301 </th> 1302<th> 1303 <p> 1304 float 1305 </p> 1306 </th> 1307<th> 1308 </th> 1309<th> 1310 </th> 1311<th> 1312 </th> 1313<th> 1314 </th> 1315<th> 1316 <p> 1317 double 1318 </p> 1319 </th> 1320<th> 1321 </th> 1322<th> 1323 </th> 1324<th> 1325 </th> 1326<th> 1327 </th> 1328<th> 1329 <p> 1330 long d 1331 </p> 1332 </th> 1333<th> 1334 </th> 1335<th> 1336 </th> 1337<th> 1338 </th> 1339<th> 1340 </th> 1341<th> 1342 <p> 1343 cpp50 1344 </p> 1345 </th> 1346<th> 1347 </th> 1348<th> 1349 </th> 1350<td class="auto-generated"> </td> 1351<td class="auto-generated"> </td> 1352</tr></thead> 1353<tbody> 1354<tr> 1355<td> 1356 <p> 1357 Algo 1358 </p> 1359 </td> 1360<td> 1361 <p> 1362 Its 1363 </p> 1364 </td> 1365<td> 1366 <p> 1367 Times 1368 </p> 1369 </td> 1370<td> 1371 <p> 1372 Norm 1373 </p> 1374 </td> 1375<td> 1376 <p> 1377 Dis 1378 </p> 1379 </td> 1380<td> 1381 </td> 1382<td> 1383 <p> 1384 Its 1385 </p> 1386 </td> 1387<td> 1388 <p> 1389 Times 1390 </p> 1391 </td> 1392<td> 1393 <p> 1394 Norm 1395 </p> 1396 </td> 1397<td> 1398 <p> 1399 Dis 1400 </p> 1401 </td> 1402<td> 1403 </td> 1404<td> 1405 <p> 1406 Its 1407 </p> 1408 </td> 1409<td> 1410 <p> 1411 Times 1412 </p> 1413 </td> 1414<td> 1415 <p> 1416 Norm 1417 </p> 1418 </td> 1419<td> 1420 <p> 1421 Dis 1422 </p> 1423 </td> 1424<td> 1425 </td> 1426<td> 1427 <p> 1428 Its 1429 </p> 1430 </td> 1431<td> 1432 <p> 1433 Times 1434 </p> 1435 </td> 1436<td> 1437 <p> 1438 Norm 1439 </p> 1440 </td> 1441<td> 1442 <p> 1443 Dis 1444 </p> 1445 </td> 1446<td> 1447 </td> 1448</tr> 1449<tr> 1450<td> 1451 <p> 1452 TOMS748 1453 </p> 1454 </td> 1455<td> 1456 <p> 1457 5 1458 </p> 1459 </td> 1460<td> 1461 <p> 1462 328 1463 </p> 1464 </td> 1465<td> 1466 <p> 1467 1.24 1468 </p> 1469 </td> 1470<td> 1471 <p> 1472 -1 1473 </p> 1474 </td> 1475<td> 1476 </td> 1477<td> 1478 <p> 1479 8 1480 </p> 1481 </td> 1482<td> 1483 <p> 1484 890 1485 </p> 1486 </td> 1487<td> 1488 <p> 1489 1.50 1490 </p> 1491 </td> 1492<td> 1493 <p> 1494 0 1495 </p> 1496 </td> 1497<td> 1498 </td> 1499<td> 1500 <p> 1501 8 1502 </p> 1503 </td> 1504<td> 1505 <p> 1506 1234 1507 </p> 1508 </td> 1509<td> 1510 <p> 1511 1.61 1512 </p> 1513 </td> 1514<td> 1515 <p> 1516 4 1517 </p> 1518 </td> 1519<td> 1520 </td> 1521<td> 1522 <p> 1523 11 1524 </p> 1525 </td> 1526<td> 1527 <p> 1528 487500 1529 </p> 1530 </td> 1531<td> 1532 <p> 1533 1.57 1534 </p> 1535 </td> 1536<td> 1537 <p> 1538 -3 1539 </p> 1540 </td> 1541<td> 1542 </td> 1543</tr> 1544<tr> 1545<td> 1546 <p> 1547 Newton 1548 </p> 1549 </td> 1550<td> 1551 <p> 1552 3 1553 </p> 1554 </td> 1555<td> 1556 <p> 1557 359 1558 </p> 1559 </td> 1560<td> 1561 <p> 1562 1.35 1563 </p> 1564 </td> 1565<td> 1566 <p> 1567 -1 1568 </p> 1569 </td> 1570<td> 1571 </td> 1572<td> 1573 <p> 1574 4 1575 </p> 1576 </td> 1577<td> 1578 <p> 1579 718 1580 </p> 1581 </td> 1582<td> 1583 <p> 1584 1.21 1585 </p> 1586 </td> 1587<td> 1588 <p> 1589 1 1590 </p> 1591 </td> 1592<td> 1593 </td> 1594<td> 1595 <p> 1596 4 1597 </p> 1598 </td> 1599<td> 1600 <p> 1601 843 1602 </p> 1603 </td> 1604<td> 1605 <p> 1606 1.10 1607 </p> 1608 </td> 1609<td> 1610 <p> 1611 1 1612 </p> 1613 </td> 1614<td> 1615 </td> 1616<td> 1617 <p> 1618 5 1619 </p> 1620 </td> 1621<td> 1622 <p> 1623 379687 1624 </p> 1625 </td> 1626<td> 1627 <p> 1628 1.22 1629 </p> 1630 </td> 1631<td> 1632 <p> 1633 0 1634 </p> 1635 </td> 1636<td> 1637 </td> 1638</tr> 1639<tr> 1640<td> 1641 <p> 1642 Halley 1643 </p> 1644 </td> 1645<td> 1646 <p> 1647 2 1648 </p> 1649 </td> 1650<td> 1651 <p> 1652 265 1653 </p> 1654 </td> 1655<td> 1656 <p> 1657 <span class="blue">1.00</span> 1658 </p> 1659 </td> 1660<td> 1661 <p> 1662 0 1663 </p> 1664 </td> 1665<td> 1666 </td> 1667<td> 1668 <p> 1669 3 1670 </p> 1671 </td> 1672<td> 1673 <p> 1674 593 1675 </p> 1676 </td> 1677<td> 1678 <p> 1679 <span class="blue">1.00</span> 1680 </p> 1681 </td> 1682<td> 1683 <p> 1684 1 1685 </p> 1686 </td> 1687<td> 1688 </td> 1689<td> 1690 <p> 1691 3 1692 </p> 1693 </td> 1694<td> 1695 <p> 1696 765 1697 </p> 1698 </td> 1699<td> 1700 <p> 1701 <span class="blue">1.00</span> 1702 </p> 1703 </td> 1704<td> 1705 <p> 1706 7 1707 </p> 1708 </td> 1709<td> 1710 </td> 1711<td> 1712 <p> 1713 4 1714 </p> 1715 </td> 1716<td> 1717 <p> 1718 310937 1719 </p> 1720 </td> 1721<td> 1722 <p> 1723 <span class="blue">1.00</span> 1724 </p> 1725 </td> 1726<td> 1727 <p> 1728 0 1729 </p> 1730 </td> 1731<td> 1732 </td> 1733</tr> 1734<tr> 1735<td> 1736 <p> 1737 Schröder 1738 </p> 1739 </td> 1740<td> 1741 <p> 1742 3 1743 </p> 1744 </td> 1745<td> 1746 <p> 1747 343 1748 </p> 1749 </td> 1750<td> 1751 <p> 1752 1.29 1753 </p> 1754 </td> 1755<td> 1756 <p> 1757 -1 1758 </p> 1759 </td> 1760<td> 1761 </td> 1762<td> 1763 <p> 1764 4 1765 </p> 1766 </td> 1767<td> 1768 <p> 1769 812 1770 </p> 1771 </td> 1772<td> 1773 <p> 1774 1.37 1775 </p> 1776 </td> 1777<td> 1778 <p> 1779 0 1780 </p> 1781 </td> 1782<td> 1783 </td> 1784<td> 1785 <p> 1786 4 1787 </p> 1788 </td> 1789<td> 1790 <p> 1791 1046 1792 </p> 1793 </td> 1794<td> 1795 <p> 1796 1.37 1797 </p> 1798 </td> 1799<td> 1800 <p> 1801 3 1802 </p> 1803 </td> 1804<td> 1805 </td> 1806<td> 1807 <p> 1808 5 1809 </p> 1810 </td> 1811<td> 1812 <p> 1813 390625 1814 </p> 1815 </td> 1816<td> 1817 <p> 1818 1.26 1819 </p> 1820 </td> 1821<td> 1822 <p> 1823 -2 1824 </p> 1825 </td> 1826<td> 1827 </td> 1828</tr> 1829</tbody> 1830</table></div> 1831</div> 1832<br class="table-break"><p> 1833 Remarks: 1834 </p> 1835<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 1836<li class="listitem"> 1837 The function being solved is now moderately expensive to call, and twice 1838 as expensive to call when obtaining the derivative than when not. Consequently 1839 there is very little improvement in moving from a derivative free method, 1840 to Newton iteration. However, once you've calculated the first derivative 1841 the second comes almost for free, consequently the third order methods 1842 (Halley) does much the best. 1843 </li> 1844<li class="listitem"> 1845 Of the two second order methods, Halley does best as would be expected: 1846 the Schroder method offers better guarantees of <span class="emphasis"><em>quadratic</em></span> 1847 convergence, while Halley relies on a smooth function with a single root 1848 to give <span class="emphasis"><em>cubic</em></span> convergence. It's not entirely clear 1849 why Schroder iteration often does worse than Newton. 1850 </li> 1851</ul></div> 1852</div> 1853<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 1854<td align="left"></td> 1855<td align="right"><div class="copyright-footer">Copyright © 2006-2019 Nikhar 1856 Agrawal, Anton Bikineev, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, 1857 Hubert Holin, Bruno Lalande, John Maddock, Jeremy Murphy, Matthew Pulver, Johan 1858 Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, 1859 Daryle Walker and Xiaogang Zhang<p> 1860 Distributed under the Boost Software License, Version 1.0. (See accompanying 1861 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>) 1862 </p> 1863</div></td> 1864</tr></table> 1865<hr> 1866<div class="spirit-nav"> 1867<a accesskey="p" href="root_n_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="../../poly.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a> 1868</div> 1869</body> 1870</html> 1871
