重大消息-一种新的任意精度对数算法研制成功

liangbch

   重大消息，近日，由我自己独创的对数log(x)算法终于定型。其复杂度与当前公开发表的最好的算法AGM同，都是O(log(P)M(P)),p为精度，其中M(P)代表两个P位整数相乘所需要的基本运算的次数。但是我的算法有很小的常数因子，故速度更快。测试报告显示，这个算法的性能是非常令人振奋的，在100-10000位精度下，可比现在最快软件Mathematica快2.8到8倍。计算一个正数的对数精确到1万位，仅需2.53毫秒。

下面给出性能数据

测试平台：
处理器: Intel(R) Core(TM) i7-2600K CPU @3.40GH
操作系统: Windows7 32-bit
Maple 版本：17.0
Mathematica版本： 10.3.0 32-bit
Pari版本： 2.9.3
mpfr版本：3.1.6

位数	时间，单位为毫秒
	Maple	Mathematica	Pari	MPFR	BCMP_log1	BCMP_log2
20	0.029941	0.00239015	0.003114	0.004833	0.008654	0.000762
30	0.040354	0.00298078	0.003744	0.005667	0.008218	0.000975
40	0.043768	0.00365648	0.004687	0.006456	0.010237	0.001043
50	0.045405	0.0043437	0.005267	0.006782	0.010515	0.001217
60	0.061336	0.00519375	0.007068	0.008939	0.012052	0.002432
70	0.063722	0.00653649	0.008129	0.009373	0.012467	0.002622
80	0.06523	0.00723503	0.008918	0.010451	0.014011	0.002847
90	0.067488	0.00835762	0.009401	0.010859	0.013989	0.002967
100	0.069835	0.00915581	0.011404	0.012145	0.017113	0.003194
125	0.072167	0.0118124	0.013434	0.014376	0.020085	0.003843
158	0.079578	0.0176895	0.020295	0.018568	0.026015	0.004825
199	0.084953	0.0243275	0.027464	0.023096	0.032686	0.005604
251	0.101058	0.0325844	0.039437	0.030076	0.041313	0.006338
316	0.111391	0.0483244	0.057234	0.03874	0.057398	0.008075
398	0.125592	0.0625776	0.090215	0.054713	0.076384	0.009971
501	0.140205	0.0837851	0.126219	0.076801	0.100851	0.012947
630	0.169863	0.137465	0.173471	0.1227	0.126775	0.025564
794	0.201257	0.202088	0.262401	0.192741	0.175562	0.022624
1000	0.26965	0.311744	0.378275	0.29729	0.260477	0.041692
1258	0.344599	0.42428	0.545905	0.425357	0.321757	0.056777
1584	0.437988	0.574393	0.836217	0.671066	0.504561	0.077545
1995	0.570668	0.814906	1.219222	1.042976	0.671209	0.133183
2511	0.807129	1.11878	1.723848	1.448282	0.983084	0.190615
3162	1.07266	1.57654	2.561828	2.257336	1.489376	0.273305
3981	1.47754	2.26133	3.66907	2.959093	2.155975	0.510987
5011	2.15234	3.06957	5.208427	3.788049	3.193957	0.727249
6309	2.96615	4.36979	7.723928	5.709551	4.507839	1.019573
7943	4.0625	6.25344	11.071721	7.894751	6.753858	1.748821
10000	6.33854	8.50294	15.950279	10.198301	9.649934	2.538205
17782	15.1146	19.8861	38.916218	23.862088	23.569465	6.929607
31622	42.25	52.1046	94.352581	68.980759	62.309453	18.861327
56234	681	117.861	207.879794	131.337302	146.628323	45.943156
100000	2012.67	261.338	587.256462	296.982964	364.771994	117.998387

性能对比折线图，以mpfr为基准，令mpfr的运行时间为1，值越小越好。



性能对比折线图2，去掉Maple的测试结果，仍以mpfr为基准，值越小越好。

liangbch

说明：我的第一个函数使用AGM算法，在上表中标记为BCMP_log1, 第二个使用新算法，标记为BCMP_log2。

更多的信息请参阅 http://calc.ac.cn/2017/12/25/bcmp_log_cn/

落叶

首先祝贺你30年的不懈努力终于得以实现！！！你的对数函数运行速度超过了我一千倍，充分展现了算法的魅力，让我无力追赶

落叶

同样的原理算法，c语言比vb快了快一倍，假如对c语言写的对数函数或其它函数进行汇编级优化，一般情况下大概能获得多大的提升，我没有这方面的经验，一直脑中有个问号？我虽然最早接触的是汇编并知道一些原理，但一直没有这方面的操作经历。

zeroieme

恭喜恭喜
希望有ARM芯片的测试，还有并行优化

liangbch

这个对数算法是基于我自己的大数库的，其中使用了超过10万以上的汇编代码。14万行汇编代码中，手工写的为5万多行，基于\( 2^{30} \) 和基于\( 10 ^9 \)各占一半，另外9万行代码是用程序生成的。所有改为ARM汇编是不大可能了。不过，我有个计划，实现一个基于GMP的对数函数，这样就有ARM版的。
关于并行优化，倒是容易实现，因为这个算法很容易并行化，不过，多线程的实现需要使用更多的内存，我暂时不打算实现。

liangbch

回4楼，大数库的关键是乘法，而乘法的关键是basecase乘（硬乘法），因为karatsuba,toom算法最终会调用basecase乘，故basecase乘法性能的提高可直接提高大数库的整体性能。
我写了5个版本的basecase乘，其中最后一个版本性能不稳定。我的大数库中实际使用的是mpn_B30_mul_basecase_2ways_SSE2。下面是几个函数的性能数据。可以看到，mpn_B30_mul_basecase_2ways_SSE2        的性能是的c语言版的性能的4.47=(3.902/0.872)倍。


# BIN_BASECASE_MUL = mpn_B30_mul_basecase_C        # cycle=3.902
# BIN_BASECASE_MUL = mpn_B30_mul_basecase_ALU        # cycle=2.771
# BIN_BASECASE_MUL = mpn_B30_mul_basecase_1way_SSE2        # cycle=1.446
BIN_BASECASE_MUL = mpn_B30_mul_basecase_2ways_SSE2        # cycle=0.872
# BIN_BASECASE_MUL = mpn_B30_mul_basecase_scatter_SSE2        # cycle=0.742

落叶

感谢你的详细讲解和详细的数据！！！

wayne

有测试代码吗？我想在我的电脑上跑跑。　对了。现在基本上都是64位的天下了，不知道６４位支持否。

另外，这种对比测试对有界面的Maple和Mathematica来说，可能不一定公平。

liangbch

现在，还没有可供使用的Dll，另外，配置也比较麻烦，现在还给不出方便的测试码