擂台：超大整数高精度快速算法-4 （快速计算千万阶乘）

gxqcn 2007-07-11 10:22:05
加精
近几个月来，我把精力主要集中于改进大数算法核心乘法部分，终于取得了令人欣喜的进展，
将最最核心的顶级大数乘法算法效率提高了近一倍左右！（代价是手工编写了大量汇编代码）


从现有的数款 CPU 及不同的操作系统的测试来看，在计算“1千万的阶乘”时均提速了 50% 以上，
如10000000!： Factorial_old(t0/s) Factorial_new(t1/s) (t0 - t1)/t1 * 100%
机台A 68.929053 43.584557 58.15%
机台B 48.787876 31.227357 56.23%
机台C 65.850629 42.810574 53.82%
机台D 41.436746 25.617276 61.75%
其中，
机台A —— Windows XP SP2，Intel Pentium 4 CPU 2.93GHz，512MB DDR - 133MHz
机台B —— Windows XP SP2，AMD Athlon 64 Processor 3200+，1GB DDR - 200MHz
机台C —— Windows Vista 64，Intel Pentium 4 CPU 3.00GHz，1GB DDR - 200MHz
机台D —— Windows XP SP2，AMD Athlon 64 X2 Dual Core Processor 4800+，2GB DDR2 - 800MHz



如果大家感兴趣，请从下列两个站点之一下载（169 KB，本链接仅在正式发布前有效）：
http://hugecalc.ik8.com/download/Factorial.rar
http://www.freewebs.com/maths/download/Factorial.rar

欢迎您将测试结果直接发布出来，或填表（我已制作好了 Excel 表）后反馈给我。。。


如果您发现计算“1千万的阶乘”还有更快的程序，请告诉我，必将千分相赠！

//=============================================================================

这是我继2004年连摆的三场“擂台”后，第四次摆“擂台”，
前几次无论是网友还是本人都收获颇丰，但愿这次也会有不俗的效果。


注：前几次“擂台”的链接如下：
http://topic.csdn.net/T/20040510/14/3049738.html
http://topic.csdn.net/T/20040721/19/3197332.html
http://topic.csdn.net/T/20041010/17/3441530.html
近期还有个帖子也非常值得看，是关于汇编优化的，也是这次升级的技术储备之一：
http://community.csdn.net/Expert/TopicView.asp?id=5505130
...全文
5298 84 打赏 收藏 转发到动态 举报
写回复
用AI写文章
84 条回复
切换为时间正序
请发表友善的回复…
发表回复
ai_ya_ya 2011-10-25
  • 打赏
  • 举报
 回复
看着大牛们的比武，小可获益良多。
dianyancao 2011-05-06
  • 打赏
  • 举报
 回复
小數啥數樹仁為本，二分油桶好回收節約資源瞧川外雨瀟瀟42，感謝樓主細心分享！～
wudeshou82666 2008-09-05
  • 打赏
  • 举报
 回复
高手.不是对手.我闪
yaos 2008-02-07
  • 打赏
  • 举报
 回复
如果存在差别
可能就是在汇编代码上存在差别
GMP和你的HugeCalc

GMP的核心四则运算都是汇编的
但稍复杂的算法都是C的，包括FFT/FNT
GMP是实现了FNT的，但似乎是个变体，你可能分析过，能发表下你的结论么
似乎GMP放弃了在小整数上使用FFT
yaos 2008-02-07
  • 打赏
  • 举报
 回复
：（

SSE2汇编和FFT汇编差别大啊
老大

你是FFT的SSE2汇编
还是加和乘的SSE2汇编

如果你连FNT都汇编了，只能说你是变态的追求效率了

看你的意思是FFT和加乘都汇编了

GMP的FFT是非汇编的
gxqcn 2008-02-05
  • 打赏
  • 举报
 回复
HugeCalc早已实现了SSE2汇编。
看来楼上发帖前并没有仔细浏览先前的帖子。
yaos 2008-02-04
  • 打赏
  • 举报
 回复
