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 to view this page for the latest version.
PrevUpHomeNext

Comparison of Cube Root Finding Algorithms

In the table below, the cube root of 28 was computed for three fundamental (built-in) 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 14.1, Dinkumware standard library version 650, Win32, x86
1000000 evaluations of each of 5 root_finding algorithms.

Table 8.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

78125

1.0

0

0

62500

1.0

1

0

93750

1.0

1

0

11890625

1.1

0

TOMS748

8

468750

6.0

-1

11

906250

15.

2

11

906250

9.7

2

6

80859375

7.6

-2

Newton

5

203125

2.6

0

6

234375

3.8

0

6

187500

2.0

0

2

10640625

1.0

0

Halley

3

234375

3.0

0

4

265625

4.3

0

4

234375

2.5

0

2

26250000

2.5

0

Schröder

4

296875

3.8

0

5

281250

4.5

0

5

234375

2.5

0

2

32437500

3.0

0


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

Table 8.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

62500

1.0

0

0

78125

1.0

0

0

3859375

1.3

0

TOMS748

8

203125

4.3

-1

11

453125

7.2

2

10

781250

10.

-1

6

21796875

7.6

-2

Newton

5

109375

2.3

0

6

140625

2.2

0

6

125000

1.6

0

2

2859375

1.0

-1

Halley

3

109375

2.3

0

4

140625

2.2

0

4

187500

2.4

0

2

6750000

2.4

0

Schröder

4

125000

2.7

0

5

187500

3.0

0

5

296875

3.8

0

2

8156250

2.9

0



PrevUpHomeNext