立方根算法比较

在下表中，使用四种算法计算了 28 的立方根，分别使用了三种基本（内置）类型浮点类型，以及一种 Boost.Multiprecision 类型 cpp_bin_float，精度为 50 位十进制数字。

“精确”答案是使用 100 位十进制数字类型计算的

cpp_bin_float_100 full_answer ("3.036588971875662519420809578505669635581453977248111123242141654169177268411884961770250390838097895");

时间是使用 Boost.Timer 的 class cpu_timer 测量的。

Its 是找到根所需的迭代次数。
Times 是以任意单位表示的 CPU 耗时。
Norm 是归一化时间，与最快的算法（值为 1.00）相比。
Dis 是与“精确”根的最接近表示的距离（以位为单位）。与“精确”答案的距离是通过使用函数 Boost.Math float_distance 测量的。一位或两位距离意味着所有结果实际上都是“正确”的。零意味着“精确” - 浮点类型的最接近可表示值。

立方根函数是一个简单的函数，是求根的一个人为示例。它确实允许我们研究一些控制效率的因素，这些因素可以推广到更复杂的函数。

使用的程序是 root_finding_algorithms.cpp。使用了每种浮点类型和算法的 100000 次评估，并且根据重复运行判断 CPU 时间的不确定性为 10%。比较 MSVC 中 double 和 long double（在此平台上相同）可能会提供时间不确定性的指南。

请求的精度设置如下

函数	请求的精度
TOMS748	numeric_limits<T>::digits - 2
牛顿法	floor(numeric_limits<T>::digits * 0.6)
哈雷法	floor(numeric_limits<T>::digits * 0.4)
施罗德法	floor(numeric_limits<T>::digits * 0.4)

C++ 标准立方根函数 std::cbrt 仅为内置或基本类型定义，因此不能与任何用户定义的浮点类型（如 Boost.Multiprecision）一起使用。这一点，以及立方函数表现良好，使得实现者可以使用许多技巧来实现快速计算。在某些平台上，std::cbrt 似乎比更通用的 boost::math::cbrt 快几倍，而在其他平台/编译器选项中，boost::math::cbrt 明显更快。一般来说，结果高度依赖于代码生成/处理器架构选择编译器选项。可以假设标准库在安装它的平台上使用几乎最优的选项编译，而用户对 Boost.Math 使用的选项有更多选择。选择太通用/保守的选项会导致性能下降，而选择利用最新指令集操作码的选项会显着提高速度。
比较了优化模式下的两个编译器：使用 Netbeans IDS 的 GCC 4.9.1 和同一硬件上的 Microsoft Visual Studio 2013（Update 1）。迭代次数似乎一致，但相对运行时间却出奇地不同。
boost::math::cbrt 允许与 任何用户定义的浮点类型 一起使用，方便地包括 Boost.Multiprecision。与 nth 次求根示例中更通用的实现相比，它也可以利用立方函数的良好行为。例如，它使用多项式逼近来生成比将指数除以三更好的猜测，并且可以避免牛顿-拉夫逊迭代中所需的复杂检查，以防止搜索严重偏离轨道。对于已知的精度，也可能固定迭代次数，从而允许内联和循环展开。它还在代数上简化了哈雷步骤，与“黑盒”实现（分别计算导数，然后在哈雷代码中组合它们）相比，大大减少了所需的浮点运算次数。通常，发现使用 double 类型进行计算时，直接使用各种求根算法而不是手工编码/优化的 cbrt 例程要花费几倍的时间。
对于多精度情况，迭代计数可以看出获得良好猜测的重要性：在这里，我们“作弊”了一点，并使用计算到双精度的立方根作为初始猜测。这种策略的局限性在于，可能的（指数）值的范围可能小于多精度类型。
对于基本（内置）类型，三种导数方法之间几乎没有区别，但对于 cpp_bin_float，牛顿-拉夫逊迭代快了两倍。请注意，立方根是一个极端的测试案例，因为调用函子的成本非常低，以至于运行时主要由迭代代码的复杂性决定。
使用优化进行编译使计算时间减半，并且算法之间的任何差异都变得几乎可以忽略不计。TOMS 算法 748：连续函数的封闭零点的优化加速尤其明显。
对于 50 位十进制数字的精度，使用像 cpp_bin_float_50 这样的多精度类型花费的时间要长得多，正如预期的那样，因为大多数计算都使用软件而不是 64 位浮点硬件。速度通常慢 50 倍以上。
使用 cpp_bin_float_50，TOMS 算法 748：连续函数的封闭零点慢得多，这表明了使用导数的好处。牛顿-拉夫逊迭代被发现比任何二阶导数方法快两倍：但这是一种极端情况，函数及其导数的计算成本非常低，以至于我们实际上是在测量样板求根代码的复杂性。
对于多精度类型，无论使用哪种算法，只需要一到两次额外的迭代即可获得剩余的 35 位数字。（这些类型所花费的时间当然要长得多）。
使用 100 位十进制数字类型仅使时间增加了一倍，并且只需要非常少的迭代次数，因此额外精度的成本主要在于计算更多数字的底层成本，而不是算法的工作方式。这证实了之前使用 NTL 用于数论的库高精度类型的观察结果。

程序 root_finding_algorithms.cpp，Microsoft Visual C++ 版本 14.1，Dinkumware 标准库版本 650，Win32，x86
每个 5 种求根算法评估 1000000 次。

表 10.1. float、double、long double 和 cpp_bin_float_50 的立方根 (28)

	float				double				long d				cpp50
算法	迭代次数	时间	归一化	距离	迭代次数	时间	归一化	距离	迭代次数	时间	归一化	距离	迭代次数	时间	归一化	距离
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
牛顿法	5	203125	2.6	0	6	234375	3.8	0	6	187500	2.0	0	2	10640625	1.0	0
哈雷法	3	234375	3.0	0	4	265625	4.3	0	4	234375	2.5	0	2	26250000	2.5	0
施罗德法	4	296875	3.8	0	5	281250	4.5	0	5	234375	2.5	0	2	32437500	3.0	0

程序 root_finding_algorithms.cpp，GNU C++ 版本 9.3.1 20200425，GNU libstdc++ 版本 20200425，Win32，x64
每个 5 种求根算法评估 1000000 次。

表 10.2. float、double、long double 和 cpp_bin_float_50 的立方根 (28)

	float				double				long d				cpp50
算法	迭代次数	时间	归一化	距离	迭代次数	时间	归一化	距离	迭代次数	时间	归一化	距离	迭代次数	时间	归一化	距离
cbrt	0	15625	1.0	0	0	62500	1.0	0	0	62500	1.0	0	0	2718750	1.2	0
TOMS748	8	140625	9.0	-1	11	265625	4.2	2	10	718750	12.	-1	6	16796875	7.5	-2
牛顿法	5	62500	4.0	0	6	62500	1.0	0	6	203125	3.2	0	2	2234375	1.0	-1
哈雷法	3	46875	3.0	0	4	93750	1.5	0	4	234375	3.8	0	2	5187500	2.3	0
施罗德法	4	78125	5.0	0	5	78125	1.2	0	5	265625	4.2	0	2	6609375	3.0	0

Boost C++ 库