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

This is the documentation for an old version of boost. Click here for the latest Boost documentation.
PrevUpHomeNext

Comparison of Cube Root Finding Algorithms

In the table below, the cube root of 28 was computed for three fundamental types floating-point types, and one Boost.Multiprecision type cpp_bin_float using 50 decimal digit precision, using four algorithms.

The 'exact' answer was computed using a 100 decimal digit type:

cpp_bin_float_100 full_answer ("3.036588971875662519420809578505669635581453977248111123242141654169177268411884961770250390838097895");

Times were measured using Boost.Timer using class cpu_timer.

The cube-root function is a simple function, and is a contrived example for root-finding. It does allow us to investigate some of the factors controlling efficiency that may be extrapolated to more complex functions.

The program used was root_finding_algorithms.cpp. 100000 evaluations of each floating-point type and algorithm were used and the CPU times were judged from repeat runs to have an uncertainty of 10 %. Comparing MSVC for double and long double (which are identical on this patform) may give a guide to uncertainty of timing.

The requested precision was set as follows:

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)

Program root_finding_algorithms.cpp, Microsoft Visual C++ version 12.0, Dinkumware standard library version 610, Win32, x64
1000000 evaluations of each of 5 root_finding algorithms.

Table 12.1. Cube root(28) for float, double, long double and cpp_bin_float_50

float

double

long d

cpp50

   

Algorithm

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

cbrt

0

46875

1.0

0

0

46875

1.0

1

0

46875

1.0

1

0

4906250

1.1

0

TOMS748

8

234375

5.0

-1

11

437500

9.3

2

11

437500

9.3

2

7

66218750

15.

-2

Newton

5

109375

2.3

0

6

125000

2.7

0

6

140625

3.0

0

2

4531250

1.0

0

Halley

3

125000

2.7

0

4

156250

3.3

0

4

156250

3.3

0

2

10625000

2.3

0

Schröder

4

140625

3.0

0

5

187500

4.0

0

5

203125

4.3

0

2

13109375

2.9

0


Program root_finding_algorithms.cpp, GNU C++ version 4.9.2, GNU libstdc++ version 20141030, Win32, x64
1000000 evaluations of each of 5 root_finding algorithms.

Table 12.2. Cube root(28) for float, double, long double and cpp_bin_float_50

float

double

long d

cpp50

   

Algorithm

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

Its

Times

Norm

Dis

cbrt

0

46875

1.0

0

0

46875

1.0

0

0

46875

1.0

0

0

3500000

1.1

0

TOMS748

8

187500

4.0

-1

11

406250

8.7

2

10

609375

13.

-1

7

44531250

14.

-2

Newton

5

93750

2.0

0

6

109375

2.3

0

6

171875

3.7

0

2

3140625

1.0

-1

Halley

3

93750

2.0

0

4

125000

2.7

0

4

218750

4.7

0

2

7171875

2.3

0

Schröder

4

109375

2.3

0

5

171875

3.7

0

5

281250

6.0

0

2

8703125

2.8

0



PrevUpHomeNext