N 次方根求根算法比较 - Boost C++ 函数库

N次根查找算法比较

第二个例子比较了四种广义 n 次根查找算法，用于查找单个值 28.0 的各种 n 次根（5、7 和 13），以及四种浮点类型 float、double、long double 和一个 Boost.Multiprecision 类型 cpp_bin_float_50。在每种情况下，目标精度都设置为我们“推荐”的精度限制（或者至少是作为良好起点——很可能接近完全精度而不进行不必要的迭代）。

函数	请求精度
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)

测试使用了 Microsoft Visual Studio 2013 (Update 1) 和 GCC 4.9.1，以及源代码 root_n_finding_algorithms.cpp。

计时不确定性（尤其在使用 MSVC 时）至少是归一化时间“Norm”的 5%。

“最佳”和“最差”算法通过蓝色和红色突出显示。当归一化时间在不确定性范围内无法区分时，可能会有多个结果是“最佳”。

程序 ..\example\root_n_finding_algorithms.cpp, Microsoft Visual C++ 版本 14.1, Dinkumware 标准库版本 650, Win32 优化模式编译., _X86_SSE2

完全精度分数 1

表 10.3. float、double、long double 和 cpp_bin_float_50 类型的 5 次根(28)，使用 _X86_SSE2

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	7	457	2.00	0	11	860	3.54	1	11	806	3.02	1	12	226875	8.11	0
牛顿法	3	228	1.00	0	4	243	1.00	-1	4	298	1.12	-1	6	27968	1.00	0
哈雷法	2	250	1.10	0	3	268	1.10	0	3	267	1.00	0	4	52812	1.89	0
施罗德法	2	256	1.12	0	3	271	1.12	-1	3	270	1.01	-1	4	61406	2.20	0

表 10.4. float、double、long double 和 cpp_bin_float_50 类型的 7 次根(28)，使用 _X86_SSE2

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	12	825	3.06	1	15	1145	4.06	2	15	1159	4.17	2	14	295781	8.12	0
牛顿法	5	270	1.00	0	6	282	1.00	0	6	278	1.00	0	8	36406	1.00	0
哈雷法	4	303	1.12	0	5	329	1.17	0	5	335	1.21	0	6	78281	2.15	0
施罗德法	5	340	1.26	0	6	432	1.53	0	6	367	1.32	0	7	85156	2.34	0

表 10.5. float、double、long double 和 cpp_bin_float_50 类型的 11 次根(28)，使用 _X86_SSE2

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	12	714	3.16	-2	14	909	4.19	2	14	793	3.69	2	17	211718	9.28	2
牛顿法	6	226	1.00	0	7	217	1.00	0	7	215	1.00	0	9	22812	1.00	0
哈雷法	4	262	1.16	-1	5	260	1.20	0	5	260	1.21	0	6	40781	1.79	0
施罗德法	6	332	1.47	0	7	314	1.45	0	7	310	1.44	0	8	67187	2.95	0

程序 root_n_finding_algorithms.cpp, Microsoft Visual C++ 版本 12.0, Dinkumware 标准库版本 610, Win32 优化模式编译., _X64_AVX

完全精度分数 1

表 10.6. float、double、long double 和 cpp_bin_float_50 类型的 5 次根(28)，使用 _X64_AVX

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	7	239	1.50	0	11	451	2.53	1	11	439	2.49	1	12	90312	7.51	0
牛顿法	3	159	1.00	0	4	178	1.00	-1	4	176	1.00	-1	6	12031	1.00	0
哈雷法	2	168	1.06	0	3	203	1.14	0	3	198	1.13	0	4	20937	1.74	0
施罗德法	2	173	1.09	0	3	206	1.16	-1	3	203	1.15	-1	4	26250	2.18	0

表 10.7. float、double、long double 和 cpp_bin_float_50 类型的 7 次根(28)，使用 _X64_AVX

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	12	385	2.19	1	15	635	3.13	2	15	621	3.17	2	14	114843	6.81	0
牛顿法	5	176	1.00	0	6	203	1.00	0	6	196	1.00	0	8	16875	1.00	0
哈雷法	4	209	1.19	0	5	254	1.25	0	5	246	1.26	0	6	32343	1.92	0
施罗德法	5	223	1.27	0	6	273	1.34	0	6	275	1.40	0	7	45156	2.68	0

表 10.8. float、double、long double 和 cpp_bin_float_50 类型的 11 次根(28)，使用 _X64_AVX

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	12	467	2.42	-2	14	648	3.06	2	14	640	2.99	2	17	170000	8.85	2
牛顿法	6	193	1.00	0	7	212	1.00	0	7	214	1.00	0	9	19218	1.00	0
哈雷法	4	209	1.08	-1	5	256	1.21	0	5	250	1.17	0	6	32656	1.70	0
施罗德法	6	248	1.28	0	7	306	1.44	0	7	298	1.39	0	8	53437	2.78	0

