数学研发论坛

 找回密码
 欢迎注册
查看: 2097|回复: 82

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

[复制链接]
发表于 2017-12-28 18:16:33 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
   重大消息,近日,由我自己独创的对数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,值越小越好。
perf1-1.png


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

perf2.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-12-28 18:20:30 | 显示全部楼层
说明:我的第一个函数使用AGM算法,在上表中标记为BCMP_log1, 第二个使用新算法,标记为BCMP_log2。

更多的信息请参阅 http://calc.ac.cn/2017/12/25/bcmp_log_cn/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-12-28 19:28:25 | 显示全部楼层
首先祝贺你30年的不懈努力终于得以实现!!!你的对数函数运行速度超过了我一千倍,充分展现了算法的魅力,让我无力追赶
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-12-28 19:52:58 | 显示全部楼层
同样的原理算法,c语言比vb快了快一倍,假如对c语言写的对数函数或其它函数进行汇编级优化,一般情况下大概能获得多大的提升,我没有这方面的经验,一直脑中有个问号?我虽然最早接触的是汇编并知道一些原理,但一直没有这方面的操作经历。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-12-28 20:16:50 | 显示全部楼层
恭喜恭喜
希望有ARM芯片的测试,还有并行优化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-12-28 20:50:01 | 显示全部楼层
这个对数算法是基于我自己的大数库的,其中使用了超过10万以上的汇编代码。14万行汇编代码中,手工写的为5万多行,基于\( 2^{30} \) 和基于\( 10 ^9 \)各占一半,另外9万行代码是用程序生成的。所有改为ARM汇编是不大可能了。不过,我有个计划,实现一个基于GMP的对数函数,这样就有ARM版的。
关于并行优化,倒是容易实现,因为这个算法很容易并行化,不过,多线程的实现需要使用更多的内存,我暂时不打算实现。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-12-28 20:52:04 | 显示全部楼层
回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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-12-28 21:12:22 | 显示全部楼层
感谢你的详细讲解和详细的数据!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-12-28 21:39:18 | 显示全部楼层
有测试代码吗?我想在我的电脑上跑跑。 对了。现在基本上都是64位的天下了,不知道64位支持否。

另外,这种对比测试对有界面的Maple和Mathematica来说,可能不一定公平。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-12-28 21:48:42 | 显示全部楼层
现在,还没有可供使用的Dll,另外,配置也比较麻烦,现在还给不出方便的测试码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-12-11 21:36 , Processed in 0.060752 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表