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 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 platform) 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 10.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 8.2.0, GNU libstdc++ version 20180728, linux, x64
1000000 evaluations of each of 5 root_finding algorithms.

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

30000

1.0

0

0

60000

1.0

0

0

70000

1.0

0

0

4440000

1.0

0

TOMS748

8

220000

7.3

-1

11

370000

6.2

2

10

580000

8.3

-1

6

28360000

6.7

-2

Newton

5

120000

4.0

0

6

130000

2.2

0

6

180000

2.6

0

2

4260000

1.0

-1

Halley

3

110000

3.7

0

4

140000

2.3

0

4

230000

3.3

0

2

9210000

2.2

0

Schröder

4

120000

4.0

0

5

140000

2.3

0

5

280000

4.0

0

2

11630000

2.7

0



PrevUpHomeNext