你想有所突破还是在FFT的优化上做点工作吧
感觉FFT的汇编化能带来大幅度的性能提升，特别是SSE2汇编，很多指令其效率很高
不过，总计算长度将有所限制

另外整的以一为底的FFT不知道你弄到没？？

写论文的事情，你还是放弃吧
在算法上你很难有突破的

在汇编优化上倒可以有写的

gxqcn 2007-11-14
  • 打赏
  • 举报
 回复
（为了与各位网友更好的沟通交流，我新申请了一个收费空间和顶级域名，欢迎大家访问）

中文名称：数学研发网

网址链接：[url=http://www.emath.ac.cn/]http://www.emath.ac.cn/[/url]

Logo图片：[url=http://www.emath.ac.cn/][/url]

网站简介：学术性数学网站；知识与趣味相交融；提供原创数学工具软件。以等幂和、幻方等数学问题为主要研讨对象，站内有许多原创作品，部分尚为国内外研究的空白。本站集知识性、趣味性于一体；从中您将充分感受到“数学美”的魅力！

关 键 词：数学,研发,等幂和,幻方,数论,组合数学,趣味数学,软件 | mathematics,rd,magic square,software,HugeCalc

备 注：HugeCalc 是一款高精度算法库（同时支持 MBCS + UNICODE 版），适合于大规模科学计算，尤其适用于数论、密码学等领域研究，其核心算法耗费作者十余年的心血。具有占用资源少、效率高、使用便捷、易二次开发、可移植性强、可扩展性好等特点。关键文件 HugeCalc.dll 虽然很小，却提供了公共函数接口 709 个（标准C++接口 473 个；标准C接口 236 个），且其计算速度完全可与大型专业数学工具软件媲美！（在双核上测试，精确计算 40,000,000!，HugeCalc 比最新的 Mathematica V6.01 快了 58%！）
liangbch 2007-09-24
  • 打赏
  • 举报
 回复
道一声，楼主辛苦了。
搂主可将这个帖子续下去。我等可以继续通报进展情况。
gxqcn 2007-09-24
  • 打赏
  • 举报
 回复
to liangbch:
短期内我不会有大的进展；倒是你近期做了不少探索，很想知道现在的进展状况如何呢？
非常谢谢你的关心和鼓励，也希望早日看到你的新作问世。

我打算明晚（中秋）结帖。
gxqcn 2007-09-22
  • 打赏
  • 举报
 回复
系统已经三番五次催着结帖了。

本帖虽然标榜为“擂台”，其实我是本着与大家交流学习为出发点，以达到抛砖引玉、相互促进为目的的。
这正如以往的几次“擂台”，让参与者都可从中获益，无论是台上的，还是台下的，哪怕是个旁观者，亦或仅仅是个路过者。

大数高精度（或曰“多精度”）计算是门对数学知识和计算机技术要求都很高的艺术，没有一定的相关知识积累，很难做到高效率。
而我，由于某些原因，既非数学专业又非计算机科班出身，仅凭个人兴趣和爱好，这一切的来源只能靠自学（当然也包括向各位请教）。过程是艰辛的，但坚持下来了，苦中也有乐。

HugeCalc 经过这几次重大升级，无论是功能和效率方面，都已日趋完善，某些综合性指标已超出一些商业性专业软件。而整个开发阶段没有得到任何科研机构的资助，完全是牺牲了业余时间一点一滴雕刻出来的。

感谢今天技术的发达，交流的便捷，让我的软件可以走出我的小屋，为千百万的天下人服务，并可及时得到用户的反馈。感谢 CSDN 这个交流平台，让沟通更方便。
在本帖中，要特别感谢 housisong 网友，因为是你的回帖，让我意识到现在已进入了多核时代，是否做到并行处理将很关键。在参考了各种资料（甚至专门到书店去翻阅购买一些书籍）后，终于写出了多核下高效率的线程池（当然，以前的数据结构也略作了调整，以实现最大程度的并行度），在朋友的双核机器CPU上测试达到了令人惊喜的速度飞跃！

HugeCalc 里面不仅有线程池，还有内存池等设计，核心算法中的每一个函数几乎都有 xxx_ALU()、 xxx_FPU()、 xxx_SSE2() 等多个汇编版本（大家可以想像工作量有多大？！该源代码文件有247KB，10612行代码，汇编近半），可以根据用户的机器配置及设定（见 HugeCalc.ini 文件）进行自动切换，以实现效率最佳化。

最后，提醒一下各位，如果您是在 2007-09-20 日之前下载的，建议到我的主页（http://o.thec.cn/maths/software.htm#02）上重新下载一遍，里面的算法虽然没有变更，但是某些细微末节的地方得到了优化，并调整了注册识别过程（因上周在一朋友笔记本上发现原过程会出现假死现象，害得我苦苦跟踪了好几天）。

时代在变，SSE4 刚出来，SSE5 的提案就来了，新的指令集将可进一步优化算法，并反过来作用于算法设计，使之更容易在新的指令集下工作。现在 HugeCalc V7.0.1.0 发布了，该版有可能是 Win32 平台下的最后一版，因为一是我有点累了，二是需要时间潜心印证一下突然闪现的几个“灵感”式猜想。至于下一版会是什么时候？又会带来什么令人惊喜的变化？还是让我们把期待留给未来吧。。。

（本帖即将结帖，最迟于下周末）
gxqcn 2007-09-20
  • 打赏
  • 举报
 回复
我在双核上测试计算 Fibonacci(2^29=536870912) 的耗时，

Mathematica V6.0.1.0 需 27.282s；

HugeCalc V7.0.1.0 用双核/单核及十进制/二进制系统分别需：
双核/单核 十进制系统 / 二进制系统
NumOfCores = 2 19.183601s / 17.895878s
NumOfCores = 1 32.358898s / 31.086899s
gxqcn 2007-09-17
  • 打赏
  • 举报
 回复
与大家分享两条“新闻”，一条硬件方面的，一条软件方面的：

一、AMD 宣布了基于x86架构的扩展指令集“SSE5”，并计划配备在K10之后的下一代“Bulldozer”核心架构中，预计2009年推出实际产品。

SSE5是128-bit指令集，一共有170条指令，其中基础指令64条；SSE5指令集官方专区：http://developer.amd.com/sse5.jsp

（我下载了它的技术文档，觉得该指令集对数值计算非常有用，相当于 SS2 带来的变革）

二、GMP 终于发布了新版 GMP 4.2.2 （http://gmplib.org/）
之前其官方网站上总是说该版本将在 2007 年春季发布，看来是延期发布了。

下面是在 AMD Athlon 64 Processor 3200+，1GB DDR 的对比测试结果：
Mathematica V5.2 运行“Timing[Fibonacci[2^29];]”的结果为：60.531 Second
HugeCalc V7.0.1.0 计算 Fibonacci(2^29=536870912) 需 44.195383s；（有 372,718,289 bits，十进制下为 112,199,358 位）
GMP V4.2.2 呢？

GMP的官方网站上称自己为地球上最快的大数库，所以我想与之对比一下。
为什么不选阶乘，而选“Fibonacci”比较？
因为前者我有针对性地对阶乘本身作了大量优化，恐对其它软件评测不公平；
而“Fibonacci”算法相对较简单，其速度基本可以反映一个算法库的大数核心乘法算法的效率。

由于我没有 Linux 平台，所以欢迎具备条件的网友对比测试一下 GMP 与 HugeCalc 的效率，谢谢！（最好是当前配置比较好的机台，如多核CPU）
liangbch 2007-09-11
  • 打赏
  • 举报
 回复
可以看看这个： 那些杂志好发文章（计算机类）？_百度知道 (http://zhidao.baidu.com/question/16682306.html)
日立奔腾浪潮微软松下联想 2007-09-10
  • 打赏
  • 举报
 回复
写成一篇《大整数算法的计算机实现》应该可以在二级学术期刊上发表，
诸如《计算机工程与科学》、《计算机工程与应用》、《计算机应用与软件》等等。
如果理论上没有新颖之处，想在一级学术期刊上发表是比较困难的，
不过也可以试试，《计算数学》、《计算机学报》等。
gxqcn 2007-09-10
  • 打赏
  • 举报
 回复
因为对未注册者限制很少，所以基本等同“免费”:)

这套软件的算法有许多独到之处，我想将它们整理成论文发表，
请问该向哪里投稿？请谁来审稿？欢迎浏览本帖的网友给我指点一二。。。
日立奔腾浪潮微软松下联想 2007-09-10
  • 打赏
  • 举报
 回复
你的软件不是免费的吗？:)
gxqcn 2007-09-05
  • 打赏
  • 举报
 回复
to housisong:
也许责任不在你，因为我用的编译器是VC6.0，而你用的是VC2005.
不过，似乎你的线程池还有优化的余地。:)
housisong 2007-09-04
  • 打赏
  • 举报
 回复