程序 ..\example\root_n_finding_algorithms.cpp, GNU C++ 版本 7.1.0, GNU libstdc++ 版本 20170502, Win32 优化模式编译., _X64_SSE2

完全精度分数 1

表 10.9. float、double、long double 和 cpp_bin_float_50 类型的 5 次根(28)，使用 _X64_SSE2

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	7	206	2.24	0	11	460	4.04	1	9	554	4.40	0	12	57656	8.39	0
牛顿法	3	92	1.00	0	4	114	1.00	-1	5	126	1.00	0	6	6875	1.00	0
哈雷法	2	106	1.15	0	3	134	1.18	0	3	178	1.41	0	4	12500	1.82	0
施罗德法	2	126	1.37	0	3	143	1.25	-1	3	198	1.57	0	4	15312	2.23	0

表 10.10. float、double、long double 和 cpp_bin_float_50 类型的 7 次根(28)，使用 _X64_SSE2

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	12	345	2.09	1	15	615	3.14	2	13	875	3.98	0	14	70937	7.32	0
牛顿法	5	165	1.00	0	6	196	1.00	0	7	220	1.00	0	8	9687	1.00	0
哈雷法	4	193	1.17	0	5	239	1.22	0	5	298	1.35	0	6	19062	1.97	0
施罗德法	5	217	1.32	0	6	270	1.38	0	6	367	1.67	0	7	27343	2.82	0

表 10.11. float、double、long double 和 cpp_bin_float_50 类型的 11 次根(28)，使用 _X64_SSE2

	float				double				long d				cpp50
算法	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离	迭代次数	时间	范数	距离
TOMS748	12	412	2.15	-2	14	646	2.96	2	14	1054	4.22	1	17	107187	9.53	2
牛顿法	6	192	1.00	0	7	218	1.00	0	7	250	1.00	0	9	11250	1.00	0
哈雷法	4	200	1.04	-1	5	243	1.11	0	5	345	1.38	0	6	19687	1.75	0
施罗德法	6	254	1.32	0	7	321	1.47	0	7	471	1.88	0	8	33281	2.96	0

从这个有限的练习中可以得出一些初步结论。

也许令人惊讶的是，各种算法在基本（内置）类型浮点类型之间几乎没有区别。使用第一导数（牛顿-拉夫逊迭代）通常是最好的，但是与无导数的TOMS 算法 748：连续函数零点的包围相比，迭代次数有显著改善，但执行时间改善不大。这反映了我们正在寻找根的函数易于求值，因此运行时间主要由每种方法中样板代码的耗时决定。
计算第二导数（Halley 或 Schröder）的额外成本通常不足以带来净收益：与立方根一样，这些函子求值非常便宜，运行时主要由根查找方法的复杂性决定。
对于 Boost.Multiprecision 浮点类型，牛顿-拉夫逊迭代是明显的赢家，比 TOMS 算法 748：连续函数零点的包围快几倍，并且与二阶导数算法相比也没有改进。
50 位十进制精度的 Boost.Multiprecision 的运行时间大约是 double 的 30 倍。
列“dis”显示了与正确结果的比特距离。牛顿-拉夫逊算法比 TOMS 算法 748：连续函数零点的包围的精度要好一到两个比特。
“猜测”的准确性对于 Boost.Multiprecision 尤其关键。单独的实验表明，使用 double 计算“猜测”可以在一到两次迭代中收敛到最终的精确结果。因此，在这个人为设计的例子中，粗略地将指数除以 N 作为“猜测”，最好使用 pow<double> 函数，或者，如果需要更精确，则使用 pow<long double> 函数来估计“猜测”。这种策略的局限性在于，可能的（指数）值的范围可能小于多精度类型。
使用浮点扩展 SSE2 指令使速度适度提升了百分之十。
使用 MSVC 时，使用 64 位有一些改进，特别是对于 Boost.Multiprecision。
GCC 编译器 4.9.1 使用 64 位比 32 位快至少五倍，这显然反映了更好的优化。

显然，您的体验 可能会有所不同，但总而言之，牛顿-拉夫逊迭代似乎是首选算法，而努力寻找一个好的“猜测”是首要的加速目标，特别是对于 Boost.Multiprecision。当然，编译器的优化对速度至关重要。

Boost C++ 库

N次根查找算法比较

程序 ..\example\root_n_finding_algorithms.cpp, Microsoft Visual C++ 版本 14.1, Dinkumware 标准库版本 650, Win32 优化模式编译., _X86_SSE2

程序 root_n_finding_algorithms.cpp, Microsoft Visual C++ 版本 12.0, Dinkumware 标准库版本 610, Win32 优化模式编译., _X64_AVX

程序 ..\example\root_n_finding_algorithms.cpp, GNU C++ 版本 7.1.0, GNU libstdc++ 版本 20170502, Win32 优化模式编译., _X64_SSE2