33,008
社区成员
发帖
与我相关
我的任务
分享擂台：超大整数高精度快速算法(续2)
// 本贴为
// http://community.csdn.net/Expert/topic/3049/3049738.xml 及
// http://community.csdn.net/Expert/topic/3197/3197332.xml
// 帖子的延续（因受30次回复限制而结贴）。
本人在业余时间开发了一套《超大整数完全精度快速算法库》HugeCalc，
可快速计算超大整数的加、减、乘、除（商/余）、乘方、开方，
支持任意不同进制下快速相互转换，
也可快速计算大数的 Fibonacci 数列、（双）阶乘、排列、组合等，
还可完成超大整数数组的最大公约数、最小公倍数等数论运算，
现在，该套软件已被华军、天空、电脑之家、天天等下载站点收录。
该算法库采用标准 C++ 开发，未调用任何算法库，
虽然未针对硬件作任何相应的特殊汇编优化，但其速度已非常快！
其最核心的乘法算法现已优于当前的 apfloat、Mathematica、Maple，甚至 GMP！
如计算 Fibonacci 数列的第 10,000,000 项(有 2,089,877 位)，
HugeCalc 仅需 2.562s，可立即输出结果；
Mathematica 需 2.797s，不含输出（测试代码：Timing[Fibonacci[10000000];]）.
计算 1,000,000 的阶乘，
HugeCalc 仅需 12.687s，
Mathematica 则需 23.265s.
因为 CSDN 是一个高手云集的地方，
所以特借这块宝地广泛征集类似算法或软件，以期达到相互促进的目的。
注：
1、HugeCalc 最新（测试）版下载地址：http://www.freewebs.com/maths/download/HugeCalc.rar
2、声明, 设此擂台的目的是为了相互促进，而非争强斗胜（其实我的计算机水平非常有限，只是比较充分地运用了数学知识而已）；
3、算法或软件不限于自身原创，欢迎提供第三方链接信息，谢谢！
4、并不要求所有功能均须强于我现有的软件，有一两项也请及时告诉我，谢谢！
5、特别欢迎各种算法的讨论，本人也将在适当的时机整理出一些核心算法，以便与大家交流；
6、为了在交流中完善该软件，现决定免费公开 HugeCalc.dll 的所有接口文件！大家可以更自由地调用 HugeCalc！
HugeCalc Ver3.0.2.1（beta 版；10月18日将正式发布），已含所有公共接口文件：
http://www.freewebs.com/maths/download/HugeCalc.rar（192 KB）
（主页服务器不太稳定，有时很难下载；可直接与我联系 gxqcn@163.com）
本算法库 HugeCalc.dll Ver3.0.2.1 小巧精悍（169个公共接口，仅 52.2KB），
但其速度完全可与大型专业数学工具软件媲美！
// http://community.csdn.net/Expert/topic/3049/3049738.xml 及
// http://community.csdn.net/Expert/topic/3197/3197332.xml
// 帖子的延续（因受30次回复限制而结贴）。
本人在业余时间开发了一套《超大整数完全精度快速算法库》HugeCalc，
可快速计算超大整数的加、减、乘、除（商/余）、乘方、开方，
支持任意不同进制下快速相互转换，
也可快速计算大数的 Fibonacci 数列、（双）阶乘、排列、组合等，
还可完成超大整数数组的最大公约数、最小公倍数等数论运算，
现在，该套软件已被华军、天空、电脑之家、天天等下载站点收录。
该算法库采用标准 C++ 开发，未调用任何算法库，
虽然未针对硬件作任何相应的特殊汇编优化，但其速度已非常快！
其最核心的乘法算法现已优于当前的 apfloat、Mathematica、Maple，甚至 GMP！
如计算 Fibonacci 数列的第 10,000,000 项(有 2,089,877 位)，
HugeCalc 仅需 2.562s，可立即输出结果；
Mathematica 需 2.797s，不含输出（测试代码：Timing[Fibonacci[10000000];]）.
计算 1,000,000 的阶乘，
HugeCalc 仅需 12.687s，
Mathematica 则需 23.265s.
因为 CSDN 是一个高手云集的地方，
所以特借这块宝地广泛征集类似算法或软件，以期达到相互促进的目的。
注：
1、HugeCalc 最新（测试）版下载地址：http://www.freewebs.com/maths/download/HugeCalc.rar
2、声明, 设此擂台的目的是为了相互促进，而非争强斗胜（其实我的计算机水平非常有限，只是比较充分地运用了数学知识而已）；
3、算法或软件不限于自身原创，欢迎提供第三方链接信息，谢谢！
4、并不要求所有功能均须强于我现有的软件，有一两项也请及时告诉我，谢谢！
5、特别欢迎各种算法的讨论，本人也将在适当的时机整理出一些核心算法，以便与大家交流；
6、为了在交流中完善该软件，现决定免费公开 HugeCalc.dll 的所有接口文件！大家可以更自由地调用 HugeCalc！
HugeCalc Ver3.0.2.1（beta 版；10月18日将正式发布），已含所有公共接口文件：
http://www.freewebs.com/maths/download/HugeCalc.rar（192 KB）
（主页服务器不太稳定，有时很难下载；可直接与我联系 gxqcn@163.com）
本算法库 HugeCalc.dll Ver3.0.2.1 小巧精悍（169个公共接口，仅 52.2KB），
但其速度完全可与大型专业数学工具软件媲美！
...全文
请发表友善的回复…
发表回复
realside 2005-05-04
- 打赏
- 举报
to: JTZY(GxQ结贴专用马甲)
谢谢你的关注，我意指32K digitals，实际是64K digitals
希望能互相交流，我的QQ249156409请注册CSDN
谢谢你的关注，我意指32K digitals，实际是64K digitals
希望能互相交流，我的QQ249156409请注册CSDN
JTZY 2005-04-30
- 打赏
- 举报
HugeCalc V5.0.0.1 的评估版发布了！
================================
下载地址为：http://maths.myrice.com/download/HugeCalc.rar (248 KB)
相对于 HugeCalc V4.0.0.0，更新点为：
⊙ 新增16进制算法系统（可与原10进制算法系统灵活转换）
⊙ 新增AND/OR/XOR等位运算
⊙ 新增超大整数取对数运算
⊙ 导出函数新增到 377 个
⊙ 改写了部分核心算法，解掉几处小bug
关于 HugeCalc.exe 的简单说明（界面见：http://maths.myrice.com/image/ui_HugeCalc.gif）：
HugeCalc.exe 的功能仅为 Demo&Test，所以界面显得简陋了些！:(
它含有两套进制系统，各有 A、B、C、D、E、F 六个变量，它们是相互对立的，这点必须注意。
另，现在对应的帮助文件正在编写中，压缩包中的 HugeCalc.chm 仍为旧版 HugeCalc V4.0.0.0 的，请不要被误导；同时停止办理对 HugeCalc V4.0.0.0 的（免费）注册。
HugeCalc V5.0.0.1 实现了许多突破，其正式版本最迟可于2005年6月初面世，敬请关注！
如果您发现问题，或有好的建议，请及时反馈，谢谢！
（email: gxqcn@1630.com; HugeCalc@Gmail.com）
//===============================================================================
由于本贴已限制楼主回复（30条所限），所以本人将于“5.1”长假后一周内关闭本贴。
并将视大家对该话题的感兴趣程度决定是否开新贴继续讨论。
祝各位五一快乐！
另，由于我家上网不方便，所以对网友的回复都将在长假结束后进行，请见谅！
================================
下载地址为：http://maths.myrice.com/download/HugeCalc.rar (248 KB)
相对于 HugeCalc V4.0.0.0，更新点为：
⊙ 新增16进制算法系统（可与原10进制算法系统灵活转换）
⊙ 新增AND/OR/XOR等位运算
⊙ 新增超大整数取对数运算
⊙ 导出函数新增到 377 个
⊙ 改写了部分核心算法，解掉几处小bug
关于 HugeCalc.exe 的简单说明（界面见：http://maths.myrice.com/image/ui_HugeCalc.gif）：
HugeCalc.exe 的功能仅为 Demo&Test，所以界面显得简陋了些！:(
它含有两套进制系统，各有 A、B、C、D、E、F 六个变量，它们是相互对立的，这点必须注意。
另，现在对应的帮助文件正在编写中，压缩包中的 HugeCalc.chm 仍为旧版 HugeCalc V4.0.0.0 的，请不要被误导；同时停止办理对 HugeCalc V4.0.0.0 的（免费）注册。
HugeCalc V5.0.0.1 实现了许多突破，其正式版本最迟可于2005年6月初面世，敬请关注！
如果您发现问题，或有好的建议，请及时反馈，谢谢！
（email: gxqcn@1630.com; HugeCalc@Gmail.com）
//===============================================================================
由于本贴已限制楼主回复（30条所限），所以本人将于“5.1”长假后一周内关闭本贴。
并将视大家对该话题的感兴趣程度决定是否开新贴继续讨论。
祝各位五一快乐！
另，由于我家上网不方便，所以对网友的回复都将在长假结束后进行，请见谅！
JTZY 2005-04-25
- 打赏
- 举报
很奇怪的ID吧？JTZY-->结贴专用-->这是“一个贴子的回复不能超过30个”催化的结果！：）
轮到俺上场，就意味着该话题到了不得已而结贴的地步了。
to realside()：
很高兴能看到有类似功能的软件问世。愿我们可以相互交流，共同促进。
但我不太明白你说的“32K长度的双数相乘”的确切意义，是指32K bits？还是32K digitals(即我们通常数学意义上的位)？又或是你内部数据结构中需要32K个内存单元存储的数？32K是乘数及被乘数的大小，还是积的大小？
自测(P1.7G, 256RAM, XP)了下HugeCalc V5.0.0.1（尚未公开）：
B=Fibonacci(200000), C=Fibonacci(200001)，计算 A = B * C 的耗时，结果如下：
(1)、10进制系统：0.036s；A、B、C的位数分别为 83595、41798、41798；
(2)、16进制系统：0.035s；A、B、C的位数分别为 69424、34712、34712.
注：之所以选择用 Fibonacci 数列测试，是因为其尾部不会产生大片的连续“0”（如果出现这种情况，乘法可优化，使测试“缩水”），且大家容易得到。
我的 HugeCalc 如完全不用汇编，效率大概会下降一半。HugeCalc 也是可以轻易移值到其它OS环境中，且无须任何浮点运算支持（内部未调用任何数学算法库，甚至未“#include <math.h>”或“#include <cmath>”）。
关于除法，可转化成 A/B=A*(1/B)，其中(1/B)用牛顿迭代法可很快计算出来。此时，除法的效率就直接与乘法效率相挂钩。从你的测试结果来看，乘法效率仍有很大提升空间。
轮到俺上场，就意味着该话题到了不得已而结贴的地步了。
to realside()：
很高兴能看到有类似功能的软件问世。愿我们可以相互交流，共同促进。
但我不太明白你说的“32K长度的双数相乘”的确切意义，是指32K bits？还是32K digitals(即我们通常数学意义上的位)？又或是你内部数据结构中需要32K个内存单元存储的数？32K是乘数及被乘数的大小，还是积的大小？
自测(P1.7G, 256RAM, XP)了下HugeCalc V5.0.0.1（尚未公开）：
B=Fibonacci(200000), C=Fibonacci(200001)，计算 A = B * C 的耗时，结果如下：
(1)、10进制系统：0.036s；A、B、C的位数分别为 83595、41798、41798；
(2)、16进制系统：0.035s；A、B、C的位数分别为 69424、34712、34712.
注：之所以选择用 Fibonacci 数列测试，是因为其尾部不会产生大片的连续“0”（如果出现这种情况，乘法可优化，使测试“缩水”），且大家容易得到。
我的 HugeCalc 如完全不用汇编，效率大概会下降一半。HugeCalc 也是可以轻易移值到其它OS环境中，且无须任何浮点运算支持（内部未调用任何数学算法库，甚至未“#include <math.h>”或“#include <cmath>”）。
关于除法，可转化成 A/B=A*(1/B)，其中(1/B)用牛顿迭代法可很快计算出来。此时，除法的效率就直接与乘法效率相挂钩。从你的测试结果来看，乘法效率仍有很大提升空间。
realside 2005-04-24
- 打赏
- 举报
（接上）
程序没有调用汇编指令，因此可以轻易移值到其它OS环境中。经测试，32K长度的双数相乘，大约耗时1~2秒。(P2.4G ,512RAM)
程序没有调用汇编指令，因此可以轻易移值到其它OS环境中。经测试，32K长度的双数相乘，大约耗时1~2秒。(P2.4G ,512RAM)
realside 2005-04-24
- 打赏
- 举报
我已经写好了一套超大整数（长度不受限制）的基本运算库，但除法运算有些问题。望楼主能告之除法运算原理，谢谢先！
junmayang 2005-04-20
- 打赏
- 举报
佩服楼主啊!!
我也来凑凑热闹，写了一个阶乘的算法，由于数学知识欠缺，未作数学上的优化，只是在代码上下了一些功夫，速度也还可以了，10000！1.3s，没有上限，需要代码的朋友可以留下MAIL，交流交流！
我将对算法作数学上的优化，争取能够快一些，向楼主学习！！
我也来凑凑热闹，写了一个阶乘的算法，由于数学知识欠缺，未作数学上的优化，只是在代码上下了一些功夫，速度也还可以了，10000！1.3s，没有上限，需要代码的朋友可以留下MAIL，交流交流！
我将对算法作数学上的优化，争取能够快一些，向楼主学习！！
gxqcn 2005-04-05
- 打赏
- 举报
//==========HugeCalc bug 警报==========
... Combination( const UINT32 n, const UINT32 r )
{
//...
// now, r <= n - r
if ( n < ( r << 1 ))
// return Permutation( n, n - r ); 由 xxx@ustc.edu 指出，2005-04-05 更正
return Combination( n, n - r );
//...
}
也就是说，以前计算Combination(40,21)，实际被误算成了Permutation(40,19)，当然错了。
该 bug 是由中国科学技术大学的一位同学在科研中用 HugeCalc 发现的，我已更正，请大家及时更新。
（更新: http://www.bossh.net/forums/index.php?act=Attach&type=post&id=66156）
//==========HugeCalc 近况通报==========
我正在开发下一版 HugeCalc，在保留现有的10进制的 CHugeInt 基础上，将新增16进制版本 CHugeIntX（暂用名），并新增与、或、异或等逻辑运算；同时改写内部核心算法，预计速度将会再次提高。
请大家对新版本的期望和建议反馈给我，以使新版本开发更完善，谢谢！
... Combination( const UINT32 n, const UINT32 r )
{
//...
// now, r <= n - r
if ( n < ( r << 1 ))
// return Permutation( n, n - r ); 由 xxx@ustc.edu 指出，2005-04-05 更正
return Combination( n, n - r );
//...
}
也就是说，以前计算Combination(40,21)，实际被误算成了Permutation(40,19)，当然错了。
该 bug 是由中国科学技术大学的一位同学在科研中用 HugeCalc 发现的，我已更正，请大家及时更新。
（更新: http://www.bossh.net/forums/index.php?act=Attach&type=post&id=66156）
//==========HugeCalc 近况通报==========
我正在开发下一版 HugeCalc，在保留现有的10进制的 CHugeInt 基础上，将新增16进制版本 CHugeIntX（暂用名），并新增与、或、异或等逻辑运算；同时改写内部核心算法，预计速度将会再次提高。
请大家对新版本的期望和建议反馈给我，以使新版本开发更完善，谢谢！
MayFlower 2005-03-24
- 打赏
- 举报
Give us some benchmark comparing with GMP.
Mathematica and Maple are not good at this kind of things.
If you can beat GMP, you are really very good !!
Mathematica and Maple are not good at this kind of things.
If you can beat GMP, you are really very good !!
gxqcn 2005-03-24
- 打赏
- 举报
to MayFlower(五月花)：
正如你的“很可惜，我用的linux平台，无法做些测试工作了”，我在 windows 平台，无法测试 GMP，所以不好对比。
曾有人说 Maple 用的是 GMP 的内核，所以我才与 Maple 进行比较。
正如你的“很可惜，我用的linux平台，无法做些测试工作了”，我在 windows 平台，无法测试 GMP，所以不好对比。
曾有人说 Maple 用的是 GMP 的内核，所以我才与 Maple 进行比较。
gxqcn 2005-03-23
- 打赏
- 举报
请见我在 擂台：超大整数高精度快速算法(续) ：
http://community.csdn.net/Expert/topic/3197/3197332.xml
中 2004-9-9 8:25:04 时的回复。
http://community.csdn.net/Expert/topic/3197/3197332.xml
中 2004-9-9 8:25:04 时的回复。
TomDebug 2005-03-20
- 打赏
- 举报
楼主,我最近自己也在写大数的运算,到除的时候卡住了,可以把你的除运算算法给我介绍一下吗?没想到你的库这么全啊,我只想到了幂运算,还是做ACM想到的,我的邮箱是hefehoo@163.com,最好通俗一点的语言
cuixiping 2005-03-14
- 打赏
- 举报
mark
MayFlower 2005-03-11
- 打赏
- 举报
回应你上面作的测试，我给个GMP的数据：
1,000,000 ! P4-M 1.5GHz
GMP real: 12.429s user: 11.711s sys: 0.121s
我还是GMP 的支持者，
如果GMP 比Hugecalc快，又开放源码，支持多平台，
常见的x86，sparc等，那么。。。。就当是学习交流吧。
如果可以，哪位给点Hugealc的测试数据。
1,000,000 ! P4-M 1.5GHz
GMP real: 12.429s user: 11.711s sys: 0.121s
我还是GMP 的支持者，
如果GMP 比Hugecalc快，又开放源码，支持多平台，
常见的x86，sparc等，那么。。。。就当是学习交流吧。
如果可以，哪位给点Hugealc的测试数据。
MayFlower 2005-03-11
- 打赏
- 举报
看上去这个包是DLL，仅限windows平台的，
而且没有开放源码，很可惜，我用的linux平台，无法做些测试工作了，
就目前我对GMP 大数乘法的了解，他的速度已经相当的不错了，
除了些特别的情况比如两个数位数相差特别大等等。
所以，如果条件允许，我倒是愿意看看楼主的算法（我主要是关心大数相乘）
关于实用性，如果你的代码有一些汇编的话，那么似乎是仅限于x86平台了
如果有谁作过和gmp的详细比较，不妨帖出来看看。
to joey5491：
谢谢指导！
而且没有开放源码，很可惜，我用的linux平台，无法做些测试工作了，
就目前我对GMP 大数乘法的了解，他的速度已经相当的不错了，
除了些特别的情况比如两个数位数相差特别大等等。
所以，如果条件允许，我倒是愿意看看楼主的算法（我主要是关心大数相乘）
关于实用性，如果你的代码有一些汇编的话，那么似乎是仅限于x86平台了
如果有谁作过和gmp的详细比较，不妨帖出来看看。
to joey5491：
谢谢指导！
gxqcn 2005-03-08
- 打赏
- 举报
很高兴，还有不少人对该问题感兴趣，在关注本话题。
下面介绍一下我自己近来的一些进展：对程序进一步进行了一些优化，某些模块甚至提高了数十倍效率；还有大量的对比实验去做（有时候算法研究，不仅仅是理论推导，也需要一些特定的测试实验）。而这所有的一切，我只能在有限的业余时间进行；同时初为人父的我，还必须尽一个父亲的责任和义务，所以版本的升级更新相对会放迟缓一些了。。。
但关于高精度快速算法的研究，我仍会继续，并关注各位网友的反馈，如果大家有任何建议和问题，请访问如下链接（因为我会经常去浏览的）：
1、CSDN - 技术社区：http://community.csdn.net/Expert/topic/3441/3441530.xml
2、数学研发论坛：http://rd.xilubbs.com/
3、博士家园：http://www.bossh.net/forums/index.php?showtopic=774
下面介绍一下我自己近来的一些进展：对程序进一步进行了一些优化，某些模块甚至提高了数十倍效率；还有大量的对比实验去做（有时候算法研究，不仅仅是理论推导，也需要一些特定的测试实验）。而这所有的一切，我只能在有限的业余时间进行；同时初为人父的我，还必须尽一个父亲的责任和义务，所以版本的升级更新相对会放迟缓一些了。。。
但关于高精度快速算法的研究，我仍会继续，并关注各位网友的反馈，如果大家有任何建议和问题，请访问如下链接（因为我会经常去浏览的）：
1、CSDN - 技术社区：http://community.csdn.net/Expert/topic/3441/3441530.xml
2、数学研发论坛：http://rd.xilubbs.com/
3、博士家园：http://www.bossh.net/forums/index.php?showtopic=774
zengwujun 2005-03-06
- 打赏
- 举报
mark
yeeshengwei 2005-01-21
- 打赏
- 举报
呵呵！这个有意思！up!
gxqcn 2005-01-07
- 打赏
- 举报
HugeCalc V4.0.0.0 精简版（2005-01-05 修正）下载链接：
http://www.allaboutprogram.com/bb/download.php?id=129（202 KB）
http://www.allaboutprogram.com/bb/download.php?id=129（202 KB）
fireofhell 2005-01-06
- 打赏
- 举报
这个帖现在还在讨论啊，难得！我好久前就看到过了，确实有几位高手在，俺刚来csdn混的时候就知道mathe这个人经常发帖，数学比较强的人！
gxqcn 2005-01-05
- 打赏
- 举报
经网友反馈，发现一个bug，请见：http://bbs.xilu.com/cgi-bin/bbs/view?forum=rd&message=3884
加载更多回复（68）
