Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Comparison of Elliptic Integral Root Finding Algoritghms

A second example compares four root finding algorithms for locating the second radius of an ellipse with first radius 28 and arc length 300, for four floating-point types, float, double, long double and a Boost.Multiprecision type cpp_bin_float_50.

Which is to say we're solving:

4xE(sqrt(1 - 282 / x2)) - 300 = 0

In each case the target accuracy was set using our "recomended" accuracy limits (or at least limits that make a good starting point - which is likely to give close to full accuracy without resorting to unnecessary iterations).

Function

Precision Requested

TOMS748

numeric_limits<T>::digits - 2

Newton

floor(numeric_limits<T>::digits * 0.6)

Halley

floor(numeric_limits<T>::digits * 0.4)

Schröder

floor(numeric_limits<T>::digits * 0.4)

Tests used Microsoft Visual Studio 2013 (Update 1) and GCC 4.9.1 using source code root_elliptic_finding.cpp.

The timing uncertainty (especially using MSVC) is at least 5% of normalized time 'Norm'.

To pick out the 'best' and 'worst' algorithms are highlighted in blue and red. More than one result can be 'best' when normalized times are indistinguishable within the uncertainty.

Program root_elliptic_finding.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32 Compiled in optimise mode., _X86_SSE2

Table 12.12. root with radius 28 and arc length 300) for float, double, long double and cpp_bin_float_50 types, using _X86_SSE2

float

double

long d

cpp50

   

Algo

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

TOMS748

5

515

1.43

-1

9

968

1.82

1

9

968

1.82

1

11

871875

1.53

-3

Newton

3

453

1.26

-1

4

640

1.21

1

4

640

1.21

1

5

685937

1.20

0

Halley

2

359

1.00

0

3

531

1.00

3

3

531

1.00

3

4

570312

1.00

0

Schröder

3

484

1.35

-1

6

1000

1.88

1

6

984

1.85

1

5

742187

1.30

-2


Program root_elliptic_finding.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32 Compiled in optimise mode., _X64_AVX

Table 12.13. root with radius 28 and arc length 300) for float, double, long double and cpp_bin_float_50 types, using _X64_AVX

float

double

long d

cpp50

   

Algo

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

TOMS748

5

500

1.33

-1

9

1046

1.72

1

9

1062

1.70

1

11

698437

1.54

-3

Newton

3

484

1.29

-1

4

734

1.21

1

4

687

1.10

1

5

545312

1.20

0

Halley

2

375

1.00

0

3

609

1.00

3

3

625

1.00

3

4

453125

1.00

0

Schröder

3

546

1.46

-1

6

1109

1.82

1

6

1187

1.90

1

5

564062

1.24

-2


Program root_elliptic_finding.cpp, GNU C++ version 4.9.2, GNU libstdc++ version 20141030, Win32 Compiled in optimise mode., _X64_SSE2

Table 12.14. root with radius 28 and arc length 300) for float, double, long double and cpp_bin_float_50 types, using _X64_SSE2

float

double

long d

cpp50

   

Algo

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

TOMS748

5

328

1.31

-1

8

875

1.51

0

8

1109

1.69

4

11

479687

1.49

-3

Newton

3

328

1.31

-1

4

671

1.16

1

4

781

1.19

1

5

387500

1.20

0

Halley

2

250

1.00

0

3

578

1.00

1

3

656

1.00

7

4

321875

1.00

0

Schröder

3

375

1.50

-1

4

734

1.27

0

4

828

1.26

3

5

414062

1.29

-2


Remarks:


PrevUpHomeNext