to: gxqcn
这个多线程错误比较奇怪了，我也有一些用它的并行程序，在多核(AMD64x2和酷睿2)上都没有遇到问题；
也许是我的应用中测试时间或次数不够；不过我自己后来用的代码改成了临界区的实现，应该不会有这个问题了;
根据你的测试情况，我把blog上的代码也更新一下，避免其他人也遇到这问题；
gxqcn 2007-09-02
  • 打赏
  • 举报
 回复
如果哪位有四核或八核的机器，不妨测试一下，并将结果公布，不胜感激！
加载更多回复（64）
WV.21-大数阶乘算法1-序
序 大数阶乘的计算是一个有趣的话题，从中学生到大学教授，许多人都投入到这个问题的探索和研究之中，并发表了他们自己的研究成果。如果你用阶乘作关键字在google上搜索，会找到许多此类文章，另外，如果你使用google学术搜索，也能找到一些计算大数阶乘的学术论文。但这些文章和论文的深度有限，并没有给出一个高速的算法和程序。   我和许多对大数阶乘感兴趣的人一样，很早就开始编制大数阶乘的程序。从2
阶乘优化算法
阶乘算法优化 2016年11月28日 10:17:37 阅读数：3574 原文地址：http://blog.csdn.net/yxnk/article/details/1665052 我的感言：首先，有一个概念上的认知，即根据阶乘定义而来的常规算法，如果是long int型只能正确计算到12左右的阶乘，如果用double型只能正确计算170左右的阶乘，当然这些只是大概，需要结合实际平台进行...
阶乘算法优化
原文地址：http://blog.csdn.net/yxnk/article/details/1665052 我的感言：首先，有一个概念上的认知，即根据阶乘定义而来的常规算法，如果是long int型只能正确计算到12左右的阶乘，如果用double型只能正确计算170左右的阶乘，当然这些只是大概，需要结合实际平台进行验证。 下面是原文： 序 大数阶乘的计算是一个有趣的话题，从中学生到大学教
大数阶乘
大数阶乘的计算是一个有趣的话题，从中学生到大学教授，许多人都投入到这个问题的探索和研究之中，并发表了他们自己的研究成果。如果你用阶乘作关键字在google上搜索，会找到许多此类文章，另外，如果你使用google学术搜索，也能找到一些计算大数阶乘的学术论文。但这些文章和论文的深度有限，并没有给出一个高速的算法和程序。   我和许多对大数阶乘感兴趣的人一样，很早就开始编制大数阶乘的程序。从2000
大数阶乘(一)
序 大数阶乘的计算是一个有趣的话题，从中学生到大学教授，许多人都投入到这个问题的探索和研究之中，并发表了他们自己的研究成果。如果你用阶乘作关键字在google上搜索，会找到许多此类文章，另外，如果你使用google学术搜索，也能找到一些计算大数阶乘的学术论文。但这些文章和论文的深度有限，并没有给出一个高速的算法和程序。 我和许多对大数阶乘感兴趣的人一样，很早就开始编...
数据结构与算法

33,008

社区成员

35,326

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章